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, PoisonValue::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(PoisonValue::get(Ty), LoopBB); 143 ScalarEvolution SE = buildSE(*F); 144 const SCEV *S1 = SE.getSCEV(PN); 145 const SCEV *S2 = SE.getSCEV(PN); 146 const SCEV *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 const SCEV *FirstExprForIV0 = SE.getSCEV(IV0); 242 const SCEV *FirstExprForIV0Inc = SE.getSCEV(IV0Inc); 243 const SCEV *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 const SCEV *Mul0 = SE.getMulExpr(Ops0); 264 const SCEV *Mul1 = SE.getMulExpr(Ops1); 265 const SCEV *Mul2 = SE.getMulExpr(Ops2); 266 const SCEV *Mul3 = SE.getMulExpr(Ops3); 267 const SCEV *Mul4 = SE.getMulExpr(Ops4); 268 const SCEV *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(PoisonValue::get(Ty), EntryBB); 332 } 333 334 BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F); 335 BranchInst::Create(LoopBB, ExitBB, PoisonValue::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 const SCEV *A = SE.getSCEV(MulA); 387 const SCEV *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 const SCEV *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 const SCEV *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 const SCEV *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 poison, 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 poison, label %loop_0, label %loop_1 " 507 " " 508 "loop_1: " 509 " br i1 poison, label %loop_2, label %loop_1 " 510 " " 511 " " 512 "loop_2: " 513 " br i1 poison, label %end, label %loop_2 " 514 " " 515 "end: " 516 " ret void " 517 "} ", 518 Err, C); 519 520 assert(M && "Could not parse module?"); 521 assert(!verifyModule(*M) && "Must have been well formed!"); 522 523 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 524 auto &I0 = GetInstByName(F, "iv0"); 525 auto &I1 = *I0.getNextNode(); 526 527 auto *S0 = cast<SCEVAddRecExpr>(SE.getSCEV(&I0)); 528 PostIncLoopSet Loops; 529 Loops.insert(S0->getLoop()); 530 auto *N0 = normalizeForPostIncUse(S0, Loops, SE); 531 auto *D0 = denormalizeForPostIncUse(N0, Loops, SE); 532 EXPECT_EQ(S0, D0) << *S0 << " " << *D0; 533 534 auto *S1 = cast<SCEVAddRecExpr>(SE.getSCEV(&I1)); 535 Loops.clear(); 536 Loops.insert(S1->getLoop()); 537 auto *N1 = normalizeForPostIncUse(S1, Loops, SE); 538 auto *D1 = denormalizeForPostIncUse(N1, Loops, SE); 539 EXPECT_EQ(S1, D1) << *S1 << " " << *D1; 540 }); 541 542 runWithSE(*M, "f_2", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 543 auto *L2 = *LI.begin(); 544 auto *L1 = *std::next(LI.begin()); 545 auto *L0 = *std::next(LI.begin(), 2); 546 547 auto GetAddRec = [&SE](const Loop *L, std::initializer_list<const SCEV *> Ops) { 548 SmallVector<const SCEV *, 4> OpsCopy(Ops); 549 return SE.getAddRecExpr(OpsCopy, L, SCEV::FlagAnyWrap); 550 }; 551 552 auto GetAdd = [&SE](std::initializer_list<const SCEV *> Ops) { 553 SmallVector<const SCEV *, 4> OpsCopy(Ops); 554 return SE.getAddExpr(OpsCopy, SCEV::FlagAnyWrap); 555 }; 556 557 // We first populate the AddRecs vector with a few "interesting" SCEV 558 // expressions, and then we go through the list and assert that each 559 // expression in it has an invertible normalization. 560 561 std::vector<const SCEV *> Exprs; 562 { 563 const SCEV *V0 = SE.getSCEV(&*F.arg_begin()); 564 const SCEV *V1 = SE.getSCEV(&*std::next(F.arg_begin(), 1)); 565 const SCEV *V2 = SE.getSCEV(&*std::next(F.arg_begin(), 2)); 566 const SCEV *V3 = SE.getSCEV(&*std::next(F.arg_begin(), 3)); 567 568 Exprs.push_back(GetAddRec(L0, {V0})); // 0 569 Exprs.push_back(GetAddRec(L0, {V0, V1})); // 1 570 Exprs.push_back(GetAddRec(L0, {V0, V1, V2})); // 2 571 Exprs.push_back(GetAddRec(L0, {V0, V1, V2, V3})); // 3 572 573 Exprs.push_back( 574 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[3], Exprs[0]})); // 4 575 Exprs.push_back( 576 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[0], Exprs[3]})); // 5 577 Exprs.push_back( 578 GetAddRec(L1, {Exprs[1], Exprs[3], Exprs[3], Exprs[1]})); // 6 579 580 Exprs.push_back(GetAdd({Exprs[6], Exprs[3], V2})); // 7 581 582 Exprs.push_back( 583 GetAddRec(L2, {Exprs[4], Exprs[3], Exprs[3], Exprs[5]})); // 8 584 585 Exprs.push_back( 586 GetAddRec(L2, {Exprs[4], Exprs[6], Exprs[7], Exprs[3], V0})); // 9 587 } 588 589 std::vector<PostIncLoopSet> LoopSets; 590 for (int i = 0; i < 8; i++) { 591 LoopSets.emplace_back(); 592 if (i & 1) 593 LoopSets.back().insert(L0); 594 if (i & 2) 595 LoopSets.back().insert(L1); 596 if (i & 4) 597 LoopSets.back().insert(L2); 598 } 599 600 for (const auto &LoopSet : LoopSets) 601 for (auto *S : Exprs) { 602 { 603 auto *N = llvm::normalizeForPostIncUse(S, LoopSet, SE); 604 auto *D = llvm::denormalizeForPostIncUse(N, LoopSet, SE); 605 606 // Normalization and then denormalizing better give us back the same 607 // value. 608 EXPECT_EQ(S, D) << "S = " << *S << " D = " << *D << " N = " << *N; 609 } 610 { 611 auto *D = llvm::denormalizeForPostIncUse(S, LoopSet, SE); 612 auto *N = llvm::normalizeForPostIncUse(D, LoopSet, SE); 613 614 // Denormalization and then normalizing better give us back the same 615 // value. 616 EXPECT_EQ(S, N) << "S = " << *S << " N = " << *N; 617 } 618 } 619 }); 620 } 621 622 // Expect the call of getZeroExtendExpr will not cost exponential time. 623 TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExpr) { 624 LLVMContext C; 625 SMDiagnostic Err; 626 627 // Generate a function like below: 628 // define void @foo() { 629 // entry: 630 // br label %for.cond 631 // 632 // for.cond: 633 // %0 = phi i64 [ 100, %entry ], [ %dec, %for.inc ] 634 // %cmp = icmp sgt i64 %0, 90 635 // br i1 %cmp, label %for.inc, label %for.cond1 636 // 637 // for.inc: 638 // %dec = add nsw i64 %0, -1 639 // br label %for.cond 640 // 641 // for.cond1: 642 // %1 = phi i64 [ 100, %for.cond ], [ %dec5, %for.inc2 ] 643 // %cmp3 = icmp sgt i64 %1, 90 644 // br i1 %cmp3, label %for.inc2, label %for.cond4 645 // 646 // for.inc2: 647 // %dec5 = add nsw i64 %1, -1 648 // br label %for.cond1 649 // 650 // ...... 651 // 652 // for.cond89: 653 // %19 = phi i64 [ 100, %for.cond84 ], [ %dec94, %for.inc92 ] 654 // %cmp93 = icmp sgt i64 %19, 90 655 // br i1 %cmp93, label %for.inc92, label %for.end 656 // 657 // for.inc92: 658 // %dec94 = add nsw i64 %19, -1 659 // br label %for.cond89 660 // 661 // for.end: 662 // %gep = getelementptr i8, i8* null, i64 %dec 663 // %gep6 = getelementptr i8, i8* %gep, i64 %dec5 664 // ...... 665 // %gep95 = getelementptr i8, i8* %gep91, i64 %dec94 666 // ret void 667 // } 668 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false); 669 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M); 670 671 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 672 BasicBlock *CondBB = BasicBlock::Create(Context, "for.cond", F); 673 BasicBlock *EndBB = BasicBlock::Create(Context, "for.end", F); 674 BranchInst::Create(CondBB, EntryBB); 675 BasicBlock *PrevBB = EntryBB; 676 677 Type *I64Ty = Type::getInt64Ty(Context); 678 Type *I8Ty = Type::getInt8Ty(Context); 679 Type *I8PtrTy = PointerType::getUnqual(Context); 680 Value *Accum = Constant::getNullValue(I8PtrTy); 681 int Iters = 20; 682 for (int i = 0; i < Iters; i++) { 683 BasicBlock *IncBB = BasicBlock::Create(Context, "for.inc", F, EndBB); 684 auto *PN = PHINode::Create(I64Ty, 2, "", CondBB); 685 PN->addIncoming(ConstantInt::get(Context, APInt(64, 100)), PrevBB); 686 auto *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_SGT, PN, 687 ConstantInt::get(Context, APInt(64, 90)), "cmp", 688 CondBB); 689 BasicBlock *NextBB; 690 if (i != Iters - 1) 691 NextBB = BasicBlock::Create(Context, "for.cond", F, EndBB); 692 else 693 NextBB = EndBB; 694 BranchInst::Create(IncBB, NextBB, Cmp, CondBB); 695 auto *Dec = BinaryOperator::CreateNSWAdd( 696 PN, ConstantInt::get(Context, APInt(64, -1)), "dec", IncBB); 697 PN->addIncoming(Dec, IncBB); 698 BranchInst::Create(CondBB, IncBB); 699 700 Accum = GetElementPtrInst::Create(I8Ty, Accum, PN, "gep", EndBB); 701 702 PrevBB = CondBB; 703 CondBB = NextBB; 704 } 705 ReturnInst::Create(Context, nullptr, EndBB); 706 ScalarEvolution SE = buildSE(*F); 707 const SCEV *S = SE.getSCEV(Accum); 708 S = SE.getLosslessPtrToIntExpr(S); 709 Type *I128Ty = Type::getInt128Ty(Context); 710 SE.getZeroExtendExpr(S, I128Ty); 711 } 712 713 // Make sure that SCEV invalidates exit limits after invalidating the values it 714 // depends on when we forget a loop. 715 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) { 716 /* 717 * Create the following code: 718 * func(i64 addrspace(10)* %arg) 719 * top: 720 * br label %L.ph 721 * L.ph: 722 * br label %L 723 * L: 724 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ] 725 * %add = add i64 %phi2, 1 726 * %cond = icmp slt i64 %add, 1000; then becomes 2000. 727 * br i1 %cond, label %post, label %L2 728 * post: 729 * ret void 730 * 731 */ 732 733 // Create a module with non-integral pointers in it's datalayout 734 Module NIM("nonintegral", Context); 735 std::string DataLayout = M.getDataLayoutStr(); 736 if (!DataLayout.empty()) 737 DataLayout += "-"; 738 DataLayout += "ni:10"; 739 NIM.setDataLayout(DataLayout); 740 741 Type *T_int64 = Type::getInt64Ty(Context); 742 Type *T_pint64 = PointerType::get(Context, 10); 743 744 FunctionType *FTy = 745 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 746 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM); 747 748 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 749 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 750 BasicBlock *L = BasicBlock::Create(Context, "L", F); 751 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 752 753 IRBuilder<> Builder(Top); 754 Builder.CreateBr(LPh); 755 756 Builder.SetInsertPoint(LPh); 757 Builder.CreateBr(L); 758 759 Builder.SetInsertPoint(L); 760 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 761 auto *Add = cast<Instruction>( 762 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); 763 auto *Limit = ConstantInt::get(T_int64, 1000); 764 auto *Cond = cast<Instruction>( 765 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond")); 766 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post)); 767 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 768 Phi->addIncoming(Add, L); 769 770 Builder.SetInsertPoint(Post); 771 Builder.CreateRetVoid(); 772 773 ScalarEvolution SE = buildSE(*F); 774 auto *Loop = LI->getLoopFor(L); 775 const SCEV *EC = SE.getBackedgeTakenCount(Loop); 776 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC)); 777 EXPECT_TRUE(isa<SCEVConstant>(EC)); 778 EXPECT_EQ(cast<SCEVConstant>(EC)->getAPInt().getLimitedValue(), 999u); 779 780 // The add recurrence {5,+,1} does not correspond to any PHI in the IR, and 781 // that is relevant to this test. 782 const SCEV *Five = SE.getConstant(APInt(/*numBits=*/64, 5)); 783 const SCEV *AR = 784 SE.getAddRecExpr(Five, SE.getOne(T_int64), Loop, SCEV::FlagAnyWrap); 785 const SCEV *ARAtLoopExit = SE.getSCEVAtScope(AR, nullptr); 786 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ARAtLoopExit)); 787 EXPECT_TRUE(isa<SCEVConstant>(ARAtLoopExit)); 788 EXPECT_EQ(cast<SCEVConstant>(ARAtLoopExit)->getAPInt().getLimitedValue(), 789 1004u); 790 791 SE.forgetLoop(Loop); 792 Br->eraseFromParent(); 793 Cond->eraseFromParent(); 794 795 Builder.SetInsertPoint(L); 796 auto *NewCond = Builder.CreateICmp( 797 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond"); 798 Builder.CreateCondBr(NewCond, L, Post); 799 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop); 800 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC)); 801 EXPECT_TRUE(isa<SCEVConstant>(NewEC)); 802 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u); 803 const SCEV *NewARAtLoopExit = SE.getSCEVAtScope(AR, nullptr); 804 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewARAtLoopExit)); 805 EXPECT_TRUE(isa<SCEVConstant>(NewARAtLoopExit)); 806 EXPECT_EQ(cast<SCEVConstant>(NewARAtLoopExit)->getAPInt().getLimitedValue(), 807 2004u); 808 } 809 810 // Make sure that SCEV invalidates exit limits after invalidating the values it 811 // depends on when we forget a value. 812 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) { 813 /* 814 * Create the following code: 815 * func(i64 addrspace(10)* %arg) 816 * top: 817 * br label %L.ph 818 * L.ph: 819 * %load = load i64 addrspace(10)* %arg 820 * br label %L 821 * L: 822 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ] 823 * %add = add i64 %phi2, 1 824 * %cond = icmp slt i64 %add, %load ; then becomes 2000. 825 * br i1 %cond, label %post, label %L2 826 * post: 827 * ret void 828 * 829 */ 830 831 // Create a module with non-integral pointers in it's datalayout 832 Module NIM("nonintegral", Context); 833 std::string DataLayout = M.getDataLayoutStr(); 834 if (!DataLayout.empty()) 835 DataLayout += "-"; 836 DataLayout += "ni:10"; 837 NIM.setDataLayout(DataLayout); 838 839 Type *T_int64 = Type::getInt64Ty(Context); 840 Type *T_pint64 = PointerType::get(Context, 10); 841 842 FunctionType *FTy = 843 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 844 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM); 845 846 Argument *Arg = &*F->arg_begin(); 847 848 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 849 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 850 BasicBlock *L = BasicBlock::Create(Context, "L", F); 851 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 852 853 IRBuilder<> Builder(Top); 854 Builder.CreateBr(LPh); 855 856 Builder.SetInsertPoint(LPh); 857 auto *Load = cast<Instruction>(Builder.CreateLoad(T_int64, Arg, "load")); 858 Builder.CreateBr(L); 859 860 Builder.SetInsertPoint(L); 861 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 862 auto *Add = cast<Instruction>( 863 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); 864 auto *Cond = cast<Instruction>( 865 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond")); 866 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post)); 867 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 868 Phi->addIncoming(Add, L); 869 870 Builder.SetInsertPoint(Post); 871 Builder.CreateRetVoid(); 872 873 ScalarEvolution SE = buildSE(*F); 874 auto *Loop = LI->getLoopFor(L); 875 const SCEV *EC = SE.getBackedgeTakenCount(Loop); 876 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC)); 877 EXPECT_FALSE(isa<SCEVConstant>(EC)); 878 879 SE.forgetValue(Load); 880 Br->eraseFromParent(); 881 Cond->eraseFromParent(); 882 Load->eraseFromParent(); 883 884 Builder.SetInsertPoint(L); 885 auto *NewCond = Builder.CreateICmp( 886 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond"); 887 Builder.CreateCondBr(NewCond, L, Post); 888 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop); 889 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC)); 890 EXPECT_TRUE(isa<SCEVConstant>(NewEC)); 891 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u); 892 } 893 894 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) { 895 // Reference: https://reviews.llvm.org/D37265 896 // Make sure that SCEV does not blow up when constructing an AddRec 897 // with predicates for a phi with the update pattern: 898 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum 899 // when either the initial value of the Phi or the InvariantAccum are 900 // constants that are too large to fit in an ix but are zero when truncated to 901 // ix. 902 FunctionType *FTy = 903 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false); 904 Function *F = 905 Function::Create(FTy, Function::ExternalLinkage, "addrecphitest", M); 906 907 /* 908 Create IR: 909 entry: 910 br label %loop 911 loop: 912 %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop] 913 %1 = shl i64 %0, 32 914 %2 = ashr exact i64 %1, 32 915 %3 = add i64 %2, -9223372036854775808 916 br i1 poison, label %exit, label %loop 917 exit: 918 ret void 919 */ 920 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 921 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 922 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 923 924 // entry: 925 BranchInst::Create(LoopBB, EntryBB); 926 // loop: 927 auto *MinInt64 = 928 ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true)); 929 auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32)); 930 auto *Br = BranchInst::Create( 931 LoopBB, ExitBB, PoisonValue::get(Type::getInt1Ty(Context)), LoopBB); 932 auto *Phi = 933 PHINode::Create(Type::getInt64Ty(Context), 2, "", Br->getIterator()); 934 auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br->getIterator()); 935 auto *AShr = 936 BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br->getIterator()); 937 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br->getIterator()); 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 poison, 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)); 987 auto *Int32_16 = ConstantInt::get(Context, APInt(32, 16)); 988 auto *Br = BranchInst::Create( 989 LoopBB, ExitBB, PoisonValue::get(Type::getInt1Ty(Context)), LoopBB); 990 auto *Phi = PHINode::Create(Int32Ty, 2, "", Br->getIterator()); 991 auto *Shl = BinaryOperator::CreateShl(Phi, Int32_16, "", Br->getIterator()); 992 auto *AShr = 993 BinaryOperator::CreateExactAShr(Shl, Int32_16, "", Br->getIterator()); 994 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt32, "", Br->getIterator()); 995 auto *Arg = &*(F->arg_begin()); 996 Phi->addIncoming(Arg, EntryBB); 997 Phi->addIncoming(Add, LoopBB); 998 // exit: 999 ReturnInst::Create(Context, nullptr, ExitBB); 1000 1001 // Make sure that SCEV doesn't blow up 1002 ScalarEvolution SE = buildSE(*F); 1003 const SCEV *Expr = SE.getSCEV(Phi); 1004 EXPECT_NE(nullptr, Expr); 1005 EXPECT_TRUE(isa<SCEVUnknown>(Expr)); 1006 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr)); 1007 } 1008 1009 TEST_F(ScalarEvolutionsTest, SCEVFoldSumOfTruncs) { 1010 // Verify that the following SCEV gets folded to a zero: 1011 // (-1 * (trunc i64 (-1 * %0) to i32)) + (-1 * (trunc i64 %0 to i32) 1012 Type *ArgTy = Type::getInt64Ty(Context); 1013 Type *Int32Ty = Type::getInt32Ty(Context); 1014 SmallVector<Type *, 1> Types; 1015 Types.push_back(ArgTy); 1016 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 1017 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 1018 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 1019 ReturnInst::Create(Context, nullptr, BB); 1020 1021 ScalarEvolution SE = buildSE(*F); 1022 1023 auto *Arg = &*(F->arg_begin()); 1024 const SCEV *ArgSCEV = SE.getSCEV(Arg); 1025 1026 // Build the SCEV 1027 const SCEV *A0 = SE.getNegativeSCEV(ArgSCEV); 1028 const SCEV *A1 = SE.getTruncateExpr(A0, Int32Ty); 1029 const SCEV *A = SE.getNegativeSCEV(A1); 1030 1031 const SCEV *B0 = SE.getTruncateExpr(ArgSCEV, Int32Ty); 1032 const SCEV *B = SE.getNegativeSCEV(B0); 1033 1034 const SCEV *Expr = SE.getAddExpr(A, B); 1035 // Verify that the SCEV was folded to 0 1036 const SCEV *ZeroConst = SE.getConstant(Int32Ty, 0); 1037 EXPECT_EQ(Expr, ZeroConst); 1038 } 1039 1040 // Check logic of SCEV expression size computation. 1041 TEST_F(ScalarEvolutionsTest, SCEVComputeExpressionSize) { 1042 /* 1043 * Create the following code: 1044 * void func(i64 %a, i64 %b) 1045 * entry: 1046 * %s1 = add i64 %a, 1 1047 * %s2 = udiv i64 %s1, %b 1048 * br label %exit 1049 * exit: 1050 * ret 1051 */ 1052 1053 // Create a module. 1054 Module M("SCEVComputeExpressionSize", Context); 1055 1056 Type *T_int64 = Type::getInt64Ty(Context); 1057 1058 FunctionType *FTy = 1059 FunctionType::get(Type::getVoidTy(Context), { T_int64, T_int64 }, false); 1060 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M); 1061 Argument *A = &*F->arg_begin(); 1062 Argument *B = &*std::next(F->arg_begin()); 1063 ConstantInt *C = ConstantInt::get(Context, APInt(64, 1)); 1064 1065 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1066 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F); 1067 1068 IRBuilder<> Builder(Entry); 1069 auto *S1 = cast<Instruction>(Builder.CreateAdd(A, C, "s1")); 1070 auto *S2 = cast<Instruction>(Builder.CreateUDiv(S1, B, "s2")); 1071 Builder.CreateBr(Exit); 1072 1073 Builder.SetInsertPoint(Exit); 1074 Builder.CreateRetVoid(); 1075 1076 ScalarEvolution SE = buildSE(*F); 1077 // Get S2 first to move it to cache. 1078 const SCEV *AS = SE.getSCEV(A); 1079 const SCEV *BS = SE.getSCEV(B); 1080 const SCEV *CS = SE.getSCEV(C); 1081 const SCEV *S1S = SE.getSCEV(S1); 1082 const SCEV *S2S = SE.getSCEV(S2); 1083 EXPECT_EQ(AS->getExpressionSize(), 1u); 1084 EXPECT_EQ(BS->getExpressionSize(), 1u); 1085 EXPECT_EQ(CS->getExpressionSize(), 1u); 1086 EXPECT_EQ(S1S->getExpressionSize(), 3u); 1087 EXPECT_EQ(S2S->getExpressionSize(), 5u); 1088 } 1089 1090 TEST_F(ScalarEvolutionsTest, SCEVLoopDecIntrinsic) { 1091 LLVMContext C; 1092 SMDiagnostic Err; 1093 std::unique_ptr<Module> M = parseAssemblyString( 1094 "define void @foo(i32 %N) { " 1095 "entry: " 1096 " %cmp3 = icmp sgt i32 %N, 0 " 1097 " br i1 %cmp3, label %for.body, label %for.cond.cleanup " 1098 "for.cond.cleanup: " 1099 " ret void " 1100 "for.body: " 1101 " %i.04 = phi i32 [ %inc, %for.body ], [ 100, %entry ] " 1102 " %inc = call i32 @llvm.loop.decrement.reg.i32.i32.i32(i32 %i.04, i32 1) " 1103 " %exitcond = icmp ne i32 %inc, 0 " 1104 " br i1 %exitcond, label %for.cond.cleanup, label %for.body " 1105 "} " 1106 "declare i32 @llvm.loop.decrement.reg.i32.i32.i32(i32, i32) ", 1107 Err, C); 1108 1109 ASSERT_TRUE(M && "Could not parse module?"); 1110 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1111 1112 runWithSE(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1113 const SCEV *ScevInc = SE.getSCEV(getInstructionByName(F, "inc")); 1114 EXPECT_TRUE(isa<SCEVAddRecExpr>(ScevInc)); 1115 }); 1116 } 1117 1118 TEST_F(ScalarEvolutionsTest, SCEVComputeConstantDifference) { 1119 LLVMContext C; 1120 SMDiagnostic Err; 1121 std::unique_ptr<Module> M = parseAssemblyString( 1122 R"(define void @foo(ptr %ptr, i32 %sz, i32 %pp, i32 %x) { 1123 entry: 1124 %v0 = add i32 %pp, 0 1125 %v3 = add i32 %pp, 3 1126 %vx = add i32 %pp, %x 1127 %vx3 = add i32 %vx, 3 1128 br label %loop.body 1129 loop.body: 1130 %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] 1131 %xa = add nsw i32 %iv, %v0 1132 %yy = add nsw i32 %iv, %v3 1133 %xb = sub nsw i32 %yy, 3 1134 %iv.next = add nsw i32 %iv, 1 1135 %cmp = icmp sle i32 %iv.next, %sz 1136 br i1 %cmp, label %loop.body, label %loop2.body 1137 loop2.body: 1138 %iv2 = phi i32 [ %iv2.next, %loop2.body ], [ %iv, %loop.body ] 1139 %iv2.next = add nsw i32 %iv2, 1 1140 %iv2p3 = add i32 %iv2, 3 1141 %var = load i32, ptr %ptr 1142 %iv2pvar = add i32 %iv2, %var 1143 %iv2pvarp3 = add i32 %iv2pvar, 3 1144 %iv2pvarm3 = mul i32 %iv2pvar, 3 1145 %iv2pvarp3m3 = mul i32 %iv2pvarp3, 3 1146 %cmp2 = icmp sle i32 %iv2.next, %sz 1147 br i1 %cmp2, label %loop2.body, label %exit 1148 exit: 1149 ret void 1150 })", 1151 Err, C); 1152 1153 if (!M) { 1154 Err.print("ScalarEvolutionTest", errs()); 1155 ASSERT_TRUE(M && "Could not parse module?"); 1156 } 1157 ASSERT_TRUE(!verifyModule(*M, &errs()) && "Must have been well formed!"); 1158 1159 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1160 const SCEV *ScevV0 = SE.getSCEV(getInstructionByName(F, "v0")); // %pp 1161 const SCEV *ScevV3 = SE.getSCEV(getInstructionByName(F, "v3")); // (3 + %pp) 1162 const SCEV *ScevVX = 1163 SE.getSCEV(getInstructionByName(F, "vx")); // (%pp + %x) 1164 // (%pp + %x + 3) 1165 const SCEV *ScevVX3 = SE.getSCEV(getInstructionByName(F, "vx3")); 1166 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1167 const SCEV *ScevXA = SE.getSCEV(getInstructionByName(F, "xa")); // {%pp,+,1} 1168 const SCEV *ScevYY = 1169 SE.getSCEV(getInstructionByName(F, "yy")); // {(3 + %pp),+,1} 1170 const SCEV *ScevXB = SE.getSCEV(getInstructionByName(F, "xb")); // {%pp,+,1} 1171 const SCEV *ScevIVNext = 1172 SE.getSCEV(getInstructionByName(F, "iv.next")); // {1,+,1} 1173 // {{0,+,1},+,1} 1174 const SCEV *ScevIV2 = SE.getSCEV(getInstructionByName(F, "iv2")); 1175 // {{3,+,1},+,1} 1176 const SCEV *ScevIV2P3 = SE.getSCEV(getInstructionByName(F, "iv2p3")); 1177 // %var + {{0,+,1},+,1} 1178 const SCEV *ScevIV2PVar = SE.getSCEV(getInstructionByName(F, "iv2pvar")); 1179 // %var + {{3,+,1},+,1} 1180 const SCEV *ScevIV2PVarP3 = 1181 SE.getSCEV(getInstructionByName(F, "iv2pvarp3")); 1182 // 3 * (%var + {{0,+,1},+,1}) 1183 const SCEV *ScevIV2PVarM3 = 1184 SE.getSCEV(getInstructionByName(F, "iv2pvarm3")); 1185 // 3 * (%var + {{3,+,1},+,1}) 1186 const SCEV *ScevIV2PVarP3M3 = 1187 SE.getSCEV(getInstructionByName(F, "iv2pvarp3m3")); 1188 1189 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> std::optional<int> { 1190 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS); 1191 if (!ConstantDiffOrNone) 1192 return std::nullopt; 1193 1194 auto ExtDiff = ConstantDiffOrNone->getSExtValue(); 1195 int Diff = ExtDiff; 1196 assert(Diff == ExtDiff && "Integer overflow"); 1197 return Diff; 1198 }; 1199 1200 EXPECT_EQ(diff(ScevV3, ScevV0), 3); 1201 EXPECT_EQ(diff(ScevV0, ScevV3), -3); 1202 EXPECT_EQ(diff(ScevV0, ScevV0), 0); 1203 EXPECT_EQ(diff(ScevV3, ScevV3), 0); 1204 EXPECT_EQ(diff(ScevVX3, ScevVX), 3); 1205 EXPECT_EQ(diff(ScevIV, ScevIV), 0); 1206 EXPECT_EQ(diff(ScevXA, ScevXB), 0); 1207 EXPECT_EQ(diff(ScevXA, ScevYY), -3); 1208 EXPECT_EQ(diff(ScevYY, ScevXB), 3); 1209 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1); 1210 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1); 1211 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0); 1212 EXPECT_EQ(diff(ScevIV2P3, ScevIV2), 3); 1213 EXPECT_EQ(diff(ScevIV2PVar, ScevIV2PVarP3), -3); 1214 EXPECT_EQ(diff(ScevIV2PVarP3M3, ScevIV2PVarM3), 9); 1215 EXPECT_EQ(diff(ScevV0, ScevIV), std::nullopt); 1216 EXPECT_EQ(diff(ScevIVNext, ScevV3), std::nullopt); 1217 EXPECT_EQ(diff(ScevYY, ScevV3), std::nullopt); 1218 }); 1219 } 1220 1221 TEST_F(ScalarEvolutionsTest, SCEVrewriteUnknowns) { 1222 LLVMContext C; 1223 SMDiagnostic Err; 1224 std::unique_ptr<Module> M = parseAssemblyString( 1225 "define void @foo(i32 %i) { " 1226 "entry: " 1227 " %cmp3 = icmp ult i32 %i, 16 " 1228 " br i1 %cmp3, label %loop.body, label %exit " 1229 "loop.body: " 1230 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] " 1231 " %iv.next = add nsw i32 %iv, 1 " 1232 " %cmp = icmp eq i32 %iv.next, 16 " 1233 " br i1 %cmp, label %exit, label %loop.body " 1234 "exit: " 1235 " ret void " 1236 "} ", 1237 Err, C); 1238 1239 ASSERT_TRUE(M && "Could not parse module?"); 1240 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1241 1242 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1243 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1244 const SCEV *ScevI = SE.getSCEV(getArgByName(F, "i")); // {0,+,1} 1245 1246 ValueToSCEVMapTy RewriteMap; 1247 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] = 1248 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)); 1249 const SCEV *WithUMin = 1250 SCEVParameterRewriter::rewrite(ScevIV, SE, RewriteMap); 1251 1252 EXPECT_NE(WithUMin, ScevIV); 1253 const auto *AR = dyn_cast<SCEVAddRecExpr>(WithUMin); 1254 EXPECT_TRUE(AR); 1255 EXPECT_EQ(AR->getStart(), 1256 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17))); 1257 EXPECT_EQ(AR->getStepRecurrence(SE), 1258 cast<SCEVAddRecExpr>(ScevIV)->getStepRecurrence(SE)); 1259 }); 1260 } 1261 1262 TEST_F(ScalarEvolutionsTest, SCEVAddNUW) { 1263 LLVMContext C; 1264 SMDiagnostic Err; 1265 std::unique_ptr<Module> M = parseAssemblyString("define void @foo(i32 %x) { " 1266 " ret void " 1267 "} ", 1268 Err, C); 1269 1270 ASSERT_TRUE(M && "Could not parse module?"); 1271 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1272 1273 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1274 const SCEV *X = SE.getSCEV(getArgByName(F, "x")); 1275 const SCEV *One = SE.getOne(X->getType()); 1276 const SCEV *Sum = SE.getAddExpr(X, One, SCEV::FlagNUW); 1277 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGE, Sum, X)); 1278 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGT, Sum, X)); 1279 }); 1280 } 1281 1282 TEST_F(ScalarEvolutionsTest, SCEVgetRanges) { 1283 LLVMContext C; 1284 SMDiagnostic Err; 1285 std::unique_ptr<Module> M = parseAssemblyString( 1286 "define void @foo(i32 %i) { " 1287 "entry: " 1288 " br label %loop.body " 1289 "loop.body: " 1290 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] " 1291 " %iv.next = add nsw i32 %iv, 1 " 1292 " %cmp = icmp eq i32 %iv.next, 16 " 1293 " br i1 %cmp, label %exit, label %loop.body " 1294 "exit: " 1295 " ret void " 1296 "} ", 1297 Err, C); 1298 1299 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1300 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1301 const SCEV *ScevI = SE.getSCEV(getArgByName(F, "i")); 1302 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getLower(), 0); 1303 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getUpper(), 16); 1304 1305 const SCEV *Add = SE.getAddExpr(ScevI, ScevIV); 1306 ValueToSCEVMapTy RewriteMap; 1307 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] = 1308 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)); 1309 const SCEV *AddWithUMin = 1310 SCEVParameterRewriter::rewrite(Add, SE, RewriteMap); 1311 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getLower(), 0); 1312 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getUpper(), 33); 1313 }); 1314 } 1315 1316 TEST_F(ScalarEvolutionsTest, SCEVgetExitLimitForGuardedLoop) { 1317 LLVMContext C; 1318 SMDiagnostic Err; 1319 std::unique_ptr<Module> M = parseAssemblyString( 1320 "define void @foo(i32 %i) { " 1321 "entry: " 1322 " %cmp3 = icmp ult i32 %i, 16 " 1323 " br i1 %cmp3, label %loop.body, label %exit " 1324 "loop.body: " 1325 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] " 1326 " %iv.next = add nsw i32 %iv, 1 " 1327 " %cmp = icmp eq i32 %iv.next, 16 " 1328 " br i1 %cmp, label %exit, label %loop.body " 1329 "exit: " 1330 " ret void " 1331 "} ", 1332 Err, C); 1333 1334 ASSERT_TRUE(M && "Could not parse module?"); 1335 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1336 1337 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1338 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1339 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop(); 1340 1341 const SCEV *BTC = SE.getBackedgeTakenCount(L); 1342 EXPECT_FALSE(isa<SCEVConstant>(BTC)); 1343 const SCEV *MaxBTC = SE.getConstantMaxBackedgeTakenCount(L); 1344 EXPECT_EQ(cast<SCEVConstant>(MaxBTC)->getAPInt(), 15); 1345 }); 1346 } 1347 1348 TEST_F(ScalarEvolutionsTest, ImpliedViaAddRecStart) { 1349 LLVMContext C; 1350 SMDiagnostic Err; 1351 std::unique_ptr<Module> M = parseAssemblyString( 1352 "define void @foo(i32* %p) { " 1353 "entry: " 1354 " %x = load i32, i32* %p, !range !0 " 1355 " br label %loop " 1356 "loop: " 1357 " %iv = phi i32 [ %x, %entry], [%iv.next, %backedge] " 1358 " %ne.check = icmp ne i32 %iv, 0 " 1359 " br i1 %ne.check, label %backedge, label %exit " 1360 "backedge: " 1361 " %iv.next = add i32 %iv, -1 " 1362 " br label %loop " 1363 "exit:" 1364 " ret void " 1365 "} " 1366 "!0 = !{i32 0, i32 2147483647}", 1367 Err, C); 1368 1369 ASSERT_TRUE(M && "Could not parse module?"); 1370 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1371 1372 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1373 const SCEV *X = SE.getSCEV(getInstructionByName(F, "x")); 1374 auto *Context = getInstructionByName(F, "iv.next"); 1375 EXPECT_TRUE(SE.isKnownPredicateAt(ICmpInst::ICMP_NE, X, 1376 SE.getZero(X->getType()), Context)); 1377 }); 1378 } 1379 1380 TEST_F(ScalarEvolutionsTest, UnsignedIsImpliedViaOperations) { 1381 LLVMContext C; 1382 SMDiagnostic Err; 1383 std::unique_ptr<Module> M = 1384 parseAssemblyString("define void @foo(i32* %p1, i32* %p2) { " 1385 "entry: " 1386 " %x = load i32, i32* %p1, !range !0 " 1387 " %cond = icmp ne i32 %x, 0 " 1388 " br i1 %cond, label %guarded, label %exit " 1389 "guarded: " 1390 " %y = add i32 %x, -1 " 1391 " ret void " 1392 "exit: " 1393 " ret void " 1394 "} " 1395 "!0 = !{i32 0, i32 2147483647}", 1396 Err, C); 1397 1398 ASSERT_TRUE(M && "Could not parse module?"); 1399 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1400 1401 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1402 const SCEV *X = SE.getSCEV(getInstructionByName(F, "x")); 1403 const SCEV *Y = SE.getSCEV(getInstructionByName(F, "y")); 1404 auto *Guarded = getInstructionByName(F, "y")->getParent(); 1405 ASSERT_TRUE(Guarded); 1406 EXPECT_TRUE( 1407 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_ULT, Y, X)); 1408 EXPECT_TRUE( 1409 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_UGT, X, Y)); 1410 }); 1411 } 1412 1413 TEST_F(ScalarEvolutionsTest, ProveImplicationViaNarrowing) { 1414 LLVMContext C; 1415 SMDiagnostic Err; 1416 std::unique_ptr<Module> M = parseAssemblyString( 1417 "define i32 @foo(i32 %start, i32* %q) { " 1418 "entry: " 1419 " %wide.start = zext i32 %start to i64 " 1420 " br label %loop " 1421 "loop: " 1422 " %wide.iv = phi i64 [%wide.start, %entry], [%wide.iv.next, %backedge] " 1423 " %iv = phi i32 [%start, %entry], [%iv.next, %backedge] " 1424 " %cond = icmp eq i64 %wide.iv, 0 " 1425 " br i1 %cond, label %exit, label %backedge " 1426 "backedge: " 1427 " %iv.next = add i32 %iv, -1 " 1428 " %index = zext i32 %iv.next to i64 " 1429 " %load.addr = getelementptr i32, i32* %q, i64 %index " 1430 " %stop = load i32, i32* %load.addr " 1431 " %loop.cond = icmp eq i32 %stop, 0 " 1432 " %wide.iv.next = add nsw i64 %wide.iv, -1 " 1433 " br i1 %loop.cond, label %loop, label %failure " 1434 "exit: " 1435 " ret i32 0 " 1436 "failure: " 1437 " unreachable " 1438 "} ", 1439 Err, C); 1440 1441 ASSERT_TRUE(M && "Could not parse module?"); 1442 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1443 1444 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1445 const SCEV *IV = SE.getSCEV(getInstructionByName(F, "iv")); 1446 const SCEV *Zero = SE.getZero(IV->getType()); 1447 auto *Backedge = getInstructionByName(F, "iv.next")->getParent(); 1448 ASSERT_TRUE(Backedge); 1449 (void)IV; 1450 (void)Zero; 1451 // FIXME: This can only be proved with turned on option 1452 // scalar-evolution-use-expensive-range-sharpening which is currently off. 1453 // Enable the check once it's switched true by default. 1454 // EXPECT_TRUE(SE.isBasicBlockEntryGuardedByCond(Backedge, 1455 // ICmpInst::ICMP_UGT, 1456 // IV, Zero)); 1457 }); 1458 } 1459 1460 TEST_F(ScalarEvolutionsTest, ImpliedCond) { 1461 LLVMContext C; 1462 SMDiagnostic Err; 1463 std::unique_ptr<Module> M = parseAssemblyString( 1464 "define void @foo(i32 %len) { " 1465 "entry: " 1466 " br label %loop " 1467 "loop: " 1468 " %iv = phi i32 [ 0, %entry], [%iv.next, %loop] " 1469 " %iv.next = add nsw i32 %iv, 1 " 1470 " %cmp = icmp slt i32 %iv, %len " 1471 " br i1 %cmp, label %loop, label %exit " 1472 "exit:" 1473 " ret void " 1474 "}", 1475 Err, C); 1476 1477 ASSERT_TRUE(M && "Could not parse module?"); 1478 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1479 1480 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1481 Instruction *IV = getInstructionByName(F, "iv"); 1482 Type *Ty = IV->getType(); 1483 const SCEV *Zero = SE.getZero(Ty); 1484 const SCEV *MinusOne = SE.getMinusOne(Ty); 1485 // {0,+,1}<nuw><nsw> 1486 const SCEV *AddRec_0_1 = SE.getSCEV(IV); 1487 // {0,+,-1}<nw> 1488 const SCEV *AddRec_0_N1 = SE.getNegativeSCEV(AddRec_0_1); 1489 1490 // {0,+,1}<nuw><nsw> > 0 -> {0,+,-1}<nw> < 0 1491 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SLT, AddRec_0_N1, Zero, 1492 ICmpInst::ICMP_SGT, AddRec_0_1, Zero)); 1493 // {0,+,-1}<nw> < -1 -> {0,+,1}<nuw><nsw> > 0 1494 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SGT, AddRec_0_1, Zero, 1495 ICmpInst::ICMP_SLT, AddRec_0_N1, MinusOne)); 1496 }); 1497 } 1498 1499 TEST_F(ScalarEvolutionsTest, MatchURem) { 1500 LLVMContext C; 1501 SMDiagnostic Err; 1502 std::unique_ptr<Module> M = parseAssemblyString( 1503 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" " 1504 " " 1505 "define void @test(i32 %a, i32 %b, i16 %c, i64 %d) {" 1506 "entry: " 1507 " %rem1 = urem i32 %a, 2" 1508 " %rem2 = urem i32 %a, 5" 1509 " %rem3 = urem i32 %a, %b" 1510 " %c.ext = zext i16 %c to i32" 1511 " %rem4 = urem i32 %c.ext, 2" 1512 " %ext = zext i32 %rem4 to i64" 1513 " %rem5 = urem i64 %d, 17179869184" 1514 " ret void " 1515 "} ", 1516 Err, C); 1517 1518 assert(M && "Could not parse module?"); 1519 assert(!verifyModule(*M) && "Must have been well formed!"); 1520 1521 runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1522 for (auto *N : {"rem1", "rem2", "rem3", "rem5"}) { 1523 auto *URemI = getInstructionByName(F, N); 1524 auto *S = SE.getSCEV(URemI); 1525 const SCEV *LHS, *RHS; 1526 EXPECT_TRUE(matchURem(SE, S, LHS, RHS)); 1527 EXPECT_EQ(LHS, SE.getSCEV(URemI->getOperand(0))); 1528 EXPECT_EQ(RHS, SE.getSCEV(URemI->getOperand(1))); 1529 EXPECT_EQ(LHS->getType(), S->getType()); 1530 EXPECT_EQ(RHS->getType(), S->getType()); 1531 } 1532 1533 // Check the case where the urem operand is zero-extended. Make sure the 1534 // match results are extended to the size of the input expression. 1535 auto *Ext = getInstructionByName(F, "ext"); 1536 auto *URem1 = getInstructionByName(F, "rem4"); 1537 auto *S = SE.getSCEV(Ext); 1538 const SCEV *LHS, *RHS; 1539 EXPECT_TRUE(matchURem(SE, S, LHS, RHS)); 1540 EXPECT_NE(LHS, SE.getSCEV(URem1->getOperand(0))); 1541 // RHS and URem1->getOperand(1) have different widths, so compare the 1542 // integer values. 1543 EXPECT_EQ(cast<SCEVConstant>(RHS)->getValue()->getZExtValue(), 1544 cast<SCEVConstant>(SE.getSCEV(URem1->getOperand(1))) 1545 ->getValue() 1546 ->getZExtValue()); 1547 EXPECT_EQ(LHS->getType(), S->getType()); 1548 EXPECT_EQ(RHS->getType(), S->getType()); 1549 }); 1550 } 1551 1552 TEST_F(ScalarEvolutionsTest, SCEVUDivFloorCeiling) { 1553 LLVMContext C; 1554 SMDiagnostic Err; 1555 std::unique_ptr<Module> M = parseAssemblyString("define void @foo() { " 1556 " ret void " 1557 "} ", 1558 Err, C); 1559 1560 ASSERT_TRUE(M && "Could not parse module?"); 1561 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1562 1563 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1564 // Check that SCEV's udiv and uceil handling produce the correct results 1565 // for all 8 bit options. Div-by-zero is deliberately excluded. 1566 for (unsigned N = 0; N < 256; N++) 1567 for (unsigned D = 1; D < 256; D++) { 1568 APInt NInt(8, N); 1569 APInt DInt(8, D); 1570 using namespace llvm::APIntOps; 1571 APInt FloorInt = RoundingUDiv(NInt, DInt, APInt::Rounding::DOWN); 1572 APInt CeilingInt = RoundingUDiv(NInt, DInt, APInt::Rounding::UP); 1573 const SCEV *NS = SE.getConstant(NInt); 1574 const SCEV *DS = SE.getConstant(DInt); 1575 auto *FloorS = cast<SCEVConstant>(SE.getUDivExpr(NS, DS)); 1576 auto *CeilingS = cast<SCEVConstant>(SE.getUDivCeilSCEV(NS, DS)); 1577 ASSERT_TRUE(FloorS->getAPInt() == FloorInt); 1578 ASSERT_TRUE(CeilingS->getAPInt() == CeilingInt); 1579 } 1580 }); 1581 } 1582 1583 TEST_F(ScalarEvolutionsTest, CheckGetPowerOfTwo) { 1584 Module M("CheckGetPowerOfTwo", Context); 1585 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false); 1586 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M); 1587 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1588 IRBuilder<> Builder(Entry); 1589 Builder.CreateRetVoid(); 1590 ScalarEvolution SE = buildSE(*F); 1591 1592 for (unsigned short i = 0; i < 64; ++i) 1593 EXPECT_TRUE( 1594 dyn_cast<SCEVConstant>(SE.getPowerOfTwo(Type::getInt64Ty(Context), i)) 1595 ->getValue() 1596 ->equalsInt(1ULL << i)); 1597 } 1598 1599 TEST_F(ScalarEvolutionsTest, ApplyLoopGuards) { 1600 LLVMContext C; 1601 SMDiagnostic Err; 1602 std::unique_ptr<Module> M = parseAssemblyString( 1603 "declare void @llvm.assume(i1)\n" 1604 "define void @test(i32 %num) {\n" 1605 "entry:\n" 1606 " %u = urem i32 %num, 4\n" 1607 " %cmp = icmp eq i32 %u, 0\n" 1608 " tail call void @llvm.assume(i1 %cmp)\n" 1609 " %cmp.1 = icmp ugt i32 %num, 0\n" 1610 " tail call void @llvm.assume(i1 %cmp.1)\n" 1611 " br label %for.body\n" 1612 "for.body:\n" 1613 " %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n" 1614 " %inc = add nuw nsw i32 %i.010, 1\n" 1615 " %cmp2 = icmp ult i32 %inc, %num\n" 1616 " br i1 %cmp2, label %for.body, label %exit\n" 1617 "exit:\n" 1618 " ret void\n" 1619 "}\n", 1620 Err, C); 1621 1622 ASSERT_TRUE(M && "Could not parse module?"); 1623 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1624 1625 runWithSE(*M, "test", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1626 const SCEV *TCScev = SE.getSCEV(getArgByName(F, "num")); 1627 const SCEV *ApplyLoopGuardsTC = SE.applyLoopGuards(TCScev, *LI.begin()); 1628 // Assert that the new TC is (4 * ((4 umax %num) /u 4)) 1629 APInt Four(32, 4); 1630 const SCEV *Constant4 = SE.getConstant(Four); 1631 const SCEV *Max = SE.getUMaxExpr(TCScev, Constant4); 1632 const SCEV *Mul = SE.getMulExpr(SE.getUDivExpr(Max, Constant4), Constant4); 1633 ASSERT_TRUE(Mul == ApplyLoopGuardsTC); 1634 }); 1635 } 1636 1637 TEST_F(ScalarEvolutionsTest, ForgetValueWithOverflowInst) { 1638 LLVMContext C; 1639 SMDiagnostic Err; 1640 std::unique_ptr<Module> M = parseAssemblyString( 1641 "declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) " 1642 "define void @foo(i32 %i) { " 1643 "entry: " 1644 " br label %loop.body " 1645 "loop.body: " 1646 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] " 1647 " %iv.next = add nsw i32 %iv, 1 " 1648 " %call = call {i32, i1} @llvm.smul.with.overflow.i32(i32 %iv, i32 -2) " 1649 " %extractvalue = extractvalue {i32, i1} %call, 0 " 1650 " %cmp = icmp eq i32 %iv.next, 16 " 1651 " br i1 %cmp, label %exit, label %loop.body " 1652 "exit: " 1653 " ret void " 1654 "} ", 1655 Err, C); 1656 1657 ASSERT_TRUE(M && "Could not parse module?"); 1658 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1659 1660 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1661 auto *ExtractValue = getInstructionByName(F, "extractvalue"); 1662 auto *IV = getInstructionByName(F, "iv"); 1663 1664 auto *ExtractValueScev = SE.getSCEV(ExtractValue); 1665 EXPECT_NE(ExtractValueScev, nullptr); 1666 1667 SE.forgetValue(IV); 1668 auto *ExtractValueScevForgotten = SE.getExistingSCEV(ExtractValue); 1669 EXPECT_EQ(ExtractValueScevForgotten, nullptr); 1670 }); 1671 } 1672 1673 TEST_F(ScalarEvolutionsTest, ComplexityComparatorIsStrictWeakOrdering) { 1674 // Regression test for a case where caching of equivalent values caused the 1675 // comparator to get inconsistent. 1676 LLVMContext C; 1677 SMDiagnostic Err; 1678 std::unique_ptr<Module> M = parseAssemblyString(R"( 1679 define i32 @foo(i32 %arg0) { 1680 %1 = add i32 %arg0, 1 1681 %2 = add i32 %arg0, 1 1682 %3 = xor i32 %2, %1 1683 %4 = add i32 %3, %2 1684 %5 = add i32 %arg0, 1 1685 %6 = xor i32 %5, %arg0 1686 %7 = add i32 %arg0, %6 1687 %8 = add i32 %5, %7 1688 %9 = xor i32 %8, %7 1689 %10 = add i32 %9, %8 1690 %11 = xor i32 %10, %9 1691 %12 = add i32 %11, %10 1692 %13 = xor i32 %12, %11 1693 %14 = add i32 %12, %13 1694 %15 = add i32 %14, %4 1695 ret i32 %15 1696 })", 1697 Err, C); 1698 1699 ASSERT_TRUE(M && "Could not parse module?"); 1700 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1701 1702 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1703 // When _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG, this will 1704 // crash if the comparator has the specific caching bug. 1705 SE.getSCEV(F.getEntryBlock().getTerminator()->getOperand(0)); 1706 }); 1707 } 1708 1709 } // end namespace llvm 1710