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 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(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 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 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 const SCEV *Five = SE.getConstant(APInt(/*numBits=*/64, 5)); 784 const SCEV *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 = 934 PHINode::Create(Type::getInt64Ty(Context), 2, "", Br->getIterator()); 935 auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br->getIterator()); 936 auto *AShr = 937 BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br->getIterator()); 938 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br->getIterator()); 939 Phi->addIncoming(MinInt64, EntryBB); 940 Phi->addIncoming(Add, LoopBB); 941 // exit: 942 ReturnInst::Create(Context, nullptr, ExitBB); 943 944 // Make sure that SCEV doesn't blow up 945 ScalarEvolution SE = buildSE(*F); 946 const SCEV *Expr = SE.getSCEV(Phi); 947 EXPECT_NE(nullptr, Expr); 948 EXPECT_TRUE(isa<SCEVUnknown>(Expr)); 949 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr)); 950 } 951 952 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstantAccum) { 953 // Make sure that SCEV does not blow up when constructing an AddRec 954 // with predicates for a phi with the update pattern: 955 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum 956 // when the InvariantAccum is a constant that is too large to fit in an 957 // ix but are zero when truncated to ix, and the initial value of the 958 // phi is not a constant. 959 Type *Int32Ty = Type::getInt32Ty(Context); 960 SmallVector<Type *, 1> Types; 961 Types.push_back(Int32Ty); 962 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 963 Function *F = 964 Function::Create(FTy, Function::ExternalLinkage, "addrecphitest", M); 965 966 /* 967 Create IR: 968 define @addrecphitest(i32) 969 entry: 970 br label %loop 971 loop: 972 %1 = phi i32 [%0, %entry], [%4, %loop] 973 %2 = shl i32 %1, 16 974 %3 = ashr exact i32 %2, 16 975 %4 = add i32 %3, -2147483648 976 br i1 undef, label %exit, label %loop 977 exit: 978 ret void 979 */ 980 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 981 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 982 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 983 984 // entry: 985 BranchInst::Create(LoopBB, EntryBB); 986 // loop: 987 auto *MinInt32 = ConstantInt::get(Context, APInt(32, 0x80000000U)); 988 auto *Int32_16 = ConstantInt::get(Context, APInt(32, 16)); 989 auto *Br = BranchInst::Create( 990 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB); 991 auto *Phi = PHINode::Create(Int32Ty, 2, "", Br->getIterator()); 992 auto *Shl = BinaryOperator::CreateShl(Phi, Int32_16, "", Br->getIterator()); 993 auto *AShr = 994 BinaryOperator::CreateExactAShr(Shl, Int32_16, "", Br->getIterator()); 995 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt32, "", Br->getIterator()); 996 auto *Arg = &*(F->arg_begin()); 997 Phi->addIncoming(Arg, EntryBB); 998 Phi->addIncoming(Add, LoopBB); 999 // exit: 1000 ReturnInst::Create(Context, nullptr, ExitBB); 1001 1002 // Make sure that SCEV doesn't blow up 1003 ScalarEvolution SE = buildSE(*F); 1004 const SCEV *Expr = SE.getSCEV(Phi); 1005 EXPECT_NE(nullptr, Expr); 1006 EXPECT_TRUE(isa<SCEVUnknown>(Expr)); 1007 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr)); 1008 } 1009 1010 TEST_F(ScalarEvolutionsTest, SCEVFoldSumOfTruncs) { 1011 // Verify that the following SCEV gets folded to a zero: 1012 // (-1 * (trunc i64 (-1 * %0) to i32)) + (-1 * (trunc i64 %0 to i32) 1013 Type *ArgTy = Type::getInt64Ty(Context); 1014 Type *Int32Ty = Type::getInt32Ty(Context); 1015 SmallVector<Type *, 1> Types; 1016 Types.push_back(ArgTy); 1017 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 1018 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M); 1019 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 1020 ReturnInst::Create(Context, nullptr, BB); 1021 1022 ScalarEvolution SE = buildSE(*F); 1023 1024 auto *Arg = &*(F->arg_begin()); 1025 const SCEV *ArgSCEV = SE.getSCEV(Arg); 1026 1027 // Build the SCEV 1028 const SCEV *A0 = SE.getNegativeSCEV(ArgSCEV); 1029 const SCEV *A1 = SE.getTruncateExpr(A0, Int32Ty); 1030 const SCEV *A = SE.getNegativeSCEV(A1); 1031 1032 const SCEV *B0 = SE.getTruncateExpr(ArgSCEV, Int32Ty); 1033 const SCEV *B = SE.getNegativeSCEV(B0); 1034 1035 const SCEV *Expr = SE.getAddExpr(A, B); 1036 // Verify that the SCEV was folded to 0 1037 const SCEV *ZeroConst = SE.getConstant(Int32Ty, 0); 1038 EXPECT_EQ(Expr, ZeroConst); 1039 } 1040 1041 // Check logic of SCEV expression size computation. 1042 TEST_F(ScalarEvolutionsTest, SCEVComputeExpressionSize) { 1043 /* 1044 * Create the following code: 1045 * void func(i64 %a, i64 %b) 1046 * entry: 1047 * %s1 = add i64 %a, 1 1048 * %s2 = udiv i64 %s1, %b 1049 * br label %exit 1050 * exit: 1051 * ret 1052 */ 1053 1054 // Create a module. 1055 Module M("SCEVComputeExpressionSize", Context); 1056 1057 Type *T_int64 = Type::getInt64Ty(Context); 1058 1059 FunctionType *FTy = 1060 FunctionType::get(Type::getVoidTy(Context), { T_int64, T_int64 }, false); 1061 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M); 1062 Argument *A = &*F->arg_begin(); 1063 Argument *B = &*std::next(F->arg_begin()); 1064 ConstantInt *C = ConstantInt::get(Context, APInt(64, 1)); 1065 1066 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1067 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F); 1068 1069 IRBuilder<> Builder(Entry); 1070 auto *S1 = cast<Instruction>(Builder.CreateAdd(A, C, "s1")); 1071 auto *S2 = cast<Instruction>(Builder.CreateUDiv(S1, B, "s2")); 1072 Builder.CreateBr(Exit); 1073 1074 Builder.SetInsertPoint(Exit); 1075 Builder.CreateRetVoid(); 1076 1077 ScalarEvolution SE = buildSE(*F); 1078 // Get S2 first to move it to cache. 1079 const SCEV *AS = SE.getSCEV(A); 1080 const SCEV *BS = SE.getSCEV(B); 1081 const SCEV *CS = SE.getSCEV(C); 1082 const SCEV *S1S = SE.getSCEV(S1); 1083 const SCEV *S2S = SE.getSCEV(S2); 1084 EXPECT_EQ(AS->getExpressionSize(), 1u); 1085 EXPECT_EQ(BS->getExpressionSize(), 1u); 1086 EXPECT_EQ(CS->getExpressionSize(), 1u); 1087 EXPECT_EQ(S1S->getExpressionSize(), 3u); 1088 EXPECT_EQ(S2S->getExpressionSize(), 5u); 1089 } 1090 1091 TEST_F(ScalarEvolutionsTest, SCEVLoopDecIntrinsic) { 1092 LLVMContext C; 1093 SMDiagnostic Err; 1094 std::unique_ptr<Module> M = parseAssemblyString( 1095 "define void @foo(i32 %N) { " 1096 "entry: " 1097 " %cmp3 = icmp sgt i32 %N, 0 " 1098 " br i1 %cmp3, label %for.body, label %for.cond.cleanup " 1099 "for.cond.cleanup: " 1100 " ret void " 1101 "for.body: " 1102 " %i.04 = phi i32 [ %inc, %for.body ], [ 100, %entry ] " 1103 " %inc = call i32 @llvm.loop.decrement.reg.i32.i32.i32(i32 %i.04, i32 1) " 1104 " %exitcond = icmp ne i32 %inc, 0 " 1105 " br i1 %exitcond, label %for.cond.cleanup, label %for.body " 1106 "} " 1107 "declare i32 @llvm.loop.decrement.reg.i32.i32.i32(i32, i32) ", 1108 Err, C); 1109 1110 ASSERT_TRUE(M && "Could not parse module?"); 1111 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1112 1113 runWithSE(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1114 const SCEV *ScevInc = SE.getSCEV(getInstructionByName(F, "inc")); 1115 EXPECT_TRUE(isa<SCEVAddRecExpr>(ScevInc)); 1116 }); 1117 } 1118 1119 TEST_F(ScalarEvolutionsTest, SCEVComputeConstantDifference) { 1120 LLVMContext C; 1121 SMDiagnostic Err; 1122 std::unique_ptr<Module> M = parseAssemblyString( 1123 R"(define void @foo(ptr %ptr, i32 %sz, i32 %pp, i32 %x) { 1124 entry: 1125 %v0 = add i32 %pp, 0 1126 %v3 = add i32 %pp, 3 1127 %vx = add i32 %pp, %x 1128 %vx3 = add i32 %vx, 3 1129 br label %loop.body 1130 loop.body: 1131 %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] 1132 %xa = add nsw i32 %iv, %v0 1133 %yy = add nsw i32 %iv, %v3 1134 %xb = sub nsw i32 %yy, 3 1135 %iv.next = add nsw i32 %iv, 1 1136 %cmp = icmp sle i32 %iv.next, %sz 1137 br i1 %cmp, label %loop.body, label %loop2.body 1138 loop2.body: 1139 %iv2 = phi i32 [ %iv2.next, %loop2.body ], [ %iv, %loop.body ] 1140 %iv2.next = add nsw i32 %iv2, 1 1141 %iv2p3 = add i32 %iv2, 3 1142 %var = load i32, ptr %ptr 1143 %iv2pvar = add i32 %iv2, %var 1144 %iv2pvarp3 = add i32 %iv2pvar, 3 1145 %iv2pvarm3 = mul i32 %iv2pvar, 3 1146 %iv2pvarp3m3 = mul i32 %iv2pvarp3, 3 1147 %cmp2 = icmp sle i32 %iv2.next, %sz 1148 br i1 %cmp2, label %loop2.body, label %exit 1149 exit: 1150 ret void 1151 })", 1152 Err, C); 1153 1154 if (!M) { 1155 Err.print("ScalarEvolutionTest", errs()); 1156 ASSERT_TRUE(M && "Could not parse module?"); 1157 } 1158 ASSERT_TRUE(!verifyModule(*M, &errs()) && "Must have been well formed!"); 1159 1160 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1161 const SCEV *ScevV0 = SE.getSCEV(getInstructionByName(F, "v0")); // %pp 1162 const SCEV *ScevV3 = SE.getSCEV(getInstructionByName(F, "v3")); // (3 + %pp) 1163 const SCEV *ScevVX = 1164 SE.getSCEV(getInstructionByName(F, "vx")); // (%pp + %x) 1165 // (%pp + %x + 3) 1166 const SCEV *ScevVX3 = SE.getSCEV(getInstructionByName(F, "vx3")); 1167 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1168 const SCEV *ScevXA = SE.getSCEV(getInstructionByName(F, "xa")); // {%pp,+,1} 1169 const SCEV *ScevYY = 1170 SE.getSCEV(getInstructionByName(F, "yy")); // {(3 + %pp),+,1} 1171 const SCEV *ScevXB = SE.getSCEV(getInstructionByName(F, "xb")); // {%pp,+,1} 1172 const SCEV *ScevIVNext = 1173 SE.getSCEV(getInstructionByName(F, "iv.next")); // {1,+,1} 1174 // {{0,+,1},+,1} 1175 const SCEV *ScevIV2 = SE.getSCEV(getInstructionByName(F, "iv2")); 1176 // {{3,+,1},+,1} 1177 const SCEV *ScevIV2P3 = SE.getSCEV(getInstructionByName(F, "iv2p3")); 1178 // %var + {{0,+,1},+,1} 1179 const SCEV *ScevIV2PVar = SE.getSCEV(getInstructionByName(F, "iv2pvar")); 1180 // %var + {{3,+,1},+,1} 1181 const SCEV *ScevIV2PVarP3 = 1182 SE.getSCEV(getInstructionByName(F, "iv2pvarp3")); 1183 // 3 * (%var + {{0,+,1},+,1}) 1184 const SCEV *ScevIV2PVarM3 = 1185 SE.getSCEV(getInstructionByName(F, "iv2pvarm3")); 1186 // 3 * (%var + {{3,+,1},+,1}) 1187 const SCEV *ScevIV2PVarP3M3 = 1188 SE.getSCEV(getInstructionByName(F, "iv2pvarp3m3")); 1189 1190 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> std::optional<int> { 1191 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS); 1192 if (!ConstantDiffOrNone) 1193 return std::nullopt; 1194 1195 auto ExtDiff = ConstantDiffOrNone->getSExtValue(); 1196 int Diff = ExtDiff; 1197 assert(Diff == ExtDiff && "Integer overflow"); 1198 return Diff; 1199 }; 1200 1201 EXPECT_EQ(diff(ScevV3, ScevV0), 3); 1202 EXPECT_EQ(diff(ScevV0, ScevV3), -3); 1203 EXPECT_EQ(diff(ScevV0, ScevV0), 0); 1204 EXPECT_EQ(diff(ScevV3, ScevV3), 0); 1205 EXPECT_EQ(diff(ScevVX3, ScevVX), 3); 1206 EXPECT_EQ(diff(ScevIV, ScevIV), 0); 1207 EXPECT_EQ(diff(ScevXA, ScevXB), 0); 1208 EXPECT_EQ(diff(ScevXA, ScevYY), -3); 1209 EXPECT_EQ(diff(ScevYY, ScevXB), 3); 1210 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1); 1211 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1); 1212 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0); 1213 EXPECT_EQ(diff(ScevIV2P3, ScevIV2), 3); 1214 EXPECT_EQ(diff(ScevIV2PVar, ScevIV2PVarP3), -3); 1215 EXPECT_EQ(diff(ScevIV2PVarP3M3, ScevIV2PVarM3), 9); 1216 EXPECT_EQ(diff(ScevV0, ScevIV), std::nullopt); 1217 EXPECT_EQ(diff(ScevIVNext, ScevV3), std::nullopt); 1218 EXPECT_EQ(diff(ScevYY, ScevV3), std::nullopt); 1219 }); 1220 } 1221 1222 TEST_F(ScalarEvolutionsTest, SCEVrewriteUnknowns) { 1223 LLVMContext C; 1224 SMDiagnostic Err; 1225 std::unique_ptr<Module> M = parseAssemblyString( 1226 "define void @foo(i32 %i) { " 1227 "entry: " 1228 " %cmp3 = icmp ult i32 %i, 16 " 1229 " br i1 %cmp3, label %loop.body, label %exit " 1230 "loop.body: " 1231 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] " 1232 " %iv.next = add nsw i32 %iv, 1 " 1233 " %cmp = icmp eq i32 %iv.next, 16 " 1234 " br i1 %cmp, label %exit, label %loop.body " 1235 "exit: " 1236 " ret void " 1237 "} ", 1238 Err, C); 1239 1240 ASSERT_TRUE(M && "Could not parse module?"); 1241 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1242 1243 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1244 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1245 const SCEV *ScevI = SE.getSCEV(getArgByName(F, "i")); // {0,+,1} 1246 1247 ValueToSCEVMapTy RewriteMap; 1248 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] = 1249 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)); 1250 const SCEV *WithUMin = 1251 SCEVParameterRewriter::rewrite(ScevIV, SE, RewriteMap); 1252 1253 EXPECT_NE(WithUMin, ScevIV); 1254 const auto *AR = dyn_cast<SCEVAddRecExpr>(WithUMin); 1255 EXPECT_TRUE(AR); 1256 EXPECT_EQ(AR->getStart(), 1257 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17))); 1258 EXPECT_EQ(AR->getStepRecurrence(SE), 1259 cast<SCEVAddRecExpr>(ScevIV)->getStepRecurrence(SE)); 1260 }); 1261 } 1262 1263 TEST_F(ScalarEvolutionsTest, SCEVAddNUW) { 1264 LLVMContext C; 1265 SMDiagnostic Err; 1266 std::unique_ptr<Module> M = parseAssemblyString("define void @foo(i32 %x) { " 1267 " ret void " 1268 "} ", 1269 Err, C); 1270 1271 ASSERT_TRUE(M && "Could not parse module?"); 1272 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1273 1274 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1275 const SCEV *X = SE.getSCEV(getArgByName(F, "x")); 1276 const SCEV *One = SE.getOne(X->getType()); 1277 const SCEV *Sum = SE.getAddExpr(X, One, SCEV::FlagNUW); 1278 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGE, Sum, X)); 1279 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGT, Sum, X)); 1280 }); 1281 } 1282 1283 TEST_F(ScalarEvolutionsTest, SCEVgetRanges) { 1284 LLVMContext C; 1285 SMDiagnostic Err; 1286 std::unique_ptr<Module> M = parseAssemblyString( 1287 "define void @foo(i32 %i) { " 1288 "entry: " 1289 " br label %loop.body " 1290 "loop.body: " 1291 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] " 1292 " %iv.next = add nsw i32 %iv, 1 " 1293 " %cmp = icmp eq i32 %iv.next, 16 " 1294 " br i1 %cmp, label %exit, label %loop.body " 1295 "exit: " 1296 " ret void " 1297 "} ", 1298 Err, C); 1299 1300 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1301 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1302 const SCEV *ScevI = SE.getSCEV(getArgByName(F, "i")); 1303 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getLower(), 0); 1304 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getUpper(), 16); 1305 1306 const SCEV *Add = SE.getAddExpr(ScevI, ScevIV); 1307 ValueToSCEVMapTy RewriteMap; 1308 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] = 1309 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)); 1310 const SCEV *AddWithUMin = 1311 SCEVParameterRewriter::rewrite(Add, SE, RewriteMap); 1312 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getLower(), 0); 1313 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getUpper(), 33); 1314 }); 1315 } 1316 1317 TEST_F(ScalarEvolutionsTest, SCEVgetExitLimitForGuardedLoop) { 1318 LLVMContext C; 1319 SMDiagnostic Err; 1320 std::unique_ptr<Module> M = parseAssemblyString( 1321 "define void @foo(i32 %i) { " 1322 "entry: " 1323 " %cmp3 = icmp ult i32 %i, 16 " 1324 " br i1 %cmp3, label %loop.body, label %exit " 1325 "loop.body: " 1326 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] " 1327 " %iv.next = add nsw i32 %iv, 1 " 1328 " %cmp = icmp eq i32 %iv.next, 16 " 1329 " br i1 %cmp, label %exit, label %loop.body " 1330 "exit: " 1331 " ret void " 1332 "} ", 1333 Err, C); 1334 1335 ASSERT_TRUE(M && "Could not parse module?"); 1336 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1337 1338 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1339 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1} 1340 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop(); 1341 1342 const SCEV *BTC = SE.getBackedgeTakenCount(L); 1343 EXPECT_FALSE(isa<SCEVConstant>(BTC)); 1344 const SCEV *MaxBTC = SE.getConstantMaxBackedgeTakenCount(L); 1345 EXPECT_EQ(cast<SCEVConstant>(MaxBTC)->getAPInt(), 15); 1346 }); 1347 } 1348 1349 TEST_F(ScalarEvolutionsTest, ImpliedViaAddRecStart) { 1350 LLVMContext C; 1351 SMDiagnostic Err; 1352 std::unique_ptr<Module> M = parseAssemblyString( 1353 "define void @foo(i32* %p) { " 1354 "entry: " 1355 " %x = load i32, i32* %p, !range !0 " 1356 " br label %loop " 1357 "loop: " 1358 " %iv = phi i32 [ %x, %entry], [%iv.next, %backedge] " 1359 " %ne.check = icmp ne i32 %iv, 0 " 1360 " br i1 %ne.check, label %backedge, label %exit " 1361 "backedge: " 1362 " %iv.next = add i32 %iv, -1 " 1363 " br label %loop " 1364 "exit:" 1365 " ret void " 1366 "} " 1367 "!0 = !{i32 0, i32 2147483647}", 1368 Err, C); 1369 1370 ASSERT_TRUE(M && "Could not parse module?"); 1371 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1372 1373 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1374 const SCEV *X = SE.getSCEV(getInstructionByName(F, "x")); 1375 auto *Context = getInstructionByName(F, "iv.next"); 1376 EXPECT_TRUE(SE.isKnownPredicateAt(ICmpInst::ICMP_NE, X, 1377 SE.getZero(X->getType()), Context)); 1378 }); 1379 } 1380 1381 TEST_F(ScalarEvolutionsTest, UnsignedIsImpliedViaOperations) { 1382 LLVMContext C; 1383 SMDiagnostic Err; 1384 std::unique_ptr<Module> M = 1385 parseAssemblyString("define void @foo(i32* %p1, i32* %p2) { " 1386 "entry: " 1387 " %x = load i32, i32* %p1, !range !0 " 1388 " %cond = icmp ne i32 %x, 0 " 1389 " br i1 %cond, label %guarded, label %exit " 1390 "guarded: " 1391 " %y = add i32 %x, -1 " 1392 " ret void " 1393 "exit: " 1394 " ret void " 1395 "} " 1396 "!0 = !{i32 0, i32 2147483647}", 1397 Err, C); 1398 1399 ASSERT_TRUE(M && "Could not parse module?"); 1400 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1401 1402 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1403 const SCEV *X = SE.getSCEV(getInstructionByName(F, "x")); 1404 const SCEV *Y = SE.getSCEV(getInstructionByName(F, "y")); 1405 auto *Guarded = getInstructionByName(F, "y")->getParent(); 1406 ASSERT_TRUE(Guarded); 1407 EXPECT_TRUE( 1408 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_ULT, Y, X)); 1409 EXPECT_TRUE( 1410 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_UGT, X, Y)); 1411 }); 1412 } 1413 1414 TEST_F(ScalarEvolutionsTest, ProveImplicationViaNarrowing) { 1415 LLVMContext C; 1416 SMDiagnostic Err; 1417 std::unique_ptr<Module> M = parseAssemblyString( 1418 "define i32 @foo(i32 %start, i32* %q) { " 1419 "entry: " 1420 " %wide.start = zext i32 %start to i64 " 1421 " br label %loop " 1422 "loop: " 1423 " %wide.iv = phi i64 [%wide.start, %entry], [%wide.iv.next, %backedge] " 1424 " %iv = phi i32 [%start, %entry], [%iv.next, %backedge] " 1425 " %cond = icmp eq i64 %wide.iv, 0 " 1426 " br i1 %cond, label %exit, label %backedge " 1427 "backedge: " 1428 " %iv.next = add i32 %iv, -1 " 1429 " %index = zext i32 %iv.next to i64 " 1430 " %load.addr = getelementptr i32, i32* %q, i64 %index " 1431 " %stop = load i32, i32* %load.addr " 1432 " %loop.cond = icmp eq i32 %stop, 0 " 1433 " %wide.iv.next = add nsw i64 %wide.iv, -1 " 1434 " br i1 %loop.cond, label %loop, label %failure " 1435 "exit: " 1436 " ret i32 0 " 1437 "failure: " 1438 " unreachable " 1439 "} ", 1440 Err, C); 1441 1442 ASSERT_TRUE(M && "Could not parse module?"); 1443 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1444 1445 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1446 const SCEV *IV = SE.getSCEV(getInstructionByName(F, "iv")); 1447 const SCEV *Zero = SE.getZero(IV->getType()); 1448 auto *Backedge = getInstructionByName(F, "iv.next")->getParent(); 1449 ASSERT_TRUE(Backedge); 1450 (void)IV; 1451 (void)Zero; 1452 // FIXME: This can only be proved with turned on option 1453 // scalar-evolution-use-expensive-range-sharpening which is currently off. 1454 // Enable the check once it's switched true by default. 1455 // EXPECT_TRUE(SE.isBasicBlockEntryGuardedByCond(Backedge, 1456 // ICmpInst::ICMP_UGT, 1457 // IV, Zero)); 1458 }); 1459 } 1460 1461 TEST_F(ScalarEvolutionsTest, ImpliedCond) { 1462 LLVMContext C; 1463 SMDiagnostic Err; 1464 std::unique_ptr<Module> M = parseAssemblyString( 1465 "define void @foo(i32 %len) { " 1466 "entry: " 1467 " br label %loop " 1468 "loop: " 1469 " %iv = phi i32 [ 0, %entry], [%iv.next, %loop] " 1470 " %iv.next = add nsw i32 %iv, 1 " 1471 " %cmp = icmp slt i32 %iv, %len " 1472 " br i1 %cmp, label %loop, label %exit " 1473 "exit:" 1474 " ret void " 1475 "}", 1476 Err, C); 1477 1478 ASSERT_TRUE(M && "Could not parse module?"); 1479 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1480 1481 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1482 Instruction *IV = getInstructionByName(F, "iv"); 1483 Type *Ty = IV->getType(); 1484 const SCEV *Zero = SE.getZero(Ty); 1485 const SCEV *MinusOne = SE.getMinusOne(Ty); 1486 // {0,+,1}<nuw><nsw> 1487 const SCEV *AddRec_0_1 = SE.getSCEV(IV); 1488 // {0,+,-1}<nw> 1489 const SCEV *AddRec_0_N1 = SE.getNegativeSCEV(AddRec_0_1); 1490 1491 // {0,+,1}<nuw><nsw> > 0 -> {0,+,-1}<nw> < 0 1492 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SLT, AddRec_0_N1, Zero, 1493 ICmpInst::ICMP_SGT, AddRec_0_1, Zero)); 1494 // {0,+,-1}<nw> < -1 -> {0,+,1}<nuw><nsw> > 0 1495 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SGT, AddRec_0_1, Zero, 1496 ICmpInst::ICMP_SLT, AddRec_0_N1, MinusOne)); 1497 }); 1498 } 1499 1500 TEST_F(ScalarEvolutionsTest, MatchURem) { 1501 LLVMContext C; 1502 SMDiagnostic Err; 1503 std::unique_ptr<Module> M = parseAssemblyString( 1504 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" " 1505 " " 1506 "define void @test(i32 %a, i32 %b, i16 %c, i64 %d) {" 1507 "entry: " 1508 " %rem1 = urem i32 %a, 2" 1509 " %rem2 = urem i32 %a, 5" 1510 " %rem3 = urem i32 %a, %b" 1511 " %c.ext = zext i16 %c to i32" 1512 " %rem4 = urem i32 %c.ext, 2" 1513 " %ext = zext i32 %rem4 to i64" 1514 " %rem5 = urem i64 %d, 17179869184" 1515 " ret void " 1516 "} ", 1517 Err, C); 1518 1519 assert(M && "Could not parse module?"); 1520 assert(!verifyModule(*M) && "Must have been well formed!"); 1521 1522 runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1523 for (auto *N : {"rem1", "rem2", "rem3", "rem5"}) { 1524 auto *URemI = getInstructionByName(F, N); 1525 auto *S = SE.getSCEV(URemI); 1526 const SCEV *LHS, *RHS; 1527 EXPECT_TRUE(matchURem(SE, S, LHS, RHS)); 1528 EXPECT_EQ(LHS, SE.getSCEV(URemI->getOperand(0))); 1529 EXPECT_EQ(RHS, SE.getSCEV(URemI->getOperand(1))); 1530 EXPECT_EQ(LHS->getType(), S->getType()); 1531 EXPECT_EQ(RHS->getType(), S->getType()); 1532 } 1533 1534 // Check the case where the urem operand is zero-extended. Make sure the 1535 // match results are extended to the size of the input expression. 1536 auto *Ext = getInstructionByName(F, "ext"); 1537 auto *URem1 = getInstructionByName(F, "rem4"); 1538 auto *S = SE.getSCEV(Ext); 1539 const SCEV *LHS, *RHS; 1540 EXPECT_TRUE(matchURem(SE, S, LHS, RHS)); 1541 EXPECT_NE(LHS, SE.getSCEV(URem1->getOperand(0))); 1542 // RHS and URem1->getOperand(1) have different widths, so compare the 1543 // integer values. 1544 EXPECT_EQ(cast<SCEVConstant>(RHS)->getValue()->getZExtValue(), 1545 cast<SCEVConstant>(SE.getSCEV(URem1->getOperand(1))) 1546 ->getValue() 1547 ->getZExtValue()); 1548 EXPECT_EQ(LHS->getType(), S->getType()); 1549 EXPECT_EQ(RHS->getType(), S->getType()); 1550 }); 1551 } 1552 1553 TEST_F(ScalarEvolutionsTest, SCEVUDivFloorCeiling) { 1554 LLVMContext C; 1555 SMDiagnostic Err; 1556 std::unique_ptr<Module> M = parseAssemblyString("define void @foo() { " 1557 " ret void " 1558 "} ", 1559 Err, C); 1560 1561 ASSERT_TRUE(M && "Could not parse module?"); 1562 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1563 1564 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1565 // Check that SCEV's udiv and uceil handling produce the correct results 1566 // for all 8 bit options. Div-by-zero is deliberately excluded. 1567 for (unsigned N = 0; N < 256; N++) 1568 for (unsigned D = 1; D < 256; D++) { 1569 APInt NInt(8, N); 1570 APInt DInt(8, D); 1571 using namespace llvm::APIntOps; 1572 APInt FloorInt = RoundingUDiv(NInt, DInt, APInt::Rounding::DOWN); 1573 APInt CeilingInt = RoundingUDiv(NInt, DInt, APInt::Rounding::UP); 1574 const SCEV *NS = SE.getConstant(NInt); 1575 const SCEV *DS = SE.getConstant(DInt); 1576 auto *FloorS = cast<SCEVConstant>(SE.getUDivExpr(NS, DS)); 1577 auto *CeilingS = cast<SCEVConstant>(SE.getUDivCeilSCEV(NS, DS)); 1578 ASSERT_TRUE(FloorS->getAPInt() == FloorInt); 1579 ASSERT_TRUE(CeilingS->getAPInt() == CeilingInt); 1580 } 1581 }); 1582 } 1583 1584 TEST_F(ScalarEvolutionsTest, CheckGetPowerOfTwo) { 1585 Module M("CheckGetPowerOfTwo", Context); 1586 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false); 1587 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M); 1588 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1589 IRBuilder<> Builder(Entry); 1590 Builder.CreateRetVoid(); 1591 ScalarEvolution SE = buildSE(*F); 1592 1593 for (unsigned short i = 0; i < 64; ++i) 1594 EXPECT_TRUE( 1595 dyn_cast<SCEVConstant>(SE.getPowerOfTwo(Type::getInt64Ty(Context), i)) 1596 ->getValue() 1597 ->equalsInt(1ULL << i)); 1598 } 1599 1600 TEST_F(ScalarEvolutionsTest, ApplyLoopGuards) { 1601 LLVMContext C; 1602 SMDiagnostic Err; 1603 std::unique_ptr<Module> M = parseAssemblyString( 1604 "declare void @llvm.assume(i1)\n" 1605 "define void @test(i32 %num) {\n" 1606 "entry:\n" 1607 " %u = urem i32 %num, 4\n" 1608 " %cmp = icmp eq i32 %u, 0\n" 1609 " tail call void @llvm.assume(i1 %cmp)\n" 1610 " %cmp.1 = icmp ugt i32 %num, 0\n" 1611 " tail call void @llvm.assume(i1 %cmp.1)\n" 1612 " br label %for.body\n" 1613 "for.body:\n" 1614 " %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n" 1615 " %inc = add nuw nsw i32 %i.010, 1\n" 1616 " %cmp2 = icmp ult i32 %inc, %num\n" 1617 " br i1 %cmp2, label %for.body, label %exit\n" 1618 "exit:\n" 1619 " ret void\n" 1620 "}\n", 1621 Err, C); 1622 1623 ASSERT_TRUE(M && "Could not parse module?"); 1624 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1625 1626 runWithSE(*M, "test", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1627 const SCEV *TCScev = SE.getSCEV(getArgByName(F, "num")); 1628 const SCEV *ApplyLoopGuardsTC = SE.applyLoopGuards(TCScev, *LI.begin()); 1629 // Assert that the new TC is (4 * ((4 umax %num) /u 4)) 1630 APInt Four(32, 4); 1631 const SCEV *Constant4 = SE.getConstant(Four); 1632 const SCEV *Max = SE.getUMaxExpr(TCScev, Constant4); 1633 const SCEV *Mul = SE.getMulExpr(SE.getUDivExpr(Max, Constant4), Constant4); 1634 ASSERT_TRUE(Mul == ApplyLoopGuardsTC); 1635 }); 1636 } 1637 1638 TEST_F(ScalarEvolutionsTest, ForgetValueWithOverflowInst) { 1639 LLVMContext C; 1640 SMDiagnostic Err; 1641 std::unique_ptr<Module> M = parseAssemblyString( 1642 "declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) " 1643 "define void @foo(i32 %i) { " 1644 "entry: " 1645 " br label %loop.body " 1646 "loop.body: " 1647 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] " 1648 " %iv.next = add nsw i32 %iv, 1 " 1649 " %call = call {i32, i1} @llvm.smul.with.overflow.i32(i32 %iv, i32 -2) " 1650 " %extractvalue = extractvalue {i32, i1} %call, 0 " 1651 " %cmp = icmp eq i32 %iv.next, 16 " 1652 " br i1 %cmp, label %exit, label %loop.body " 1653 "exit: " 1654 " ret void " 1655 "} ", 1656 Err, C); 1657 1658 ASSERT_TRUE(M && "Could not parse module?"); 1659 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1660 1661 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1662 auto *ExtractValue = getInstructionByName(F, "extractvalue"); 1663 auto *IV = getInstructionByName(F, "iv"); 1664 1665 auto *ExtractValueScev = SE.getSCEV(ExtractValue); 1666 EXPECT_NE(ExtractValueScev, nullptr); 1667 1668 SE.forgetValue(IV); 1669 auto *ExtractValueScevForgotten = SE.getExistingSCEV(ExtractValue); 1670 EXPECT_EQ(ExtractValueScevForgotten, nullptr); 1671 }); 1672 } 1673 1674 TEST_F(ScalarEvolutionsTest, ComplexityComparatorIsStrictWeakOrdering) { 1675 // Regression test for a case where caching of equivalent values caused the 1676 // comparator to get inconsistent. 1677 LLVMContext C; 1678 SMDiagnostic Err; 1679 std::unique_ptr<Module> M = parseAssemblyString(R"( 1680 define i32 @foo(i32 %arg0) { 1681 %1 = add i32 %arg0, 1 1682 %2 = add i32 %arg0, 1 1683 %3 = xor i32 %2, %1 1684 %4 = add i32 %3, %2 1685 %5 = add i32 %arg0, 1 1686 %6 = xor i32 %5, %arg0 1687 %7 = add i32 %arg0, %6 1688 %8 = add i32 %5, %7 1689 %9 = xor i32 %8, %7 1690 %10 = add i32 %9, %8 1691 %11 = xor i32 %10, %9 1692 %12 = add i32 %11, %10 1693 %13 = xor i32 %12, %11 1694 %14 = add i32 %12, %13 1695 %15 = add i32 %14, %4 1696 ret i32 %15 1697 })", 1698 Err, C); 1699 1700 ASSERT_TRUE(M && "Could not parse module?"); 1701 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1702 1703 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1704 // When _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG, this will 1705 // crash if the comparator has the specific caching bug. 1706 SE.getSCEV(F.getEntryBlock().getTerminator()->getOperand(0)); 1707 }); 1708 } 1709 1710 } // end namespace llvm 1711