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