991 lines · cpp
1//=== ScalarEvolutionExpanderTest.cpp - ScalarEvolutionExpander 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"10#include "llvm/ADT/SmallVector.h"11#include "llvm/Analysis/AssumptionCache.h"12#include "llvm/Analysis/LoopInfo.h"13#include "llvm/Analysis/ScalarEvolutionExpressions.h"14#include "llvm/Analysis/TargetLibraryInfo.h"15#include "llvm/AsmParser/Parser.h"16#include "llvm/IR/Constants.h"17#include "llvm/IR/Dominators.h"18#include "llvm/IR/GlobalVariable.h"19#include "llvm/IR/IRBuilder.h"20#include "llvm/IR/InstIterator.h"21#include "llvm/IR/LLVMContext.h"22#include "llvm/IR/Module.h"23#include "llvm/IR/PatternMatch.h"24#include "llvm/IR/Verifier.h"25#include "llvm/Support/SourceMgr.h"26#include "gtest/gtest.h"27 28namespace llvm {29 30using namespace PatternMatch;31 32// We use this fixture to ensure that we clean up ScalarEvolution before33// deleting the PassManager.34class ScalarEvolutionExpanderTest : public testing::Test {35protected: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 ScalarEvolutionExpanderTest()46 : M("", Context), TLII(M.getTargetTriple()), TLI(TLII) {}47 48 ScalarEvolution buildSE(Function &F) {49 AC.reset(new AssumptionCache(F));50 DT.reset(new DominatorTree(F));51 LI.reset(new LoopInfo(*DT));52 return ScalarEvolution(F, TLI, *AC, *DT, *LI);53 }54 55 void runWithSE(56 Module &M, StringRef FuncName,57 function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {58 auto *F = M.getFunction(FuncName);59 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;60 ScalarEvolution SE = buildSE(*F);61 Test(*F, *LI, SE);62 }63};64 65static Instruction &GetInstByName(Function &F, StringRef Name) {66 for (auto &I : instructions(F))67 if (I.getName() == Name)68 return I;69 llvm_unreachable("Could not find instructions!");70}71 72TEST_F(ScalarEvolutionExpanderTest, ExpandPtrTypeSCEV) {73 // It is to test the fix for PR30213. It exercises the branch in scev74 // expansion when the value in ValueOffsetPair is a ptr and the offset75 // is not divisible by the elem type size of value.76 auto *I8Ty = Type::getInt8Ty(Context);77 auto *PtrTy = PointerType::get(Context, 0);78 auto *I32Ty = Type::getInt32Ty(Context);79 FunctionType *FTy =80 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);81 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);82 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);83 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);84 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);85 BranchInst::Create(LoopBB, EntryBB);86 ReturnInst::Create(Context, nullptr, ExitBB);87 88 // loop: ; preds = %loop, %entry89 // %alloca = alloca i3290 // %gep0 = getelementptr i32, ptr %alloca, i32 191 // %gep1 = getelementptr i8, ptr %gep0, i32 192 // %gep2 = getelementptr i8, ptr undef, i32 193 // %cmp = icmp ult ptr undef, %gep094 // %select = select i1 %cmp, ptr %gep1, ptr %gep295 // br i1 undef, label %loop, label %exit96 97 const DataLayout &DL = F->getDataLayout();98 BranchInst *Br = BranchInst::Create(99 LoopBB, ExitBB, PoisonValue::get(Type::getInt1Ty(Context)), LoopBB);100 AllocaInst *Alloca = new AllocaInst(I32Ty, DL.getAllocaAddrSpace(), "alloca",101 Br->getIterator());102 ConstantInt *Ci32 = ConstantInt::get(Context, APInt(32, 1));103 UndefValue *UndefPtr = UndefValue::get(PtrTy);104 GetElementPtrInst *Gep0 =105 GetElementPtrInst::Create(I32Ty, Alloca, Ci32, "gep0", Br->getIterator());106 GetElementPtrInst *Gep1 =107 GetElementPtrInst::Create(I8Ty, Gep0, Ci32, "gep1", Br->getIterator());108 GetElementPtrInst *Gep2 = GetElementPtrInst::Create(109 I8Ty, UndefPtr, Ci32, "gep2", Br->getIterator());110 CmpInst *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT,111 UndefPtr, Gep0, "cmp", Br->getIterator());112 SelectInst *Select =113 SelectInst::Create(Cmp, Gep1, Gep2, "select", Br->getIterator());114 115 ScalarEvolution SE = buildSE(*F);116 const SCEV *S = SE.getSCEV(Select);117 EXPECT_TRUE(isa<SCEVUnknown>(S));118}119 120// Make sure that SCEV doesn't introduce illegal ptrtoint/inttoptr instructions121TEST_F(ScalarEvolutionExpanderTest, SCEVZeroExtendExprNonIntegral) {122 /*123 * Create the following code:124 * func(ptr addrspace(10) %arg)125 * top:126 * br label %L.ph127 * L.ph:128 * %gepbase = getelementptr ptr addrspace(10) %arg, i64 1129 * br label %L130 * L:131 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]132 * %add = add i64 %phi2, 1133 * br i1 undef, label %post, label %L2134 * post:135 * #= %gep = getelementptr ptr addrspace(10) %gepbase, i64 %add =#136 * ret void137 *138 * We will create the appropriate SCEV expression for %gep and expand it,139 * then check that no inttoptr/ptrtoint instructions got inserted.140 */141 142 // Create a module with non-integral pointers in it's datalayout143 Module NIM("nonintegral", Context);144 std::string DataLayout = M.getDataLayoutStr();145 if (!DataLayout.empty())146 DataLayout += "-";147 DataLayout += "ni:10";148 NIM.setDataLayout(DataLayout);149 150 Type *T_int1 = Type::getInt1Ty(Context);151 Type *T_int64 = Type::getInt64Ty(Context);152 Type *T_pint64 = PointerType::get(Context, 10);153 154 FunctionType *FTy =155 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);156 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);157 158 Argument *Arg = &*F->arg_begin();159 160 BasicBlock *Top = BasicBlock::Create(Context, "top", F);161 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);162 BasicBlock *L = BasicBlock::Create(Context, "L", F);163 BasicBlock *Post = BasicBlock::Create(Context, "post", F);164 165 IRBuilder<> Builder(Top);166 Builder.CreateBr(LPh);167 168 Builder.SetInsertPoint(LPh);169 Value *GepBase =170 Builder.CreateGEP(T_int64, Arg, ConstantInt::get(T_int64, 1));171 Builder.CreateBr(L);172 173 Builder.SetInsertPoint(L);174 PHINode *Phi = Builder.CreatePHI(T_int64, 2);175 Value *Add = Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add");176 Builder.CreateCondBr(PoisonValue::get(T_int1), L, Post);177 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);178 Phi->addIncoming(Add, L);179 180 Builder.SetInsertPoint(Post);181 Instruction *Ret = Builder.CreateRetVoid();182 183 ScalarEvolution SE = buildSE(*F);184 const SCEV *AddRec =185 SE.getAddRecExpr(SE.getUnknown(GepBase), SE.getConstant(T_int64, 1),186 LI->getLoopFor(L), SCEV::FlagNUW);187 188 SCEVExpander Exp(SE, NIM.getDataLayout(), "expander");189 Exp.disableCanonicalMode();190 Exp.expandCodeFor(AddRec, T_pint64, Ret);191 192 // Make sure none of the instructions inserted were inttoptr/ptrtoint.193 // The verifier will check this.194 EXPECT_FALSE(verifyFunction(*F, &errs()));195}196 197// Check that we can correctly identify the points at which the SCEV of the198// AddRec can be expanded.199TEST_F(ScalarEvolutionExpanderTest, SCEVExpanderIsSafeToExpandAt) {200 /*201 * Create the following code:202 * func(ptr addrspace(10) %arg)203 * top:204 * br label %L.ph205 * L.ph:206 * br label %L207 * L:208 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]209 * %add = add i64 %phi2, 1210 * %cond = icmp slt i64 %add, 1000; then becomes 2000.211 * br i1 %cond, label %post, label %L2212 * post:213 * ret void214 *215 */216 217 // Create a module with non-integral pointers in it's datalayout218 Module NIM("nonintegral", Context);219 std::string DataLayout = M.getDataLayoutStr();220 if (!DataLayout.empty())221 DataLayout += "-";222 DataLayout += "ni:10";223 NIM.setDataLayout(DataLayout);224 225 Type *T_int64 = Type::getInt64Ty(Context);226 Type *T_pint64 = PointerType::get(Context, 10);227 228 FunctionType *FTy =229 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);230 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);231 232 BasicBlock *Top = BasicBlock::Create(Context, "top", F);233 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);234 BasicBlock *L = BasicBlock::Create(Context, "L", F);235 BasicBlock *Post = BasicBlock::Create(Context, "post", F);236 237 IRBuilder<> Builder(Top);238 Builder.CreateBr(LPh);239 240 Builder.SetInsertPoint(LPh);241 Builder.CreateBr(L);242 243 Builder.SetInsertPoint(L);244 PHINode *Phi = Builder.CreatePHI(T_int64, 2);245 auto *Add = cast<Instruction>(246 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));247 auto *Limit = ConstantInt::get(T_int64, 1000);248 auto *Cond = cast<Instruction>(249 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));250 Builder.CreateCondBr(Cond, L, Post);251 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);252 Phi->addIncoming(Add, L);253 254 Builder.SetInsertPoint(Post);255 Instruction *Ret = Builder.CreateRetVoid();256 257 ScalarEvolution SE = buildSE(*F);258 SCEVExpander Exp(SE, M.getDataLayout(), "expander");259 const SCEV *S = SE.getSCEV(Phi);260 EXPECT_TRUE(isa<SCEVAddRecExpr>(S));261 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);262 EXPECT_TRUE(AR->isAffine());263 EXPECT_FALSE(Exp.isSafeToExpandAt(AR, Top->getTerminator()));264 EXPECT_FALSE(Exp.isSafeToExpandAt(AR, LPh->getTerminator()));265 EXPECT_TRUE(Exp.isSafeToExpandAt(AR, L->getTerminator()));266 EXPECT_TRUE(Exp.isSafeToExpandAt(AR, Post->getTerminator()));267 268 EXPECT_TRUE(LI->getLoopFor(L)->isLCSSAForm(*DT));269 Exp.expandCodeFor(SE.getSCEV(Add), nullptr, Ret);270 EXPECT_TRUE(LI->getLoopFor(L)->isLCSSAForm(*DT));271}272 273// Check that SCEV expander does not use the nuw instruction274// for expansion.275TEST_F(ScalarEvolutionExpanderTest, SCEVExpanderNUW) {276 /*277 * Create the following code:278 * func(i64 %a)279 * entry:280 * br false, label %exit, label %body281 * body:282 * %s1 = add i64 %a, -1283 * br label %exit284 * exit:285 * %s = add nuw i64 %a, -1286 * ret %s287 */288 289 // Create a module.290 Module M("SCEVExpanderNUW", Context);291 292 Type *T_int64 = Type::getInt64Ty(Context);293 294 FunctionType *FTy =295 FunctionType::get(Type::getVoidTy(Context), {T_int64}, false);296 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M);297 Argument *Arg = &*F->arg_begin();298 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));299 300 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);301 BasicBlock *Body = BasicBlock::Create(Context, "body", F);302 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);303 304 IRBuilder<> Builder(Entry);305 ConstantInt *Cond = ConstantInt::get(Context, APInt(1, 0));306 Builder.CreateCondBr(Cond, Exit, Body);307 308 Builder.SetInsertPoint(Body);309 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));310 Builder.CreateBr(Exit);311 312 Builder.SetInsertPoint(Exit);313 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));314 S2->setHasNoUnsignedWrap(true);315 auto *R = cast<Instruction>(Builder.CreateRetVoid());316 317 ScalarEvolution SE = buildSE(*F);318 const SCEV *S = SE.getSCEV(S1);319 EXPECT_TRUE(isa<SCEVAddExpr>(S));320 SCEVExpander Exp(SE, M.getDataLayout(), "expander");321 auto *I = cast<Instruction>(Exp.expandCodeFor(S, nullptr, R));322 EXPECT_FALSE(I->hasNoUnsignedWrap());323}324 325// Check that SCEV expander does not use the nsw instruction326// for expansion.327TEST_F(ScalarEvolutionExpanderTest, SCEVExpanderNSW) {328 /*329 * Create the following code:330 * func(i64 %a)331 * entry:332 * br false, label %exit, label %body333 * body:334 * %s1 = add i64 %a, -1335 * br label %exit336 * exit:337 * %s = add nsw i64 %a, -1338 * ret %s339 */340 341 // Create a module.342 Module M("SCEVExpanderNSW", Context);343 344 Type *T_int64 = Type::getInt64Ty(Context);345 346 FunctionType *FTy =347 FunctionType::get(Type::getVoidTy(Context), {T_int64}, false);348 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M);349 Argument *Arg = &*F->arg_begin();350 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));351 352 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);353 BasicBlock *Body = BasicBlock::Create(Context, "body", F);354 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);355 356 IRBuilder<> Builder(Entry);357 ConstantInt *Cond = ConstantInt::get(Context, APInt(1, 0));358 Builder.CreateCondBr(Cond, Exit, Body);359 360 Builder.SetInsertPoint(Body);361 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));362 Builder.CreateBr(Exit);363 364 Builder.SetInsertPoint(Exit);365 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));366 S2->setHasNoSignedWrap(true);367 auto *R = cast<Instruction>(Builder.CreateRetVoid());368 369 ScalarEvolution SE = buildSE(*F);370 const SCEV *S = SE.getSCEV(S1);371 EXPECT_TRUE(isa<SCEVAddExpr>(S));372 SCEVExpander Exp(SE, M.getDataLayout(), "expander");373 auto *I = cast<Instruction>(Exp.expandCodeFor(S, nullptr, R));374 EXPECT_FALSE(I->hasNoSignedWrap());375}376 377// Check that SCEV does not save the SCEV -> V378// mapping of SCEV differ from V in NUW flag.379TEST_F(ScalarEvolutionExpanderTest, SCEVCacheNUW) {380 /*381 * Create the following code:382 * func(i64 %a)383 * entry:384 * %s1 = add i64 %a, -1385 * %s2 = add nuw i64 %a, -1386 * br label %exit387 * exit:388 * ret %s389 */390 391 // Create a module.392 Module M("SCEVCacheNUW", Context);393 394 Type *T_int64 = Type::getInt64Ty(Context);395 396 FunctionType *FTy =397 FunctionType::get(Type::getVoidTy(Context), {T_int64}, false);398 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M);399 Argument *Arg = &*F->arg_begin();400 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));401 402 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);403 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);404 405 IRBuilder<> Builder(Entry);406 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));407 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));408 S2->setHasNoUnsignedWrap(true);409 Builder.CreateBr(Exit);410 411 Builder.SetInsertPoint(Exit);412 auto *R = cast<Instruction>(Builder.CreateRetVoid());413 414 ScalarEvolution SE = buildSE(*F);415 // Get S2 first to move it to cache.416 const SCEV *SC2 = SE.getSCEV(S2);417 EXPECT_TRUE(isa<SCEVAddExpr>(SC2));418 // Now get S1.419 const SCEV *SC1 = SE.getSCEV(S1);420 EXPECT_TRUE(isa<SCEVAddExpr>(SC1));421 // Expand for S1, it should use S1 not S2 in spite S2422 // first in the cache.423 SCEVExpander Exp(SE, M.getDataLayout(), "expander");424 auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));425 EXPECT_FALSE(I->hasNoUnsignedWrap());426}427 428// Check that SCEV does not save the SCEV -> V429// mapping of SCEV differ from V in NSW flag.430TEST_F(ScalarEvolutionExpanderTest, SCEVCacheNSW) {431 /*432 * Create the following code:433 * func(i64 %a)434 * entry:435 * %s1 = add i64 %a, -1436 * %s2 = add nsw i64 %a, -1437 * br label %exit438 * exit:439 * ret %s440 */441 442 // Create a module.443 Module M("SCEVCacheNUW", Context);444 445 Type *T_int64 = Type::getInt64Ty(Context);446 447 FunctionType *FTy =448 FunctionType::get(Type::getVoidTy(Context), {T_int64}, false);449 Function *F = Function::Create(FTy, Function::ExternalLinkage, "func", M);450 Argument *Arg = &*F->arg_begin();451 ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));452 453 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);454 BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);455 456 IRBuilder<> Builder(Entry);457 auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));458 auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));459 S2->setHasNoSignedWrap(true);460 Builder.CreateBr(Exit);461 462 Builder.SetInsertPoint(Exit);463 auto *R = cast<Instruction>(Builder.CreateRetVoid());464 465 ScalarEvolution SE = buildSE(*F);466 // Get S2 first to move it to cache.467 const SCEV *SC2 = SE.getSCEV(S2);468 EXPECT_TRUE(isa<SCEVAddExpr>(SC2));469 // Now get S1.470 const SCEV *SC1 = SE.getSCEV(S1);471 EXPECT_TRUE(isa<SCEVAddExpr>(SC1));472 // Expand for S1, it should use S1 not S2 in spite S2473 // first in the cache.474 SCEVExpander Exp(SE, M.getDataLayout(), "expander");475 auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));476 EXPECT_FALSE(I->hasNoSignedWrap());477}478 479TEST_F(ScalarEvolutionExpanderTest, SCEVExpandInsertCanonicalIV) {480 LLVMContext C;481 SMDiagnostic Err;482 483 // Expand the addrec produced by GetAddRec into a loop without a canonical IV.484 // SCEVExpander will insert one.485 auto TestNoCanonicalIV =486 [&](std::function<const SCEV *(ScalarEvolution & SE, Loop * L)>487 GetAddRec) {488 std::unique_ptr<Module> M = parseAssemblyString(489 "define i32 @test(i32 %limit) { "490 "entry: "491 " br label %loop "492 "loop: "493 " %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "494 " %i.inc = add nsw i32 %i, 1 "495 " %cont = icmp slt i32 %i.inc, %limit "496 " br i1 %cont, label %loop, label %exit "497 "exit: "498 " ret i32 %i.inc "499 "}",500 Err, C);501 502 assert(M && "Could not parse module?");503 assert(!verifyModule(*M) && "Must have been well formed!");504 505 runWithSE(506 *M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {507 auto &I = GetInstByName(F, "i");508 auto *Loop = LI.getLoopFor(I.getParent());509 EXPECT_FALSE(Loop->getCanonicalInductionVariable());510 511 auto *AR = GetAddRec(SE, Loop);512 unsigned ExpectedCanonicalIVWidth =513 SE.getTypeSizeInBits(AR->getType());514 515 SCEVExpander Exp(SE, M->getDataLayout(), "expander");516 auto *InsertAt = I.getNextNode();517 Exp.expandCodeFor(AR, nullptr, InsertAt);518 PHINode *CanonicalIV = Loop->getCanonicalInductionVariable();519 unsigned CanonicalIVBitWidth =520 cast<IntegerType>(CanonicalIV->getType())->getBitWidth();521 EXPECT_EQ(CanonicalIVBitWidth, ExpectedCanonicalIVWidth);522 });523 };524 525 // Expand the addrec produced by GetAddRec into a loop with a canonical IV526 // which is narrower than addrec type.527 // SCEVExpander will insert a canonical IV of a wider type to expand the528 // addrec.529 auto TestNarrowCanonicalIV = [&](std::function<const SCEV *(530 ScalarEvolution & SE, Loop * L)>531 GetAddRec) {532 std::unique_ptr<Module> M = parseAssemblyString(533 "define i32 @test(i32 %limit) { "534 "entry: "535 " br label %loop "536 "loop: "537 " %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "538 " %canonical.iv = phi i8 [ 0, %entry ], [ %canonical.iv.inc, %loop ] "539 " %i.inc = add nsw i32 %i, 1 "540 " %canonical.iv.inc = add i8 %canonical.iv, 1 "541 " %cont = icmp slt i32 %i.inc, %limit "542 " br i1 %cont, label %loop, label %exit "543 "exit: "544 " ret i32 %i.inc "545 "}",546 Err, C);547 548 assert(M && "Could not parse module?");549 assert(!verifyModule(*M) && "Must have been well formed!");550 551 runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {552 auto &I = GetInstByName(F, "i");553 554 auto *LoopHeaderBB = I.getParent();555 auto *Loop = LI.getLoopFor(LoopHeaderBB);556 PHINode *CanonicalIV = Loop->getCanonicalInductionVariable();557 EXPECT_EQ(CanonicalIV, &GetInstByName(F, "canonical.iv"));558 559 auto *AR = GetAddRec(SE, Loop);560 561 unsigned ExpectedCanonicalIVWidth = SE.getTypeSizeInBits(AR->getType());562 unsigned CanonicalIVBitWidth =563 cast<IntegerType>(CanonicalIV->getType())->getBitWidth();564 EXPECT_LT(CanonicalIVBitWidth, ExpectedCanonicalIVWidth);565 566 SCEVExpander Exp(SE, M->getDataLayout(), "expander");567 auto *InsertAt = I.getNextNode();568 Exp.expandCodeFor(AR, nullptr, InsertAt);569 570 // Loop over all of the PHI nodes, looking for the new canonical indvar.571 PHINode *NewCanonicalIV = nullptr;572 for (BasicBlock::iterator i = LoopHeaderBB->begin(); isa<PHINode>(i);573 ++i) {574 PHINode *PN = cast<PHINode>(i);575 if (PN == &I || PN == CanonicalIV)576 continue;577 // We expect that the only PHI added is the new canonical IV578 EXPECT_FALSE(NewCanonicalIV);579 NewCanonicalIV = PN;580 }581 582 // Check that NewCanonicalIV is a canonical IV, i.e {0,+,1}583 BasicBlock *Incoming = nullptr, *Backedge = nullptr;584 EXPECT_TRUE(Loop->getIncomingAndBackEdge(Incoming, Backedge));585 auto *Start = NewCanonicalIV->getIncomingValueForBlock(Incoming);586 EXPECT_TRUE(isa<ConstantInt>(Start));587 EXPECT_TRUE(dyn_cast<ConstantInt>(Start)->isZero());588 auto *Next = NewCanonicalIV->getIncomingValueForBlock(Backedge);589 EXPECT_TRUE(isa<BinaryOperator>(Next));590 auto *NextBinOp = dyn_cast<BinaryOperator>(Next);591 EXPECT_EQ(NextBinOp->getOpcode(), Instruction::Add);592 EXPECT_EQ(NextBinOp->getOperand(0), NewCanonicalIV);593 auto *Step = NextBinOp->getOperand(1);594 EXPECT_TRUE(isa<ConstantInt>(Step));595 EXPECT_TRUE(dyn_cast<ConstantInt>(Step)->isOne());596 597 unsigned NewCanonicalIVBitWidth =598 cast<IntegerType>(NewCanonicalIV->getType())->getBitWidth();599 EXPECT_EQ(NewCanonicalIVBitWidth, ExpectedCanonicalIVWidth);600 });601 };602 603 // Expand the addrec produced by GetAddRec into a loop with a canonical IV604 // of addrec width.605 // To expand the addrec SCEVExpander should use the existing canonical IV.606 auto TestMatchingCanonicalIV =607 [&](std::function<const SCEV *(ScalarEvolution & SE, Loop * L)> GetAddRec,608 unsigned ARBitWidth) {609 auto ARBitWidthTypeStr = "i" + std::to_string(ARBitWidth);610 std::unique_ptr<Module> M = parseAssemblyString(611 "define i32 @test(i32 %limit) { "612 "entry: "613 " br label %loop "614 "loop: "615 " %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "616 " %canonical.iv = phi " +617 ARBitWidthTypeStr +618 " [ 0, %entry ], [ %canonical.iv.inc, %loop ] "619 " %i.inc = add nsw i32 %i, 1 "620 " %canonical.iv.inc = add " +621 ARBitWidthTypeStr +622 " %canonical.iv, 1 "623 " %cont = icmp slt i32 %i.inc, %limit "624 " br i1 %cont, label %loop, label %exit "625 "exit: "626 " ret i32 %i.inc "627 "}",628 Err, C);629 630 assert(M && "Could not parse module?");631 assert(!verifyModule(*M) && "Must have been well formed!");632 633 runWithSE(634 *M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {635 auto &I = GetInstByName(F, "i");636 auto &CanonicalIV = GetInstByName(F, "canonical.iv");637 638 auto *LoopHeaderBB = I.getParent();639 auto *Loop = LI.getLoopFor(LoopHeaderBB);640 EXPECT_EQ(&CanonicalIV, Loop->getCanonicalInductionVariable());641 unsigned CanonicalIVBitWidth =642 cast<IntegerType>(CanonicalIV.getType())->getBitWidth();643 644 auto *AR = GetAddRec(SE, Loop);645 EXPECT_EQ(ARBitWidth, SE.getTypeSizeInBits(AR->getType()));646 EXPECT_EQ(CanonicalIVBitWidth, ARBitWidth);647 648 SCEVExpander Exp(SE, M->getDataLayout(), "expander");649 auto *InsertAt = I.getNextNode();650 Exp.expandCodeFor(AR, nullptr, InsertAt);651 652 // Loop over all of the PHI nodes, looking if a new canonical653 // indvar was introduced.654 PHINode *NewCanonicalIV = nullptr;655 for (BasicBlock::iterator i = LoopHeaderBB->begin();656 isa<PHINode>(i); ++i) {657 PHINode *PN = cast<PHINode>(i);658 if (PN == &I || PN == &CanonicalIV)659 continue;660 NewCanonicalIV = PN;661 }662 EXPECT_FALSE(NewCanonicalIV);663 });664 };665 666 unsigned ARBitWidth = 16;667 Type *ARType = IntegerType::get(C, ARBitWidth);668 669 // Expand {5,+,1}670 auto GetAR2 = [&](ScalarEvolution &SE, Loop *L) -> const SCEV * {671 return SE.getAddRecExpr(SE.getConstant(APInt(ARBitWidth, 5)),672 SE.getOne(ARType), L, SCEV::FlagAnyWrap);673 };674 TestNoCanonicalIV(GetAR2);675 TestNarrowCanonicalIV(GetAR2);676 TestMatchingCanonicalIV(GetAR2, ARBitWidth);677}678 679TEST_F(ScalarEvolutionExpanderTest, SCEVExpanderShlNSW) {680 681 auto checkOneCase = [this](std::string &&str) {682 LLVMContext C;683 SMDiagnostic Err;684 std::unique_ptr<Module> M = parseAssemblyString(str, Err, C);685 686 assert(M && "Could not parse module?");687 assert(!verifyModule(*M) && "Must have been well formed!");688 689 Function *F = M->getFunction("f");690 ASSERT_NE(F, nullptr) << "Could not find function 'f'";691 692 BasicBlock &Entry = F->getEntryBlock();693 LoadInst *Load = cast<LoadInst>(&Entry.front());694 BinaryOperator *And = cast<BinaryOperator>(*Load->user_begin());695 696 ScalarEvolution SE = buildSE(*F);697 const SCEV *AndSCEV = SE.getSCEV(And);698 EXPECT_TRUE(isa<SCEVMulExpr>(AndSCEV));699 EXPECT_TRUE(cast<SCEVMulExpr>(AndSCEV)->hasNoSignedWrap());700 701 SCEVExpander Exp(SE, M->getDataLayout(), "expander");702 auto *I = cast<Instruction>(Exp.expandCodeFor(AndSCEV, nullptr, And));703 EXPECT_EQ(I->getOpcode(), Instruction::Shl);704 EXPECT_FALSE(I->hasNoSignedWrap());705 };706 707 checkOneCase("define void @f(ptr %arrayidx) { "708 " %1 = load i16, ptr %arrayidx "709 " %2 = and i16 %1, -32768 "710 " ret void "711 "} ");712 713 checkOneCase("define void @f(ptr %arrayidx) { "714 " %1 = load i8, ptr %arrayidx "715 " %2 = and i8 %1, -128 "716 " ret void "717 "} ");718}719 720// Test expansion of nested addrecs in CanonicalMode.721// Expanding nested addrecs in canonical mode requiers a canonical IV of a722// type wider than the type of the addrec itself. Currently, SCEVExpander723// just falls back to literal mode for nested addrecs.724TEST_F(ScalarEvolutionExpanderTest, SCEVExpandNonAffineAddRec) {725 LLVMContext C;726 SMDiagnostic Err;727 728 // Expand the addrec produced by GetAddRec into a loop without a canonical IV.729 auto TestNoCanonicalIV =730 [&](std::function<const SCEVAddRecExpr *(ScalarEvolution & SE, Loop * L)>731 GetAddRec) {732 std::unique_ptr<Module> M = parseAssemblyString(733 "define i32 @test(i32 %limit) { "734 "entry: "735 " br label %loop "736 "loop: "737 " %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "738 " %i.inc = add nsw i32 %i, 1 "739 " %cont = icmp slt i32 %i.inc, %limit "740 " br i1 %cont, label %loop, label %exit "741 "exit: "742 " ret i32 %i.inc "743 "}",744 Err, C);745 746 assert(M && "Could not parse module?");747 assert(!verifyModule(*M) && "Must have been well formed!");748 749 runWithSE(*M, "test",750 [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {751 auto &I = GetInstByName(F, "i");752 auto *Loop = LI.getLoopFor(I.getParent());753 EXPECT_FALSE(Loop->getCanonicalInductionVariable());754 755 auto *AR = GetAddRec(SE, Loop);756 EXPECT_FALSE(AR->isAffine());757 758 SCEVExpander Exp(SE, M->getDataLayout(), "expander");759 auto *InsertAt = I.getNextNode();760 Value *V = Exp.expandCodeFor(AR, nullptr, InsertAt);761 const SCEV *ExpandedAR = SE.getSCEV(V);762 // Check that the expansion happened literally.763 EXPECT_EQ(AR, ExpandedAR);764 });765 };766 767 // Expand the addrec produced by GetAddRec into a loop with a canonical IV768 // which is narrower than addrec type.769 auto TestNarrowCanonicalIV = [&](std::function<const SCEVAddRecExpr *(770 ScalarEvolution & SE, Loop * L)>771 GetAddRec) {772 std::unique_ptr<Module> M = parseAssemblyString(773 "define i32 @test(i32 %limit) { "774 "entry: "775 " br label %loop "776 "loop: "777 " %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "778 " %canonical.iv = phi i8 [ 0, %entry ], [ %canonical.iv.inc, %loop ] "779 " %i.inc = add nsw i32 %i, 1 "780 " %canonical.iv.inc = add i8 %canonical.iv, 1 "781 " %cont = icmp slt i32 %i.inc, %limit "782 " br i1 %cont, label %loop, label %exit "783 "exit: "784 " ret i32 %i.inc "785 "}",786 Err, C);787 788 assert(M && "Could not parse module?");789 assert(!verifyModule(*M) && "Must have been well formed!");790 791 runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {792 auto &I = GetInstByName(F, "i");793 794 auto *LoopHeaderBB = I.getParent();795 auto *Loop = LI.getLoopFor(LoopHeaderBB);796 PHINode *CanonicalIV = Loop->getCanonicalInductionVariable();797 EXPECT_EQ(CanonicalIV, &GetInstByName(F, "canonical.iv"));798 799 auto *AR = GetAddRec(SE, Loop);800 EXPECT_FALSE(AR->isAffine());801 802 unsigned ExpectedCanonicalIVWidth = SE.getTypeSizeInBits(AR->getType());803 unsigned CanonicalIVBitWidth =804 cast<IntegerType>(CanonicalIV->getType())->getBitWidth();805 EXPECT_LT(CanonicalIVBitWidth, ExpectedCanonicalIVWidth);806 807 SCEVExpander Exp(SE, M->getDataLayout(), "expander");808 auto *InsertAt = I.getNextNode();809 Value *V = Exp.expandCodeFor(AR, nullptr, InsertAt);810 const SCEV *ExpandedAR = SE.getSCEV(V);811 // Check that the expansion happened literally.812 EXPECT_EQ(AR, ExpandedAR);813 });814 };815 816 // Expand the addrec produced by GetAddRec into a loop with a canonical IV817 // of addrec width.818 auto TestMatchingCanonicalIV =819 [&](std::function<const SCEVAddRecExpr *(ScalarEvolution & SE, Loop * L)>820 GetAddRec,821 unsigned ARBitWidth) {822 auto ARBitWidthTypeStr = "i" + std::to_string(ARBitWidth);823 std::unique_ptr<Module> M = parseAssemblyString(824 "define i32 @test(i32 %limit) { "825 "entry: "826 " br label %loop "827 "loop: "828 " %i = phi i32 [ 1, %entry ], [ %i.inc, %loop ] "829 " %canonical.iv = phi " +830 ARBitWidthTypeStr +831 " [ 0, %entry ], [ %canonical.iv.inc, %loop ] "832 " %i.inc = add nsw i32 %i, 1 "833 " %canonical.iv.inc = add " +834 ARBitWidthTypeStr +835 " %canonical.iv, 1 "836 " %cont = icmp slt i32 %i.inc, %limit "837 " br i1 %cont, label %loop, label %exit "838 "exit: "839 " ret i32 %i.inc "840 "}",841 Err, C);842 843 assert(M && "Could not parse module?");844 assert(!verifyModule(*M) && "Must have been well formed!");845 846 runWithSE(847 *M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {848 auto &I = GetInstByName(F, "i");849 auto &CanonicalIV = GetInstByName(F, "canonical.iv");850 851 auto *LoopHeaderBB = I.getParent();852 auto *Loop = LI.getLoopFor(LoopHeaderBB);853 EXPECT_EQ(&CanonicalIV, Loop->getCanonicalInductionVariable());854 unsigned CanonicalIVBitWidth =855 cast<IntegerType>(CanonicalIV.getType())->getBitWidth();856 857 auto *AR = GetAddRec(SE, Loop);858 EXPECT_FALSE(AR->isAffine());859 EXPECT_EQ(ARBitWidth, SE.getTypeSizeInBits(AR->getType()));860 EXPECT_EQ(CanonicalIVBitWidth, ARBitWidth);861 862 SCEVExpander Exp(SE, M->getDataLayout(), "expander");863 auto *InsertAt = I.getNextNode();864 Value *V = Exp.expandCodeFor(AR, nullptr, InsertAt);865 const SCEV *ExpandedAR = SE.getSCEV(V);866 // Check that the expansion happened literally.867 EXPECT_EQ(AR, ExpandedAR);868 });869 };870 871 unsigned ARBitWidth = 16;872 Type *ARType = IntegerType::get(C, ARBitWidth);873 874 // Expand {5,+,1,+,1}875 auto GetAR3 = [&](ScalarEvolution &SE, Loop *L) -> const SCEVAddRecExpr * {876 SmallVector<const SCEV *, 3> Ops = {SE.getConstant(APInt(ARBitWidth, 5)),877 SE.getOne(ARType), SE.getOne(ARType)};878 return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, L, SCEV::FlagAnyWrap));879 };880 TestNoCanonicalIV(GetAR3);881 TestNarrowCanonicalIV(GetAR3);882 TestMatchingCanonicalIV(GetAR3, ARBitWidth);883 884 // Expand {5,+,1,+,1,+,1}885 auto GetAR4 = [&](ScalarEvolution &SE, Loop *L) -> const SCEVAddRecExpr * {886 SmallVector<const SCEV *, 4> Ops = {SE.getConstant(APInt(ARBitWidth, 5)),887 SE.getOne(ARType), SE.getOne(ARType),888 SE.getOne(ARType)};889 return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, L, SCEV::FlagAnyWrap));890 };891 TestNoCanonicalIV(GetAR4);892 TestNarrowCanonicalIV(GetAR4);893 TestMatchingCanonicalIV(GetAR4, ARBitWidth);894 895 // Expand {5,+,1,+,1,+,1,+,1}896 auto GetAR5 = [&](ScalarEvolution &SE, Loop *L) -> const SCEVAddRecExpr * {897 SmallVector<const SCEV *, 5> Ops = {SE.getConstant(APInt(ARBitWidth, 5)),898 SE.getOne(ARType), SE.getOne(ARType),899 SE.getOne(ARType), SE.getOne(ARType)};900 return cast<SCEVAddRecExpr>(SE.getAddRecExpr(Ops, L, SCEV::FlagAnyWrap));901 };902 TestNoCanonicalIV(GetAR5);903 TestNarrowCanonicalIV(GetAR5);904 TestMatchingCanonicalIV(GetAR5, ARBitWidth);905}906 907TEST_F(ScalarEvolutionExpanderTest, ExpandNonIntegralPtrWithNullBase) {908 LLVMContext C;909 SMDiagnostic Err;910 911 std::unique_ptr<Module> M =912 parseAssemblyString("target datalayout = "913 "\"e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:"914 "128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2\""915 "define ptr addrspace(1) @test(i64 %offset) { "916 " %ptr = getelementptr inbounds float, ptr "917 "addrspace(1) null, i64 %offset"918 " ret ptr addrspace(1) %ptr"919 "}",920 Err, C);921 922 assert(M && "Could not parse module?");923 assert(!verifyModule(*M) && "Must have been well formed!");924 925 runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {926 auto &I = GetInstByName(F, "ptr");927 auto PtrPlus1 =928 SE.getAddExpr(SE.getSCEV(&I), SE.getConstant(I.getType(), 1));929 SCEVExpander Exp(SE, M->getDataLayout(), "expander");930 931 Value *V = Exp.expandCodeFor(PtrPlus1, I.getType(), &I);932 I.replaceAllUsesWith(V);933 934 // Check that the expander created:935 // define ptr addrspace(1) @test(i64 %off) {936 // %1 = shl i64 %offset, 2937 // %2 = add nuw nsw i64 %1, 1938 // %uglygep = getelementptr i8, ptr addrspace(1) null, i64 %2939 // %ptr = getelementptr inbounds float, ptr addrspace(1) null, i64 %off940 // ret ptr addrspace(1) %uglygep941 // }942 943 Value *Offset = &*F.arg_begin();944 auto *GEP = dyn_cast<GetElementPtrInst>(V);945 EXPECT_TRUE(GEP);946 EXPECT_TRUE(cast<Constant>(GEP->getPointerOperand())->isNullValue());947 EXPECT_EQ(GEP->getNumOperands(), 2U);948 EXPECT_TRUE(match(949 GEP->getOperand(1),950 m_Add(m_Shl(m_Specific(Offset), m_SpecificInt(2)), m_SpecificInt(1))));951 EXPECT_EQ(cast<PointerType>(GEP->getPointerOperand()->getType())952 ->getAddressSpace(),953 cast<PointerType>(I.getType())->getAddressSpace());954 EXPECT_FALSE(verifyFunction(F, &errs()));955 });956}957 958TEST_F(ScalarEvolutionExpanderTest, GEPFlags) {959 LLVMContext C;960 SMDiagnostic Err;961 StringRef ModStr = R"(962 define void @f(ptr %p, i64 %x) {963 %gep_inbounds = getelementptr inbounds i8, ptr %p, i64 %x964 ret void965 })";966 std::unique_ptr<Module> M = parseAssemblyString(ModStr, Err, C);967 968 assert(M && "Could not parse module?");969 assert(!verifyModule(*M) && "Must have been well formed!");970 971 Function *F = M->getFunction("f");972 ASSERT_NE(F, nullptr) << "Could not find function 'f'";973 BasicBlock &Entry = F->getEntryBlock();974 auto *GEP = cast<GetElementPtrInst>(&Entry.front());975 976 ScalarEvolution SE = buildSE(*F);977 const SCEV *Ptr = SE.getSCEV(F->getArg(0));978 const SCEV *X = SE.getSCEV(F->getArg(1));979 const SCEV *PtrX = SE.getAddExpr(Ptr, X);980 981 SCEVExpander Exp(SE, M->getDataLayout(), "expander");982 auto *I = cast<Instruction>(983 Exp.expandCodeFor(PtrX, nullptr, Entry.getTerminator()));984 // Check that the GEP is reused, but the inbounds flag cleared. We don't985 // know that the newly introduced use is inbounds.986 EXPECT_EQ(I, GEP);987 EXPECT_EQ(GEP->getNoWrapFlags(), GEPNoWrapFlags::none());988}989 990} // end namespace llvm991