1 //===- ScalarEvolutionsTest.cpp - ScalarEvolution unit tests --------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/ADT/SmallVector.h" 11 #include "llvm/Analysis/AssumptionCache.h" 12 #include "llvm/Analysis/LoopInfo.h" 13 #include "llvm/Analysis/ScalarEvolutionExpander.h" 14 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 15 #include "llvm/Analysis/TargetLibraryInfo.h" 16 #include "llvm/AsmParser/Parser.h" 17 #include "llvm/IR/Constants.h" 18 #include "llvm/IR/Dominators.h" 19 #include "llvm/IR/GlobalVariable.h" 20 #include "llvm/IR/IRBuilder.h" 21 #include "llvm/IR/InstIterator.h" 22 #include "llvm/IR/LLVMContext.h" 23 #include "llvm/IR/LegacyPassManager.h" 24 #include "llvm/IR/Module.h" 25 #include "llvm/IR/Verifier.h" 26 #include "llvm/Support/SourceMgr.h" 27 #include "gtest/gtest.h" 28 29 namespace llvm { 30 namespace { 31 32 // We use this fixture to ensure that we clean up ScalarEvolution before 33 // deleting the PassManager. 34 class ScalarEvolutionsTest : public testing::Test { 35 protected: 36 LLVMContext Context; 37 Module M; 38 TargetLibraryInfoImpl TLII; 39 TargetLibraryInfo TLI; 40 41 std::unique_ptr<AssumptionCache> AC; 42 std::unique_ptr<DominatorTree> DT; 43 std::unique_ptr<LoopInfo> LI; 44 45 ScalarEvolutionsTest() : M("", Context), TLII(), TLI(TLII) {} 46 47 ScalarEvolution buildSE(Function &F) { 48 AC.reset(new AssumptionCache(F)); 49 DT.reset(new DominatorTree(F)); 50 LI.reset(new LoopInfo(*DT)); 51 return ScalarEvolution(F, TLI, *AC, *DT, *LI); 52 } 53 54 void runWithSE( 55 Module &M, StringRef FuncName, 56 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) { 57 auto *F = M.getFunction(FuncName); 58 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 59 ScalarEvolution SE = buildSE(*F); 60 Test(*F, *LI, SE); 61 } 62 }; 63 64 TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) { 65 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), 66 std::vector<Type *>(), false); 67 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 68 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 69 ReturnInst::Create(Context, nullptr, BB); 70 71 Type *Ty = Type::getInt1Ty(Context); 72 Constant *Init = Constant::getNullValue(Ty); 73 Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0"); 74 Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1"); 75 Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2"); 76 77 ScalarEvolution SE = buildSE(*F); 78 79 const SCEV *S0 = SE.getSCEV(V0); 80 const SCEV *S1 = SE.getSCEV(V1); 81 const SCEV *S2 = SE.getSCEV(V2); 82 83 const SCEV *P0 = SE.getAddExpr(S0, S0); 84 const SCEV *P1 = SE.getAddExpr(S1, S1); 85 const SCEV *P2 = SE.getAddExpr(S2, S2); 86 87 const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0); 88 const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1); 89 const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2); 90 91 EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(), 92 2u); 93 EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(), 94 2u); 95 EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(), 96 2u); 97 98 // Before the RAUWs, these are all pointing to separate values. 99 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0); 100 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1); 101 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2); 102 103 // Do some RAUWs. 104 V2->replaceAllUsesWith(V1); 105 V1->replaceAllUsesWith(V0); 106 107 // After the RAUWs, these should all be pointing to V0. 108 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0); 109 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0); 110 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0); 111 } 112 113 TEST_F(ScalarEvolutionsTest, SimplifiedPHI) { 114 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), 115 std::vector<Type *>(), false); 116 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 117 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 118 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 119 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 120 BranchInst::Create(LoopBB, EntryBB); 121 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), 122 LoopBB); 123 ReturnInst::Create(Context, nullptr, ExitBB); 124 auto *Ty = Type::getInt32Ty(Context); 125 auto *PN = PHINode::Create(Ty, 2, "", &*LoopBB->begin()); 126 PN->addIncoming(Constant::getNullValue(Ty), EntryBB); 127 PN->addIncoming(UndefValue::get(Ty), LoopBB); 128 ScalarEvolution SE = buildSE(*F); 129 auto *S1 = SE.getSCEV(PN); 130 auto *S2 = SE.getSCEV(PN); 131 auto *ZeroConst = SE.getConstant(Ty, 0); 132 133 // At some point, only the first call to getSCEV returned the simplified 134 // SCEVConstant and later calls just returned a SCEVUnknown referencing the 135 // PHI node. 136 EXPECT_EQ(S1, ZeroConst); 137 EXPECT_EQ(S1, S2); 138 } 139 140 TEST_F(ScalarEvolutionsTest, ExpandPtrTypeSCEV) { 141 // It is to test the fix for PR30213. It exercises the branch in scev 142 // expansion when the value in ValueOffsetPair is a ptr and the offset 143 // is not divisible by the elem type size of value. 144 auto *I8Ty = Type::getInt8Ty(Context); 145 auto *I8PtrTy = Type::getInt8PtrTy(Context); 146 auto *I32Ty = Type::getInt32Ty(Context); 147 auto *I32PtrTy = Type::getInt32PtrTy(Context); 148 FunctionType *FTy = 149 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false); 150 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 151 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 152 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 153 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 154 BranchInst::Create(LoopBB, EntryBB); 155 ReturnInst::Create(Context, nullptr, ExitBB); 156 157 // loop: ; preds = %loop, %entry 158 // %alloca = alloca i32 159 // %gep0 = getelementptr i32, i32* %alloca, i32 1 160 // %bitcast1 = bitcast i32* %gep0 to i8* 161 // %gep1 = getelementptr i8, i8* %bitcast1, i32 1 162 // %gep2 = getelementptr i8, i8* undef, i32 1 163 // %cmp = icmp ult i8* undef, %bitcast1 164 // %select = select i1 %cmp, i8* %gep1, i8* %gep2 165 // %bitcast2 = bitcast i8* %select to i32* 166 // br i1 undef, label %loop, label %exit 167 168 const DataLayout &DL = F->getParent()->getDataLayout(); 169 BranchInst *Br = BranchInst::Create( 170 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB); 171 AllocaInst *Alloca = new AllocaInst(I32Ty, DL.getAllocaAddrSpace(), 172 "alloca", Br); 173 ConstantInt *Ci32 = ConstantInt::get(Context, APInt(32, 1)); 174 GetElementPtrInst *Gep0 = 175 GetElementPtrInst::Create(I32Ty, Alloca, Ci32, "gep0", Br); 176 CastInst *CastA = 177 CastInst::CreateBitOrPointerCast(Gep0, I8PtrTy, "bitcast1", Br); 178 GetElementPtrInst *Gep1 = 179 GetElementPtrInst::Create(I8Ty, CastA, Ci32, "gep1", Br); 180 GetElementPtrInst *Gep2 = GetElementPtrInst::Create( 181 I8Ty, UndefValue::get(I8PtrTy), Ci32, "gep2", Br); 182 CmpInst *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT, 183 UndefValue::get(I8PtrTy), CastA, "cmp", Br); 184 SelectInst *Sel = SelectInst::Create(Cmp, Gep1, Gep2, "select", Br); 185 CastInst *CastB = 186 CastInst::CreateBitOrPointerCast(Sel, I32PtrTy, "bitcast2", Br); 187 188 ScalarEvolution SE = buildSE(*F); 189 auto *S = SE.getSCEV(CastB); 190 SCEVExpander Exp(SE, M.getDataLayout(), "expander"); 191 Value *V = 192 Exp.expandCodeFor(cast<SCEVAddExpr>(S)->getOperand(1), nullptr, Br); 193 194 // Expect the expansion code contains: 195 // %0 = bitcast i32* %bitcast2 to i8* 196 // %uglygep = getelementptr i8, i8* %0, i64 -1 197 // %1 = bitcast i8* %uglygep to i32* 198 EXPECT_TRUE(isa<BitCastInst>(V)); 199 Instruction *Gep = cast<Instruction>(V)->getPrevNode(); 200 EXPECT_TRUE(isa<GetElementPtrInst>(Gep)); 201 EXPECT_TRUE(isa<ConstantInt>(Gep->getOperand(1))); 202 EXPECT_EQ(cast<ConstantInt>(Gep->getOperand(1))->getSExtValue(), -1); 203 EXPECT_TRUE(isa<BitCastInst>(Gep->getPrevNode())); 204 } 205 206 static Instruction *getInstructionByName(Function &F, StringRef Name) { 207 for (auto &I : instructions(F)) 208 if (I.getName() == Name) 209 return &I; 210 llvm_unreachable("Expected to find instruction!"); 211 } 212 213 TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) { 214 LLVMContext C; 215 SMDiagnostic Err; 216 std::unique_ptr<Module> M = parseAssemblyString( 217 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" " 218 " " 219 "@var_0 = external global i32, align 4" 220 "@var_1 = external global i32, align 4" 221 "@var_2 = external global i32, align 4" 222 " " 223 "declare i32 @unknown(i32, i32, i32)" 224 " " 225 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) " 226 " local_unnamed_addr { " 227 "entry: " 228 " %entrycond = icmp sgt i32 %n, 0 " 229 " br i1 %entrycond, label %loop.ph, label %for.end " 230 " " 231 "loop.ph: " 232 " %a = load i32, i32* %A, align 4 " 233 " %b = load i32, i32* %B, align 4 " 234 " %mul = mul nsw i32 %b, %a " 235 " %iv0.init = getelementptr inbounds i8, i8* %arr, i32 %mul " 236 " br label %loop " 237 " " 238 "loop: " 239 " %iv0 = phi i8* [ %iv0.inc, %loop ], [ %iv0.init, %loop.ph ] " 240 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ 0, %loop.ph ] " 241 " %conv = trunc i32 %iv1 to i8 " 242 " store i8 %conv, i8* %iv0, align 1 " 243 " %iv0.inc = getelementptr inbounds i8, i8* %iv0, i32 %b " 244 " %iv1.inc = add nuw nsw i32 %iv1, 1 " 245 " %exitcond = icmp eq i32 %iv1.inc, %n " 246 " br i1 %exitcond, label %for.end.loopexit, label %loop " 247 " " 248 "for.end.loopexit: " 249 " br label %for.end " 250 " " 251 "for.end: " 252 " ret void " 253 "} " 254 " " 255 "define void @f_2(i32* %X, i32* %Y, i32* %Z) { " 256 " %x = load i32, i32* %X " 257 " %y = load i32, i32* %Y " 258 " %z = load i32, i32* %Z " 259 " ret void " 260 "} " 261 " " 262 "define void @f_3() { " 263 " %x = load i32, i32* @var_0" 264 " %y = load i32, i32* @var_1" 265 " %z = load i32, i32* @var_2" 266 " ret void" 267 "} " 268 " " 269 "define void @f_4(i32 %a, i32 %b, i32 %c) { " 270 " %x = call i32 @unknown(i32 %a, i32 %b, i32 %c)" 271 " %y = call i32 @unknown(i32 %b, i32 %c, i32 %a)" 272 " %z = call i32 @unknown(i32 %c, i32 %a, i32 %b)" 273 " ret void" 274 "} " 275 , 276 Err, C); 277 278 assert(M && "Could not parse module?"); 279 assert(!verifyModule(*M) && "Must have been well formed!"); 280 281 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 282 auto *IV0 = getInstructionByName(F, "iv0"); 283 auto *IV0Inc = getInstructionByName(F, "iv0.inc"); 284 285 auto *FirstExprForIV0 = SE.getSCEV(IV0); 286 auto *FirstExprForIV0Inc = SE.getSCEV(IV0Inc); 287 auto *SecondExprForIV0 = SE.getSCEV(IV0); 288 289 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0)); 290 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0Inc)); 291 EXPECT_TRUE(isa<SCEVAddRecExpr>(SecondExprForIV0)); 292 }); 293 294 auto CheckCommutativeMulExprs = [&](ScalarEvolution &SE, const SCEV *A, 295 const SCEV *B, const SCEV *C) { 296 EXPECT_EQ(SE.getMulExpr(A, B), SE.getMulExpr(B, A)); 297 EXPECT_EQ(SE.getMulExpr(B, C), SE.getMulExpr(C, B)); 298 EXPECT_EQ(SE.getMulExpr(A, C), SE.getMulExpr(C, A)); 299 300 SmallVector<const SCEV *, 3> Ops0 = {A, B, C}; 301 SmallVector<const SCEV *, 3> Ops1 = {A, C, B}; 302 SmallVector<const SCEV *, 3> Ops2 = {B, A, C}; 303 SmallVector<const SCEV *, 3> Ops3 = {B, C, A}; 304 SmallVector<const SCEV *, 3> Ops4 = {C, B, A}; 305 SmallVector<const SCEV *, 3> Ops5 = {C, A, B}; 306 307 auto *Mul0 = SE.getMulExpr(Ops0); 308 auto *Mul1 = SE.getMulExpr(Ops1); 309 auto *Mul2 = SE.getMulExpr(Ops2); 310 auto *Mul3 = SE.getMulExpr(Ops3); 311 auto *Mul4 = SE.getMulExpr(Ops4); 312 auto *Mul5 = SE.getMulExpr(Ops5); 313 314 EXPECT_EQ(Mul0, Mul1) << "Expected " << *Mul0 << " == " << *Mul1; 315 EXPECT_EQ(Mul1, Mul2) << "Expected " << *Mul1 << " == " << *Mul2; 316 EXPECT_EQ(Mul2, Mul3) << "Expected " << *Mul2 << " == " << *Mul3; 317 EXPECT_EQ(Mul3, Mul4) << "Expected " << *Mul3 << " == " << *Mul4; 318 EXPECT_EQ(Mul4, Mul5) << "Expected " << *Mul4 << " == " << *Mul5; 319 }; 320 321 for (StringRef FuncName : {"f_2", "f_3", "f_4"}) 322 runWithSE( 323 *M, FuncName, [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 324 CheckCommutativeMulExprs(SE, SE.getSCEV(getInstructionByName(F, "x")), 325 SE.getSCEV(getInstructionByName(F, "y")), 326 SE.getSCEV(getInstructionByName(F, "z"))); 327 }); 328 } 329 330 TEST_F(ScalarEvolutionsTest, CompareSCEVComplexity) { 331 FunctionType *FTy = 332 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false); 333 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 334 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 335 BasicBlock *LoopBB = BasicBlock::Create(Context, "bb1", F); 336 BranchInst::Create(LoopBB, EntryBB); 337 338 auto *Ty = Type::getInt32Ty(Context); 339 SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8); 340 341 Acc[0] = PHINode::Create(Ty, 2, "", LoopBB); 342 Acc[1] = PHINode::Create(Ty, 2, "", LoopBB); 343 Acc[2] = PHINode::Create(Ty, 2, "", LoopBB); 344 Acc[3] = PHINode::Create(Ty, 2, "", LoopBB); 345 Acc[4] = PHINode::Create(Ty, 2, "", LoopBB); 346 Acc[5] = PHINode::Create(Ty, 2, "", LoopBB); 347 Acc[6] = PHINode::Create(Ty, 2, "", LoopBB); 348 Acc[7] = PHINode::Create(Ty, 2, "", LoopBB); 349 350 for (int i = 0; i < 20; i++) { 351 Muls[0] = BinaryOperator::CreateMul(Acc[0], Acc[0], "", LoopBB); 352 NextAcc[0] = BinaryOperator::CreateAdd(Muls[0], Acc[4], "", LoopBB); 353 Muls[1] = BinaryOperator::CreateMul(Acc[1], Acc[1], "", LoopBB); 354 NextAcc[1] = BinaryOperator::CreateAdd(Muls[1], Acc[5], "", LoopBB); 355 Muls[2] = BinaryOperator::CreateMul(Acc[2], Acc[2], "", LoopBB); 356 NextAcc[2] = BinaryOperator::CreateAdd(Muls[2], Acc[6], "", LoopBB); 357 Muls[3] = BinaryOperator::CreateMul(Acc[3], Acc[3], "", LoopBB); 358 NextAcc[3] = BinaryOperator::CreateAdd(Muls[3], Acc[7], "", LoopBB); 359 360 Muls[4] = BinaryOperator::CreateMul(Acc[4], Acc[4], "", LoopBB); 361 NextAcc[4] = BinaryOperator::CreateAdd(Muls[4], Acc[0], "", LoopBB); 362 Muls[5] = BinaryOperator::CreateMul(Acc[5], Acc[5], "", LoopBB); 363 NextAcc[5] = BinaryOperator::CreateAdd(Muls[5], Acc[1], "", LoopBB); 364 Muls[6] = BinaryOperator::CreateMul(Acc[6], Acc[6], "", LoopBB); 365 NextAcc[6] = BinaryOperator::CreateAdd(Muls[6], Acc[2], "", LoopBB); 366 Muls[7] = BinaryOperator::CreateMul(Acc[7], Acc[7], "", LoopBB); 367 NextAcc[7] = BinaryOperator::CreateAdd(Muls[7], Acc[3], "", LoopBB); 368 Acc = NextAcc; 369 } 370 371 auto II = LoopBB->begin(); 372 for (int i = 0; i < 8; i++) { 373 PHINode *Phi = cast<PHINode>(&*II++); 374 Phi->addIncoming(Acc[i], LoopBB); 375 Phi->addIncoming(UndefValue::get(Ty), EntryBB); 376 } 377 378 BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F); 379 BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), 380 LoopBB); 381 382 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB); 383 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB); 384 Acc[2] = BinaryOperator::CreateAdd(Acc[4], Acc[5], "", ExitBB); 385 Acc[3] = BinaryOperator::CreateAdd(Acc[6], Acc[7], "", ExitBB); 386 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB); 387 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB); 388 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB); 389 390 ReturnInst::Create(Context, nullptr, ExitBB); 391 392 ScalarEvolution SE = buildSE(*F); 393 394 EXPECT_NE(nullptr, SE.getSCEV(Acc[0])); 395 } 396 397 TEST_F(ScalarEvolutionsTest, CompareValueComplexity) { 398 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(Context); 399 PointerType *IntPtrPtrTy = IntPtrTy->getPointerTo(); 400 401 FunctionType *FTy = 402 FunctionType::get(Type::getVoidTy(Context), {IntPtrTy, IntPtrTy}, false); 403 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 404 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 405 406 Value *X = &*F->arg_begin(); 407 Value *Y = &*std::next(F->arg_begin()); 408 409 const int ValueDepth = 10; 410 for (int i = 0; i < ValueDepth; i++) { 411 X = new LoadInst(new IntToPtrInst(X, IntPtrPtrTy, "", EntryBB), "", 412 /*isVolatile*/ false, EntryBB); 413 Y = new LoadInst(new IntToPtrInst(Y, IntPtrPtrTy, "", EntryBB), "", 414 /*isVolatile*/ false, EntryBB); 415 } 416 417 auto *MulA = BinaryOperator::CreateMul(X, Y, "", EntryBB); 418 auto *MulB = BinaryOperator::CreateMul(Y, X, "", EntryBB); 419 ReturnInst::Create(Context, nullptr, EntryBB); 420 421 // This test isn't checking for correctness. Today making A and B resolve to 422 // the same SCEV would require deeper searching in CompareValueComplexity, 423 // which will slow down compilation. However, this test can fail (with LLVM's 424 // behavior still being correct) if we ever have a smarter 425 // CompareValueComplexity that is both fast and more accurate. 426 427 ScalarEvolution SE = buildSE(*F); 428 auto *A = SE.getSCEV(MulA); 429 auto *B = SE.getSCEV(MulB); 430 EXPECT_NE(A, B); 431 } 432 433 TEST_F(ScalarEvolutionsTest, SCEVAddExpr) { 434 Type *Ty32 = Type::getInt32Ty(Context); 435 Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32}; 436 437 FunctionType *FTy = 438 FunctionType::get(Type::getVoidTy(Context), ArgTys, false); 439 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 440 441 Argument *A1 = &*F->arg_begin(); 442 Argument *A2 = &*(std::next(F->arg_begin())); 443 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 444 445 Instruction *Trunc = CastInst::CreateTruncOrBitCast(A1, Ty32, "", EntryBB); 446 Instruction *Mul1 = BinaryOperator::CreateMul(Trunc, A2, "", EntryBB); 447 Instruction *Add1 = BinaryOperator::CreateAdd(Mul1, Trunc, "", EntryBB); 448 Mul1 = BinaryOperator::CreateMul(Add1, Trunc, "", EntryBB); 449 Instruction *Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB); 450 // FIXME: The size of this is arbitrary and doesn't seem to change the 451 // result, but SCEV will do quadratic work for these so a large number here 452 // will be extremely slow. We should revisit what and how this is testing 453 // SCEV. 454 for (int i = 0; i < 10; i++) { 455 Mul1 = BinaryOperator::CreateMul(Add2, Add1, "", EntryBB); 456 Add1 = Add2; 457 Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB); 458 } 459 460 ReturnInst::Create(Context, nullptr, EntryBB); 461 ScalarEvolution SE = buildSE(*F); 462 EXPECT_NE(nullptr, SE.getSCEV(Mul1)); 463 } 464 465 static Instruction &GetInstByName(Function &F, StringRef Name) { 466 for (auto &I : instructions(F)) 467 if (I.getName() == Name) 468 return I; 469 llvm_unreachable("Could not find instructions!"); 470 } 471 472 TEST_F(ScalarEvolutionsTest, SCEVNormalization) { 473 LLVMContext C; 474 SMDiagnostic Err; 475 std::unique_ptr<Module> M = parseAssemblyString( 476 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" " 477 " " 478 "@var_0 = external global i32, align 4" 479 "@var_1 = external global i32, align 4" 480 "@var_2 = external global i32, align 4" 481 " " 482 "declare i32 @unknown(i32, i32, i32)" 483 " " 484 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) " 485 " local_unnamed_addr { " 486 "entry: " 487 " br label %loop.ph " 488 " " 489 "loop.ph: " 490 " br label %loop " 491 " " 492 "loop: " 493 " %iv0 = phi i32 [ %iv0.inc, %loop ], [ 0, %loop.ph ] " 494 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ -2147483648, %loop.ph ] " 495 " %iv0.inc = add i32 %iv0, 1 " 496 " %iv1.inc = add i32 %iv1, 3 " 497 " br i1 undef, label %for.end.loopexit, label %loop " 498 " " 499 "for.end.loopexit: " 500 " ret void " 501 "} " 502 " " 503 "define void @f_2(i32 %a, i32 %b, i32 %c, i32 %d) " 504 " local_unnamed_addr { " 505 "entry: " 506 " br label %loop_0 " 507 " " 508 "loop_0: " 509 " br i1 undef, label %loop_0, label %loop_1 " 510 " " 511 "loop_1: " 512 " br i1 undef, label %loop_2, label %loop_1 " 513 " " 514 " " 515 "loop_2: " 516 " br i1 undef, label %end, label %loop_2 " 517 " " 518 "end: " 519 " ret void " 520 "} " 521 , 522 Err, C); 523 524 assert(M && "Could not parse module?"); 525 assert(!verifyModule(*M) && "Must have been well formed!"); 526 527 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 528 auto &I0 = GetInstByName(F, "iv0"); 529 auto &I1 = *I0.getNextNode(); 530 531 auto *S0 = cast<SCEVAddRecExpr>(SE.getSCEV(&I0)); 532 PostIncLoopSet Loops; 533 Loops.insert(S0->getLoop()); 534 auto *N0 = normalizeForPostIncUse(S0, Loops, SE); 535 auto *D0 = denormalizeForPostIncUse(N0, Loops, SE); 536 EXPECT_EQ(S0, D0) << *S0 << " " << *D0; 537 538 auto *S1 = cast<SCEVAddRecExpr>(SE.getSCEV(&I1)); 539 Loops.clear(); 540 Loops.insert(S1->getLoop()); 541 auto *N1 = normalizeForPostIncUse(S1, Loops, SE); 542 auto *D1 = denormalizeForPostIncUse(N1, Loops, SE); 543 EXPECT_EQ(S1, D1) << *S1 << " " << *D1; 544 }); 545 546 runWithSE(*M, "f_2", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 547 auto *L2 = *LI.begin(); 548 auto *L1 = *std::next(LI.begin()); 549 auto *L0 = *std::next(LI.begin(), 2); 550 551 auto GetAddRec = [&SE](const Loop *L, std::initializer_list<const SCEV *> Ops) { 552 SmallVector<const SCEV *, 4> OpsCopy(Ops); 553 return SE.getAddRecExpr(OpsCopy, L, SCEV::FlagAnyWrap); 554 }; 555 556 auto GetAdd = [&SE](std::initializer_list<const SCEV *> Ops) { 557 SmallVector<const SCEV *, 4> OpsCopy(Ops); 558 return SE.getAddExpr(OpsCopy, SCEV::FlagAnyWrap); 559 }; 560 561 // We first populate the AddRecs vector with a few "interesting" SCEV 562 // expressions, and then we go through the list and assert that each 563 // expression in it has an invertible normalization. 564 565 std::vector<const SCEV *> Exprs; 566 { 567 const SCEV *V0 = SE.getSCEV(&*F.arg_begin()); 568 const SCEV *V1 = SE.getSCEV(&*std::next(F.arg_begin(), 1)); 569 const SCEV *V2 = SE.getSCEV(&*std::next(F.arg_begin(), 2)); 570 const SCEV *V3 = SE.getSCEV(&*std::next(F.arg_begin(), 3)); 571 572 Exprs.push_back(GetAddRec(L0, {V0})); // 0 573 Exprs.push_back(GetAddRec(L0, {V0, V1})); // 1 574 Exprs.push_back(GetAddRec(L0, {V0, V1, V2})); // 2 575 Exprs.push_back(GetAddRec(L0, {V0, V1, V2, V3})); // 3 576 577 Exprs.push_back( 578 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[3], Exprs[0]})); // 4 579 Exprs.push_back( 580 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[0], Exprs[3]})); // 5 581 Exprs.push_back( 582 GetAddRec(L1, {Exprs[1], Exprs[3], Exprs[3], Exprs[1]})); // 6 583 584 Exprs.push_back(GetAdd({Exprs[6], Exprs[3], V2})); // 7 585 586 Exprs.push_back( 587 GetAddRec(L2, {Exprs[4], Exprs[3], Exprs[3], Exprs[5]})); // 8 588 589 Exprs.push_back( 590 GetAddRec(L2, {Exprs[4], Exprs[6], Exprs[7], Exprs[3], V0})); // 9 591 } 592 593 std::vector<PostIncLoopSet> LoopSets; 594 for (int i = 0; i < 8; i++) { 595 LoopSets.emplace_back(); 596 if (i & 1) 597 LoopSets.back().insert(L0); 598 if (i & 2) 599 LoopSets.back().insert(L1); 600 if (i & 4) 601 LoopSets.back().insert(L2); 602 } 603 604 for (const auto &LoopSet : LoopSets) 605 for (auto *S : Exprs) { 606 { 607 auto *N = llvm::normalizeForPostIncUse(S, LoopSet, SE); 608 auto *D = llvm::denormalizeForPostIncUse(N, LoopSet, SE); 609 610 // Normalization and then denormalizing better give us back the same 611 // value. 612 EXPECT_EQ(S, D) << "S = " << *S << " D = " << *D << " N = " << *N; 613 } 614 { 615 auto *D = llvm::denormalizeForPostIncUse(S, LoopSet, SE); 616 auto *N = llvm::normalizeForPostIncUse(D, LoopSet, SE); 617 618 // Denormalization and then normalizing better give us back the same 619 // value. 620 EXPECT_EQ(S, N) << "S = " << *S << " N = " << *N; 621 } 622 } 623 }); 624 } 625 626 // Expect the call of getZeroExtendExpr will not cost exponential time. 627 TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExpr) { 628 LLVMContext C; 629 SMDiagnostic Err; 630 631 // Generate a function like below: 632 // define void @foo() { 633 // entry: 634 // br label %for.cond 635 // 636 // for.cond: 637 // %0 = phi i64 [ 100, %entry ], [ %dec, %for.inc ] 638 // %cmp = icmp sgt i64 %0, 90 639 // br i1 %cmp, label %for.inc, label %for.cond1 640 // 641 // for.inc: 642 // %dec = add nsw i64 %0, -1 643 // br label %for.cond 644 // 645 // for.cond1: 646 // %1 = phi i64 [ 100, %for.cond ], [ %dec5, %for.inc2 ] 647 // %cmp3 = icmp sgt i64 %1, 90 648 // br i1 %cmp3, label %for.inc2, label %for.cond4 649 // 650 // for.inc2: 651 // %dec5 = add nsw i64 %1, -1 652 // br label %for.cond1 653 // 654 // ...... 655 // 656 // for.cond89: 657 // %19 = phi i64 [ 100, %for.cond84 ], [ %dec94, %for.inc92 ] 658 // %cmp93 = icmp sgt i64 %19, 90 659 // br i1 %cmp93, label %for.inc92, label %for.end 660 // 661 // for.inc92: 662 // %dec94 = add nsw i64 %19, -1 663 // br label %for.cond89 664 // 665 // for.end: 666 // %gep = getelementptr i8, i8* null, i64 %dec 667 // %gep6 = getelementptr i8, i8* %gep, i64 %dec5 668 // ...... 669 // %gep95 = getelementptr i8, i8* %gep91, i64 %dec94 670 // ret void 671 // } 672 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false); 673 Function *F = cast<Function>(M.getOrInsertFunction("foo", FTy)); 674 675 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 676 BasicBlock *CondBB = BasicBlock::Create(Context, "for.cond", F); 677 BasicBlock *EndBB = BasicBlock::Create(Context, "for.end", F); 678 BranchInst::Create(CondBB, EntryBB); 679 BasicBlock *PrevBB = EntryBB; 680 681 Type *I64Ty = Type::getInt64Ty(Context); 682 Type *I8Ty = Type::getInt8Ty(Context); 683 Type *I8PtrTy = Type::getInt8PtrTy(Context); 684 Value *Accum = Constant::getNullValue(I8PtrTy); 685 int Iters = 20; 686 for (int i = 0; i < Iters; i++) { 687 BasicBlock *IncBB = BasicBlock::Create(Context, "for.inc", F, EndBB); 688 auto *PN = PHINode::Create(I64Ty, 2, "", CondBB); 689 PN->addIncoming(ConstantInt::get(Context, APInt(64, 100)), PrevBB); 690 auto *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_SGT, PN, 691 ConstantInt::get(Context, APInt(64, 90)), "cmp", 692 CondBB); 693 BasicBlock *NextBB; 694 if (i != Iters - 1) 695 NextBB = BasicBlock::Create(Context, "for.cond", F, EndBB); 696 else 697 NextBB = EndBB; 698 BranchInst::Create(IncBB, NextBB, Cmp, CondBB); 699 auto *Dec = BinaryOperator::CreateNSWAdd( 700 PN, ConstantInt::get(Context, APInt(64, -1)), "dec", IncBB); 701 PN->addIncoming(Dec, IncBB); 702 BranchInst::Create(CondBB, IncBB); 703 704 Accum = GetElementPtrInst::Create(I8Ty, Accum, Dec, "gep", EndBB); 705 706 PrevBB = CondBB; 707 CondBB = NextBB; 708 } 709 ReturnInst::Create(Context, nullptr, EndBB); 710 ScalarEvolution SE = buildSE(*F); 711 const SCEV *S = SE.getSCEV(Accum); 712 Type *I128Ty = Type::getInt128Ty(Context); 713 SE.getZeroExtendExpr(S, I128Ty); 714 } 715 716 // Make sure that SCEV doesn't introduce illegal ptrtoint/inttoptr instructions 717 TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExprNonIntegral) { 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 * br i1 undef, label %post, label %L2 729 * post: 730 * %gepbase = getelementptr i64 addrspace(10)* %arg, i64 1 731 * #= %gep = getelementptr i64 addrspace(10)* %gepbase, i64 %add =# 732 * ret void 733 * 734 * We will create the appropriate SCEV expression for %gep and expand it, 735 * then check that no inttoptr/ptrtoint instructions got inserted. 736 */ 737 738 // Create a module with non-integral pointers in it's datalayout 739 Module NIM("nonintegral", Context); 740 std::string DataLayout = M.getDataLayoutStr(); 741 if (!DataLayout.empty()) 742 DataLayout += "-"; 743 DataLayout += "ni:10"; 744 NIM.setDataLayout(DataLayout); 745 746 Type *T_int1 = Type::getInt1Ty(Context); 747 Type *T_int64 = Type::getInt64Ty(Context); 748 Type *T_pint64 = T_int64->getPointerTo(10); 749 750 FunctionType *FTy = 751 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 752 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy)); 753 754 Argument *Arg = &*F->arg_begin(); 755 756 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 757 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 758 BasicBlock *L = BasicBlock::Create(Context, "L", F); 759 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 760 761 IRBuilder<> Builder(Top); 762 Builder.CreateBr(LPh); 763 764 Builder.SetInsertPoint(LPh); 765 Builder.CreateBr(L); 766 767 Builder.SetInsertPoint(L); 768 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 769 Value *Add = Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"); 770 Builder.CreateCondBr(UndefValue::get(T_int1), L, Post); 771 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 772 Phi->addIncoming(Add, L); 773 774 Builder.SetInsertPoint(Post); 775 Value *GepBase = Builder.CreateGEP(Arg, ConstantInt::get(T_int64, 1)); 776 Instruction *Ret = Builder.CreateRetVoid(); 777 778 ScalarEvolution SE = buildSE(*F); 779 auto *AddRec = 780 SE.getAddRecExpr(SE.getUnknown(GepBase), SE.getConstant(T_int64, 1), 781 LI->getLoopFor(L), SCEV::FlagNUW); 782 783 SCEVExpander Exp(SE, NIM.getDataLayout(), "expander"); 784 Exp.disableCanonicalMode(); 785 Exp.expandCodeFor(AddRec, T_pint64, Ret); 786 787 // Make sure none of the instructions inserted were inttoptr/ptrtoint. 788 // The verifier will check this. 789 EXPECT_FALSE(verifyFunction(*F, &errs())); 790 } 791 792 // Make sure that SCEV invalidates exit limits after invalidating the values it 793 // depends on when we forget a loop. 794 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) { 795 /* 796 * Create the following code: 797 * func(i64 addrspace(10)* %arg) 798 * top: 799 * br label %L.ph 800 * L.ph: 801 * br label %L 802 * L: 803 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ] 804 * %add = add i64 %phi2, 1 805 * %cond = icmp slt i64 %add, 1000; then becomes 2000. 806 * br i1 %cond, label %post, label %L2 807 * post: 808 * ret void 809 * 810 */ 811 812 // Create a module with non-integral pointers in it's datalayout 813 Module NIM("nonintegral", Context); 814 std::string DataLayout = M.getDataLayoutStr(); 815 if (!DataLayout.empty()) 816 DataLayout += "-"; 817 DataLayout += "ni:10"; 818 NIM.setDataLayout(DataLayout); 819 820 Type *T_int64 = Type::getInt64Ty(Context); 821 Type *T_pint64 = T_int64->getPointerTo(10); 822 823 FunctionType *FTy = 824 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 825 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy)); 826 827 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 828 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 829 BasicBlock *L = BasicBlock::Create(Context, "L", F); 830 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 831 832 IRBuilder<> Builder(Top); 833 Builder.CreateBr(LPh); 834 835 Builder.SetInsertPoint(LPh); 836 Builder.CreateBr(L); 837 838 Builder.SetInsertPoint(L); 839 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 840 auto *Add = cast<Instruction>( 841 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); 842 auto *Limit = ConstantInt::get(T_int64, 1000); 843 auto *Cond = cast<Instruction>( 844 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond")); 845 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post)); 846 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 847 Phi->addIncoming(Add, L); 848 849 Builder.SetInsertPoint(Post); 850 Builder.CreateRetVoid(); 851 852 ScalarEvolution SE = buildSE(*F); 853 auto *Loop = LI->getLoopFor(L); 854 const SCEV *EC = SE.getBackedgeTakenCount(Loop); 855 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC)); 856 EXPECT_TRUE(isa<SCEVConstant>(EC)); 857 EXPECT_EQ(cast<SCEVConstant>(EC)->getAPInt().getLimitedValue(), 999u); 858 859 // The add recurrence {5,+,1} does not correspond to any PHI in the IR, and 860 // that is relevant to this test. 861 auto *Five = SE.getConstant(APInt(/*numBits=*/64, 5)); 862 auto *AR = 863 SE.getAddRecExpr(Five, SE.getOne(T_int64), Loop, SCEV::FlagAnyWrap); 864 const SCEV *ARAtLoopExit = SE.getSCEVAtScope(AR, nullptr); 865 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ARAtLoopExit)); 866 EXPECT_TRUE(isa<SCEVConstant>(ARAtLoopExit)); 867 EXPECT_EQ(cast<SCEVConstant>(ARAtLoopExit)->getAPInt().getLimitedValue(), 868 1004u); 869 870 SE.forgetLoop(Loop); 871 Br->eraseFromParent(); 872 Cond->eraseFromParent(); 873 874 Builder.SetInsertPoint(L); 875 auto *NewCond = Builder.CreateICmp( 876 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond"); 877 Builder.CreateCondBr(NewCond, L, Post); 878 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop); 879 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC)); 880 EXPECT_TRUE(isa<SCEVConstant>(NewEC)); 881 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u); 882 const SCEV *NewARAtLoopExit = SE.getSCEVAtScope(AR, nullptr); 883 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewARAtLoopExit)); 884 EXPECT_TRUE(isa<SCEVConstant>(NewARAtLoopExit)); 885 EXPECT_EQ(cast<SCEVConstant>(NewARAtLoopExit)->getAPInt().getLimitedValue(), 886 2004u); 887 } 888 889 // Make sure that SCEV invalidates exit limits after invalidating the values it 890 // depends on when we forget a value. 891 TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) { 892 /* 893 * Create the following code: 894 * func(i64 addrspace(10)* %arg) 895 * top: 896 * br label %L.ph 897 * L.ph: 898 * %load = load i64 addrspace(10)* %arg 899 * br label %L 900 * L: 901 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ] 902 * %add = add i64 %phi2, 1 903 * %cond = icmp slt i64 %add, %load ; then becomes 2000. 904 * br i1 %cond, label %post, label %L2 905 * post: 906 * ret void 907 * 908 */ 909 910 // Create a module with non-integral pointers in it's datalayout 911 Module NIM("nonintegral", Context); 912 std::string DataLayout = M.getDataLayoutStr(); 913 if (!DataLayout.empty()) 914 DataLayout += "-"; 915 DataLayout += "ni:10"; 916 NIM.setDataLayout(DataLayout); 917 918 Type *T_int64 = Type::getInt64Ty(Context); 919 Type *T_pint64 = T_int64->getPointerTo(10); 920 921 FunctionType *FTy = 922 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 923 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy)); 924 925 Argument *Arg = &*F->arg_begin(); 926 927 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 928 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 929 BasicBlock *L = BasicBlock::Create(Context, "L", F); 930 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 931 932 IRBuilder<> Builder(Top); 933 Builder.CreateBr(LPh); 934 935 Builder.SetInsertPoint(LPh); 936 auto *Load = cast<Instruction>(Builder.CreateLoad(T_int64, Arg, "load")); 937 Builder.CreateBr(L); 938 939 Builder.SetInsertPoint(L); 940 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 941 auto *Add = cast<Instruction>( 942 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); 943 auto *Cond = cast<Instruction>( 944 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond")); 945 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post)); 946 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 947 Phi->addIncoming(Add, L); 948 949 Builder.SetInsertPoint(Post); 950 Builder.CreateRetVoid(); 951 952 ScalarEvolution SE = buildSE(*F); 953 auto *Loop = LI->getLoopFor(L); 954 const SCEV *EC = SE.getBackedgeTakenCount(Loop); 955 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC)); 956 EXPECT_FALSE(isa<SCEVConstant>(EC)); 957 958 SE.forgetValue(Load); 959 Br->eraseFromParent(); 960 Cond->eraseFromParent(); 961 Load->eraseFromParent(); 962 963 Builder.SetInsertPoint(L); 964 auto *NewCond = Builder.CreateICmp( 965 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond"); 966 Builder.CreateCondBr(NewCond, L, Post); 967 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop); 968 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC)); 969 EXPECT_TRUE(isa<SCEVConstant>(NewEC)); 970 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u); 971 } 972 973 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) { 974 // Reference: https://reviews.llvm.org/D37265 975 // Make sure that SCEV does not blow up when constructing an AddRec 976 // with predicates for a phi with the update pattern: 977 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum 978 // when either the initial value of the Phi or the InvariantAccum are 979 // constants that are too large to fit in an ix but are zero when truncated to 980 // ix. 981 FunctionType *FTy = 982 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false); 983 Function *F = cast<Function>(M.getOrInsertFunction("addrecphitest", FTy)); 984 985 /* 986 Create IR: 987 entry: 988 br label %loop 989 loop: 990 %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop] 991 %1 = shl i64 %0, 32 992 %2 = ashr exact i64 %1, 32 993 %3 = add i64 %2, -9223372036854775808 994 br i1 undef, label %exit, label %loop 995 exit: 996 ret void 997 */ 998 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 999 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 1000 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 1001 1002 // entry: 1003 BranchInst::Create(LoopBB, EntryBB); 1004 // loop: 1005 auto *MinInt64 = 1006 ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true)); 1007 auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32)); 1008 auto *Br = BranchInst::Create( 1009 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB); 1010 auto *Phi = PHINode::Create(Type::getInt64Ty(Context), 2, "", Br); 1011 auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br); 1012 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br); 1013 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br); 1014 Phi->addIncoming(MinInt64, EntryBB); 1015 Phi->addIncoming(Add, LoopBB); 1016 // exit: 1017 ReturnInst::Create(Context, nullptr, ExitBB); 1018 1019 // Make sure that SCEV doesn't blow up 1020 ScalarEvolution SE = buildSE(*F); 1021 SCEVUnionPredicate Preds; 1022 const SCEV *Expr = SE.getSCEV(Phi); 1023 EXPECT_NE(nullptr, Expr); 1024 EXPECT_TRUE(isa<SCEVUnknown>(Expr)); 1025 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr)); 1026 } 1027 1028 TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstantAccum) { 1029 // Make sure that SCEV does not blow up when constructing an AddRec 1030 // with predicates for a phi with the update pattern: 1031 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum 1032 // when the InvariantAccum is a constant that is too large to fit in an 1033 // ix but are zero when truncated to ix, and the initial value of the 1034 // phi is not a constant. 1035 Type *Int32Ty = Type::getInt32Ty(Context); 1036 SmallVector<Type *, 1> Types; 1037 Types.push_back(Int32Ty); 1038 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 1039 Function *F = cast<Function>(M.getOrInsertFunction("addrecphitest", FTy)); 1040 1041 /* 1042 Create IR: 1043 define @addrecphitest(i32) 1044 entry: 1045 br label %loop 1046 loop: 1047 %1 = phi i32 [%0, %entry], [%4, %loop] 1048 %2 = shl i32 %1, 16 1049 %3 = ashr exact i32 %2, 16 1050 %4 = add i32 %3, -2147483648 1051 br i1 undef, label %exit, label %loop 1052 exit: 1053 ret void 1054 */ 1055 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F); 1056 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F); 1057 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F); 1058 1059 // entry: 1060 BranchInst::Create(LoopBB, EntryBB); 1061 // loop: 1062 auto *MinInt32 = ConstantInt::get(Context, APInt(32, 0x80000000U, true)); 1063 auto *Int32_16 = ConstantInt::get(Context, APInt(32, 16)); 1064 auto *Br = BranchInst::Create( 1065 LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB); 1066 auto *Phi = PHINode::Create(Int32Ty, 2, "", Br); 1067 auto *Shl = BinaryOperator::CreateShl(Phi, Int32_16, "", Br); 1068 auto *AShr = BinaryOperator::CreateExactAShr(Shl, Int32_16, "", Br); 1069 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt32, "", Br); 1070 auto *Arg = &*(F->arg_begin()); 1071 Phi->addIncoming(Arg, EntryBB); 1072 Phi->addIncoming(Add, LoopBB); 1073 // exit: 1074 ReturnInst::Create(Context, nullptr, ExitBB); 1075 1076 // Make sure that SCEV doesn't blow up 1077 ScalarEvolution SE = buildSE(*F); 1078 SCEVUnionPredicate Preds; 1079 const SCEV *Expr = SE.getSCEV(Phi); 1080 EXPECT_NE(nullptr, Expr); 1081 EXPECT_TRUE(isa<SCEVUnknown>(Expr)); 1082 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr)); 1083 } 1084 1085 TEST_F(ScalarEvolutionsTest, SCEVFoldSumOfTruncs) { 1086 // Verify that the following SCEV gets folded to a zero: 1087 // (-1 * (trunc i64 (-1 * %0) to i32)) + (-1 * (trunc i64 %0 to i32) 1088 Type *ArgTy = Type::getInt64Ty(Context); 1089 Type *Int32Ty = Type::getInt32Ty(Context); 1090 SmallVector<Type *, 1> Types; 1091 Types.push_back(ArgTy); 1092 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 1093 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 1094 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 1095 ReturnInst::Create(Context, nullptr, BB); 1096 1097 ScalarEvolution SE = buildSE(*F); 1098 1099 auto *Arg = &*(F->arg_begin()); 1100 const auto *ArgSCEV = SE.getSCEV(Arg); 1101 1102 // Build the SCEV 1103 const auto *A0 = SE.getNegativeSCEV(ArgSCEV); 1104 const auto *A1 = SE.getTruncateExpr(A0, Int32Ty); 1105 const auto *A = SE.getNegativeSCEV(A1); 1106 1107 const auto *B0 = SE.getTruncateExpr(ArgSCEV, Int32Ty); 1108 const auto *B = SE.getNegativeSCEV(B0); 1109 1110 const auto *Expr = SE.getAddExpr(A, B); 1111 // Verify that the SCEV was folded to 0 1112 const auto *ZeroConst = SE.getConstant(Int32Ty, 0); 1113 EXPECT_EQ(Expr, ZeroConst); 1114 } 1115 1116 // Check that we can correctly identify the points at which the SCEV of the 1117 // AddRec can be expanded. 1118 TEST_F(ScalarEvolutionsTest, SCEVExpanderIsSafeToExpandAt) { 1119 /* 1120 * Create the following code: 1121 * func(i64 addrspace(10)* %arg) 1122 * top: 1123 * br label %L.ph 1124 * L.ph: 1125 * br label %L 1126 * L: 1127 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ] 1128 * %add = add i64 %phi2, 1 1129 * %cond = icmp slt i64 %add, 1000; then becomes 2000. 1130 * br i1 %cond, label %post, label %L2 1131 * post: 1132 * ret void 1133 * 1134 */ 1135 1136 // Create a module with non-integral pointers in it's datalayout 1137 Module NIM("nonintegral", Context); 1138 std::string DataLayout = M.getDataLayoutStr(); 1139 if (!DataLayout.empty()) 1140 DataLayout += "-"; 1141 DataLayout += "ni:10"; 1142 NIM.setDataLayout(DataLayout); 1143 1144 Type *T_int64 = Type::getInt64Ty(Context); 1145 Type *T_pint64 = T_int64->getPointerTo(10); 1146 1147 FunctionType *FTy = 1148 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 1149 Function *F = cast<Function>(NIM.getOrInsertFunction("foo", FTy)); 1150 1151 BasicBlock *Top = BasicBlock::Create(Context, "top", F); 1152 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F); 1153 BasicBlock *L = BasicBlock::Create(Context, "L", F); 1154 BasicBlock *Post = BasicBlock::Create(Context, "post", F); 1155 1156 IRBuilder<> Builder(Top); 1157 Builder.CreateBr(LPh); 1158 1159 Builder.SetInsertPoint(LPh); 1160 Builder.CreateBr(L); 1161 1162 Builder.SetInsertPoint(L); 1163 PHINode *Phi = Builder.CreatePHI(T_int64, 2); 1164 auto *Add = cast<Instruction>( 1165 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add")); 1166 auto *Limit = ConstantInt::get(T_int64, 1000); 1167 auto *Cond = cast<Instruction>( 1168 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond")); 1169 Builder.CreateCondBr(Cond, L, Post); 1170 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh); 1171 Phi->addIncoming(Add, L); 1172 1173 Builder.SetInsertPoint(Post); 1174 Builder.CreateRetVoid(); 1175 1176 ScalarEvolution SE = buildSE(*F); 1177 const SCEV *S = SE.getSCEV(Phi); 1178 EXPECT_TRUE(isa<SCEVAddRecExpr>(S)); 1179 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S); 1180 EXPECT_TRUE(AR->isAffine()); 1181 EXPECT_FALSE(isSafeToExpandAt(AR, Top->getTerminator(), SE)); 1182 EXPECT_FALSE(isSafeToExpandAt(AR, LPh->getTerminator(), SE)); 1183 EXPECT_TRUE(isSafeToExpandAt(AR, L->getTerminator(), SE)); 1184 EXPECT_TRUE(isSafeToExpandAt(AR, Post->getTerminator(), SE)); 1185 } 1186 1187 // Check that SCEV expander does not use the nuw instruction 1188 // for expansion. 1189 TEST_F(ScalarEvolutionsTest, SCEVExpanderNUW) { 1190 /* 1191 * Create the following code: 1192 * func(i64 %a) 1193 * entry: 1194 * br false, label %exit, label %body 1195 * body: 1196 * %s1 = add i64 %a, -1 1197 * br label %exit 1198 * exit: 1199 * %s = add nuw i64 %a, -1 1200 * ret %s 1201 */ 1202 1203 // Create a module. 1204 Module M("SCEVExpanderNUW", Context); 1205 1206 Type *T_int64 = Type::getInt64Ty(Context); 1207 1208 FunctionType *FTy = 1209 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false); 1210 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy)); 1211 Argument *Arg = &*F->arg_begin(); 1212 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1)); 1213 1214 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1215 BasicBlock *Body = BasicBlock::Create(Context, "body", F); 1216 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F); 1217 1218 IRBuilder<> Builder(Entry); 1219 ConstantInt *Cond = ConstantInt::get(Context, APInt(1, 0)); 1220 Builder.CreateCondBr(Cond, Exit, Body); 1221 1222 Builder.SetInsertPoint(Body); 1223 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1224 Builder.CreateBr(Exit); 1225 1226 Builder.SetInsertPoint(Exit); 1227 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1228 S2->setHasNoUnsignedWrap(true); 1229 auto *R = cast<Instruction>(Builder.CreateRetVoid()); 1230 1231 ScalarEvolution SE = buildSE(*F); 1232 const SCEV *S = SE.getSCEV(S1); 1233 EXPECT_TRUE(isa<SCEVAddExpr>(S)); 1234 SCEVExpander Exp(SE, M.getDataLayout(), "expander"); 1235 auto *I = cast<Instruction>(Exp.expandCodeFor(S, nullptr, R)); 1236 EXPECT_FALSE(I->hasNoUnsignedWrap()); 1237 } 1238 1239 // Check that SCEV expander does not use the nsw instruction 1240 // for expansion. 1241 TEST_F(ScalarEvolutionsTest, SCEVExpanderNSW) { 1242 /* 1243 * Create the following code: 1244 * func(i64 %a) 1245 * entry: 1246 * br false, label %exit, label %body 1247 * body: 1248 * %s1 = add i64 %a, -1 1249 * br label %exit 1250 * exit: 1251 * %s = add nsw i64 %a, -1 1252 * ret %s 1253 */ 1254 1255 // Create a module. 1256 Module M("SCEVExpanderNSW", Context); 1257 1258 Type *T_int64 = Type::getInt64Ty(Context); 1259 1260 FunctionType *FTy = 1261 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false); 1262 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy)); 1263 Argument *Arg = &*F->arg_begin(); 1264 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1)); 1265 1266 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1267 BasicBlock *Body = BasicBlock::Create(Context, "body", F); 1268 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F); 1269 1270 IRBuilder<> Builder(Entry); 1271 ConstantInt *Cond = ConstantInt::get(Context, APInt(1, 0)); 1272 Builder.CreateCondBr(Cond, Exit, Body); 1273 1274 Builder.SetInsertPoint(Body); 1275 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1276 Builder.CreateBr(Exit); 1277 1278 Builder.SetInsertPoint(Exit); 1279 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1280 S2->setHasNoSignedWrap(true); 1281 auto *R = cast<Instruction>(Builder.CreateRetVoid()); 1282 1283 ScalarEvolution SE = buildSE(*F); 1284 const SCEV *S = SE.getSCEV(S1); 1285 EXPECT_TRUE(isa<SCEVAddExpr>(S)); 1286 SCEVExpander Exp(SE, M.getDataLayout(), "expander"); 1287 auto *I = cast<Instruction>(Exp.expandCodeFor(S, nullptr, R)); 1288 EXPECT_FALSE(I->hasNoSignedWrap()); 1289 } 1290 1291 // Check that SCEV does not save the SCEV -> V 1292 // mapping of SCEV differ from V in NUW flag. 1293 TEST_F(ScalarEvolutionsTest, SCEVCacheNUW) { 1294 /* 1295 * Create the following code: 1296 * func(i64 %a) 1297 * entry: 1298 * %s1 = add i64 %a, -1 1299 * %s2 = add nuw i64 %a, -1 1300 * br label %exit 1301 * exit: 1302 * ret %s 1303 */ 1304 1305 // Create a module. 1306 Module M("SCEVCacheNUW", Context); 1307 1308 Type *T_int64 = Type::getInt64Ty(Context); 1309 1310 FunctionType *FTy = 1311 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false); 1312 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy)); 1313 Argument *Arg = &*F->arg_begin(); 1314 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1)); 1315 1316 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1317 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F); 1318 1319 IRBuilder<> Builder(Entry); 1320 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1321 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1322 S2->setHasNoUnsignedWrap(true); 1323 Builder.CreateBr(Exit); 1324 1325 Builder.SetInsertPoint(Exit); 1326 auto *R = cast<Instruction>(Builder.CreateRetVoid()); 1327 1328 ScalarEvolution SE = buildSE(*F); 1329 // Get S2 first to move it to cache. 1330 const SCEV *SC2 = SE.getSCEV(S2); 1331 EXPECT_TRUE(isa<SCEVAddExpr>(SC2)); 1332 // Now get S1. 1333 const SCEV *SC1 = SE.getSCEV(S1); 1334 EXPECT_TRUE(isa<SCEVAddExpr>(SC1)); 1335 // Expand for S1, it should use S1 not S2 in spite S2 1336 // first in the cache. 1337 SCEVExpander Exp(SE, M.getDataLayout(), "expander"); 1338 auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R)); 1339 EXPECT_FALSE(I->hasNoUnsignedWrap()); 1340 } 1341 1342 // Check that SCEV does not save the SCEV -> V 1343 // mapping of SCEV differ from V in NSW flag. 1344 TEST_F(ScalarEvolutionsTest, SCEVCacheNSW) { 1345 /* 1346 * Create the following code: 1347 * func(i64 %a) 1348 * entry: 1349 * %s1 = add i64 %a, -1 1350 * %s2 = add nsw i64 %a, -1 1351 * br label %exit 1352 * exit: 1353 * ret %s 1354 */ 1355 1356 // Create a module. 1357 Module M("SCEVCacheNUW", Context); 1358 1359 Type *T_int64 = Type::getInt64Ty(Context); 1360 1361 FunctionType *FTy = 1362 FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false); 1363 Function *F = cast<Function>(M.getOrInsertFunction("func", FTy)); 1364 Argument *Arg = &*F->arg_begin(); 1365 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1)); 1366 1367 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F); 1368 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F); 1369 1370 IRBuilder<> Builder(Entry); 1371 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1372 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add")); 1373 S2->setHasNoSignedWrap(true); 1374 Builder.CreateBr(Exit); 1375 1376 Builder.SetInsertPoint(Exit); 1377 auto *R = cast<Instruction>(Builder.CreateRetVoid()); 1378 1379 ScalarEvolution SE = buildSE(*F); 1380 // Get S2 first to move it to cache. 1381 const SCEV *SC2 = SE.getSCEV(S2); 1382 EXPECT_TRUE(isa<SCEVAddExpr>(SC2)); 1383 // Now get S1. 1384 const SCEV *SC1 = SE.getSCEV(S1); 1385 EXPECT_TRUE(isa<SCEVAddExpr>(SC1)); 1386 // Expand for S1, it should use S1 not S2 in spite S2 1387 // first in the cache. 1388 SCEVExpander Exp(SE, M.getDataLayout(), "expander"); 1389 auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R)); 1390 EXPECT_FALSE(I->hasNoSignedWrap()); 1391 } 1392 1393 } // end anonymous namespace 1394 } // end namespace llvm 1395