1907 lines · cpp
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-exception6//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/ScalarEvolutionPatternMatch.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/Module.h"24#include "llvm/IR/Verifier.h"25#include "llvm/Support/SourceMgr.h"26#include "gtest/gtest.h"27 28namespace llvm {29 30using namespace SCEVPatternMatch;31 32// We use this fixture to ensure that we clean up ScalarEvolution before33// deleting the PassManager.34class ScalarEvolutionsTest : 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 ScalarEvolutionsTest()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 64static std::optional<APInt> computeConstantDifference(ScalarEvolution &SE,65 const SCEV *LHS,66 const SCEV *RHS) {67 return SE.computeConstantDifference(LHS, RHS);68}69 70 static bool isImpliedCond(71 ScalarEvolution &SE, ICmpInst::Predicate Pred, const SCEV *LHS,72 const SCEV *RHS, ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,73 const SCEV *FoundRHS) {74 return SE.isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS);75 }76};77 78TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {79 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),80 std::vector<Type *>(), false);81 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);82 BasicBlock *BB = BasicBlock::Create(Context, "entry", F);83 ReturnInst::Create(Context, nullptr, BB);84 85 Type *Ty = Type::getInt1Ty(Context);86 Constant *Init = Constant::getNullValue(Ty);87 Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0");88 Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1");89 Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");90 91 ScalarEvolution SE = buildSE(*F);92 93 const SCEV *S0 = SE.getSCEV(V0);94 const SCEV *S1 = SE.getSCEV(V1);95 const SCEV *S2 = SE.getSCEV(V2);96 97 const SCEV *P0 = SE.getAddExpr(S0, SE.getConstant(S0->getType(), 2));98 const SCEV *P1 = SE.getAddExpr(S1, SE.getConstant(S0->getType(), 2));99 const SCEV *P2 = SE.getAddExpr(S2, SE.getConstant(S0->getType(), 2));100 101 auto *M0 = cast<SCEVAddExpr>(P0);102 auto *M1 = cast<SCEVAddExpr>(P1);103 auto *M2 = cast<SCEVAddExpr>(P2);104 105 EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),106 2u);107 EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),108 2u);109 EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),110 2u);111 112 // Before the RAUWs, these are all pointing to separate values.113 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);114 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1);115 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2);116 117 // Do some RAUWs.118 V2->replaceAllUsesWith(V1);119 V1->replaceAllUsesWith(V0);120 121 // After the RAUWs, these should all be pointing to V0.122 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);123 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0);124 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0);125}126 127TEST_F(ScalarEvolutionsTest, SimplifiedPHI) {128 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),129 std::vector<Type *>(), false);130 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);131 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);132 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);133 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);134 BranchInst::Create(LoopBB, EntryBB);135 BranchInst::Create(LoopBB, ExitBB, PoisonValue::get(Type::getInt1Ty(Context)),136 LoopBB);137 ReturnInst::Create(Context, nullptr, ExitBB);138 auto *Ty = Type::getInt32Ty(Context);139 auto *PN = PHINode::Create(Ty, 2, "", LoopBB->begin());140 PN->addIncoming(Constant::getNullValue(Ty), EntryBB);141 PN->addIncoming(PoisonValue::get(Ty), LoopBB);142 ScalarEvolution SE = buildSE(*F);143 const SCEV *S1 = SE.getSCEV(PN);144 const SCEV *S2 = SE.getSCEV(PN);145 const SCEV *ZeroConst = SE.getConstant(Ty, 0);146 147 // At some point, only the first call to getSCEV returned the simplified148 // SCEVConstant and later calls just returned a SCEVUnknown referencing the149 // PHI node.150 EXPECT_EQ(S1, ZeroConst);151 EXPECT_EQ(S1, S2);152}153 154 155static Instruction *getInstructionByName(Function &F, StringRef Name) {156 for (auto &I : instructions(F))157 if (I.getName() == Name)158 return &I;159 llvm_unreachable("Expected to find instruction!");160}161 162static Value *getArgByName(Function &F, StringRef Name) {163 for (auto &Arg : F.args())164 if (Arg.getName() == Name)165 return &Arg;166 llvm_unreachable("Expected to find instruction!");167}168TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) {169 LLVMContext C;170 SMDiagnostic Err;171 std::unique_ptr<Module> M = parseAssemblyString(172 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "173 " "174 "@var_0 = external global i32, align 4"175 "@var_1 = external global i32, align 4"176 "@var_2 = external global i32, align 4"177 " "178 "declare i32 @unknown(i32, i32, i32)"179 " "180 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "181 " local_unnamed_addr { "182 "entry: "183 " %entrycond = icmp sgt i32 %n, 0 "184 " br i1 %entrycond, label %loop.ph, label %for.end "185 " "186 "loop.ph: "187 " %a = load i32, i32* %A, align 4 "188 " %b = load i32, i32* %B, align 4 "189 " %mul = mul nsw i32 %b, %a "190 " %iv0.init = getelementptr inbounds i8, i8* %arr, i32 %mul "191 " br label %loop "192 " "193 "loop: "194 " %iv0 = phi i8* [ %iv0.inc, %loop ], [ %iv0.init, %loop.ph ] "195 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ 0, %loop.ph ] "196 " %conv = trunc i32 %iv1 to i8 "197 " store i8 %conv, i8* %iv0, align 1 "198 " %iv0.inc = getelementptr inbounds i8, i8* %iv0, i32 %b "199 " %iv1.inc = add nuw nsw i32 %iv1, 1 "200 " %exitcond = icmp eq i32 %iv1.inc, %n "201 " br i1 %exitcond, label %for.end.loopexit, label %loop "202 " "203 "for.end.loopexit: "204 " br label %for.end "205 " "206 "for.end: "207 " ret void "208 "} "209 " "210 "define void @f_2(i32* %X, i32* %Y, i32* %Z) { "211 " %x = load i32, i32* %X "212 " %y = load i32, i32* %Y "213 " %z = load i32, i32* %Z "214 " ret void "215 "} "216 " "217 "define void @f_3() { "218 " %x = load i32, i32* @var_0"219 " %y = load i32, i32* @var_1"220 " %z = load i32, i32* @var_2"221 " ret void"222 "} "223 " "224 "define void @f_4(i32 %a, i32 %b, i32 %c) { "225 " %x = call i32 @unknown(i32 %a, i32 %b, i32 %c)"226 " %y = call i32 @unknown(i32 %b, i32 %c, i32 %a)"227 " %z = call i32 @unknown(i32 %c, i32 %a, i32 %b)"228 " ret void"229 "} "230 ,231 Err, C);232 233 assert(M && "Could not parse module?");234 assert(!verifyModule(*M) && "Must have been well formed!");235 236 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {237 auto *IV0 = getInstructionByName(F, "iv0");238 auto *IV0Inc = getInstructionByName(F, "iv0.inc");239 240 const SCEV *FirstExprForIV0 = SE.getSCEV(IV0);241 const SCEV *FirstExprForIV0Inc = SE.getSCEV(IV0Inc);242 const SCEV *SecondExprForIV0 = SE.getSCEV(IV0);243 244 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0));245 EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0Inc));246 EXPECT_TRUE(isa<SCEVAddRecExpr>(SecondExprForIV0));247 });248 249 auto CheckCommutativeMulExprs = [&](ScalarEvolution &SE, const SCEV *A,250 const SCEV *B, const SCEV *C) {251 EXPECT_EQ(SE.getMulExpr(A, B), SE.getMulExpr(B, A));252 EXPECT_EQ(SE.getMulExpr(B, C), SE.getMulExpr(C, B));253 EXPECT_EQ(SE.getMulExpr(A, C), SE.getMulExpr(C, A));254 255 SmallVector<const SCEV *, 3> Ops0 = {A, B, C};256 SmallVector<const SCEV *, 3> Ops1 = {A, C, B};257 SmallVector<const SCEV *, 3> Ops2 = {B, A, C};258 SmallVector<const SCEV *, 3> Ops3 = {B, C, A};259 SmallVector<const SCEV *, 3> Ops4 = {C, B, A};260 SmallVector<const SCEV *, 3> Ops5 = {C, A, B};261 262 const SCEV *Mul0 = SE.getMulExpr(Ops0);263 const SCEV *Mul1 = SE.getMulExpr(Ops1);264 const SCEV *Mul2 = SE.getMulExpr(Ops2);265 const SCEV *Mul3 = SE.getMulExpr(Ops3);266 const SCEV *Mul4 = SE.getMulExpr(Ops4);267 const SCEV *Mul5 = SE.getMulExpr(Ops5);268 269 EXPECT_EQ(Mul0, Mul1) << "Expected " << *Mul0 << " == " << *Mul1;270 EXPECT_EQ(Mul1, Mul2) << "Expected " << *Mul1 << " == " << *Mul2;271 EXPECT_EQ(Mul2, Mul3) << "Expected " << *Mul2 << " == " << *Mul3;272 EXPECT_EQ(Mul3, Mul4) << "Expected " << *Mul3 << " == " << *Mul4;273 EXPECT_EQ(Mul4, Mul5) << "Expected " << *Mul4 << " == " << *Mul5;274 };275 276 for (StringRef FuncName : {"f_2", "f_3", "f_4"})277 runWithSE(278 *M, FuncName, [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {279 CheckCommutativeMulExprs(SE, SE.getSCEV(getInstructionByName(F, "x")),280 SE.getSCEV(getInstructionByName(F, "y")),281 SE.getSCEV(getInstructionByName(F, "z")));282 });283}284 285TEST_F(ScalarEvolutionsTest, CompareSCEVComplexity) {286 FunctionType *FTy =287 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);288 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);289 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);290 BasicBlock *LoopBB = BasicBlock::Create(Context, "bb1", F);291 BranchInst::Create(LoopBB, EntryBB);292 293 auto *Ty = Type::getInt32Ty(Context);294 SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8);295 296 Acc[0] = PHINode::Create(Ty, 2, "", LoopBB);297 Acc[1] = PHINode::Create(Ty, 2, "", LoopBB);298 Acc[2] = PHINode::Create(Ty, 2, "", LoopBB);299 Acc[3] = PHINode::Create(Ty, 2, "", LoopBB);300 Acc[4] = PHINode::Create(Ty, 2, "", LoopBB);301 Acc[5] = PHINode::Create(Ty, 2, "", LoopBB);302 Acc[6] = PHINode::Create(Ty, 2, "", LoopBB);303 Acc[7] = PHINode::Create(Ty, 2, "", LoopBB);304 305 for (int i = 0; i < 20; i++) {306 Muls[0] = BinaryOperator::CreateMul(Acc[0], Acc[0], "", LoopBB);307 NextAcc[0] = BinaryOperator::CreateAdd(Muls[0], Acc[4], "", LoopBB);308 Muls[1] = BinaryOperator::CreateMul(Acc[1], Acc[1], "", LoopBB);309 NextAcc[1] = BinaryOperator::CreateAdd(Muls[1], Acc[5], "", LoopBB);310 Muls[2] = BinaryOperator::CreateMul(Acc[2], Acc[2], "", LoopBB);311 NextAcc[2] = BinaryOperator::CreateAdd(Muls[2], Acc[6], "", LoopBB);312 Muls[3] = BinaryOperator::CreateMul(Acc[3], Acc[3], "", LoopBB);313 NextAcc[3] = BinaryOperator::CreateAdd(Muls[3], Acc[7], "", LoopBB);314 315 Muls[4] = BinaryOperator::CreateMul(Acc[4], Acc[4], "", LoopBB);316 NextAcc[4] = BinaryOperator::CreateAdd(Muls[4], Acc[0], "", LoopBB);317 Muls[5] = BinaryOperator::CreateMul(Acc[5], Acc[5], "", LoopBB);318 NextAcc[5] = BinaryOperator::CreateAdd(Muls[5], Acc[1], "", LoopBB);319 Muls[6] = BinaryOperator::CreateMul(Acc[6], Acc[6], "", LoopBB);320 NextAcc[6] = BinaryOperator::CreateAdd(Muls[6], Acc[2], "", LoopBB);321 Muls[7] = BinaryOperator::CreateMul(Acc[7], Acc[7], "", LoopBB);322 NextAcc[7] = BinaryOperator::CreateAdd(Muls[7], Acc[3], "", LoopBB);323 Acc = NextAcc;324 }325 326 auto II = LoopBB->begin();327 for (int i = 0; i < 8; i++) {328 PHINode *Phi = cast<PHINode>(&*II++);329 Phi->addIncoming(Acc[i], LoopBB);330 Phi->addIncoming(PoisonValue::get(Ty), EntryBB);331 }332 333 BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F);334 BranchInst::Create(LoopBB, ExitBB, PoisonValue::get(Type::getInt1Ty(Context)),335 LoopBB);336 337 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);338 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);339 Acc[2] = BinaryOperator::CreateAdd(Acc[4], Acc[5], "", ExitBB);340 Acc[3] = BinaryOperator::CreateAdd(Acc[6], Acc[7], "", ExitBB);341 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);342 Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);343 Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);344 345 ReturnInst::Create(Context, nullptr, ExitBB);346 347 ScalarEvolution SE = buildSE(*F);348 349 EXPECT_NE(nullptr, SE.getSCEV(Acc[0]));350}351 352TEST_F(ScalarEvolutionsTest, CompareValueComplexity) {353 IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(Context);354 PointerType *IntPtrPtrTy = PointerType::getUnqual(Context);355 356 FunctionType *FTy =357 FunctionType::get(Type::getVoidTy(Context), {IntPtrTy, IntPtrTy}, false);358 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);359 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);360 361 Value *X = &*F->arg_begin();362 Value *Y = &*std::next(F->arg_begin());363 364 const int ValueDepth = 10;365 for (int i = 0; i < ValueDepth; i++) {366 X = new LoadInst(IntPtrTy, new IntToPtrInst(X, IntPtrPtrTy, "", EntryBB),367 "",368 /*isVolatile*/ false, EntryBB);369 Y = new LoadInst(IntPtrTy, new IntToPtrInst(Y, IntPtrPtrTy, "", EntryBB),370 "",371 /*isVolatile*/ false, EntryBB);372 }373 374 auto *MulA = BinaryOperator::CreateMul(X, Y, "", EntryBB);375 auto *MulB = BinaryOperator::CreateMul(Y, X, "", EntryBB);376 ReturnInst::Create(Context, nullptr, EntryBB);377 378 // This test isn't checking for correctness. Today making A and B resolve to379 // the same SCEV would require deeper searching in CompareValueComplexity,380 // which will slow down compilation. However, this test can fail (with LLVM's381 // behavior still being correct) if we ever have a smarter382 // CompareValueComplexity that is both fast and more accurate.383 384 ScalarEvolution SE = buildSE(*F);385 const SCEV *A = SE.getSCEV(MulA);386 const SCEV *B = SE.getSCEV(MulB);387 EXPECT_NE(A, B);388}389 390TEST_F(ScalarEvolutionsTest, SCEVAddExpr) {391 Type *Ty32 = Type::getInt32Ty(Context);392 Type *ArgTys[] = {Type::getInt64Ty(Context), Ty32, Ty32, Ty32, Ty32, Ty32};393 394 FunctionType *FTy =395 FunctionType::get(Type::getVoidTy(Context), ArgTys, false);396 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);397 398 Argument *A1 = &*F->arg_begin();399 Argument *A2 = &*(std::next(F->arg_begin()));400 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);401 402 Instruction *Trunc = CastInst::CreateTruncOrBitCast(A1, Ty32, "", EntryBB);403 Instruction *Mul1 = BinaryOperator::CreateMul(Trunc, A2, "", EntryBB);404 Instruction *Add1 = BinaryOperator::CreateAdd(Mul1, Trunc, "", EntryBB);405 Mul1 = BinaryOperator::CreateMul(Add1, Trunc, "", EntryBB);406 Instruction *Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB);407 // FIXME: The size of this is arbitrary and doesn't seem to change the408 // result, but SCEV will do quadratic work for these so a large number here409 // will be extremely slow. We should revisit what and how this is testing410 // SCEV.411 for (int i = 0; i < 10; i++) {412 Mul1 = BinaryOperator::CreateMul(Add2, Add1, "", EntryBB);413 Add1 = Add2;414 Add2 = BinaryOperator::CreateAdd(Mul1, Add1, "", EntryBB);415 }416 417 ReturnInst::Create(Context, nullptr, EntryBB);418 ScalarEvolution SE = buildSE(*F);419 EXPECT_NE(nullptr, SE.getSCEV(Mul1));420 421 Argument *A3 = &*(std::next(F->arg_begin(), 2));422 Argument *A4 = &*(std::next(F->arg_begin(), 3));423 Argument *A5 = &*(std::next(F->arg_begin(), 4));424 Argument *A6 = &*(std::next(F->arg_begin(), 5));425 426 auto *AddWithNUW = cast<SCEVAddExpr>(SE.getAddExpr(427 SE.getAddExpr(SE.getSCEV(A2), SE.getSCEV(A3), SCEV::FlagNUW),428 SE.getConstant(APInt(/*numBits=*/32, 5)), SCEV::FlagNUW));429 EXPECT_EQ(AddWithNUW->getNumOperands(), 3u);430 EXPECT_EQ(AddWithNUW->getNoWrapFlags(), SCEV::FlagNUW);431 432 const SCEV *AddWithAnyWrap =433 SE.getAddExpr(SE.getSCEV(A3), SE.getSCEV(A4), SCEV::FlagAnyWrap);434 auto *AddWithAnyWrapNUW = cast<SCEVAddExpr>(435 SE.getAddExpr(AddWithAnyWrap, SE.getSCEV(A5), SCEV::FlagNUW));436 EXPECT_EQ(AddWithAnyWrapNUW->getNumOperands(), 3u);437 EXPECT_EQ(AddWithAnyWrapNUW->getNoWrapFlags(), SCEV::FlagAnyWrap);438 439 const SCEV *AddWithNSW = SE.getAddExpr(440 SE.getSCEV(A2), SE.getConstant(APInt(32, 99)), SCEV::FlagNSW);441 auto *AddWithNSW_NUW = cast<SCEVAddExpr>(442 SE.getAddExpr(AddWithNSW, SE.getSCEV(A5), SCEV::FlagNUW));443 EXPECT_EQ(AddWithNSW_NUW->getNumOperands(), 3u);444 EXPECT_EQ(AddWithNSW_NUW->getNoWrapFlags(), SCEV::FlagAnyWrap);445 446 const SCEV *AddWithNSWNUW =447 SE.getAddExpr(SE.getSCEV(A2), SE.getSCEV(A4),448 ScalarEvolution::setFlags(SCEV::FlagNUW, SCEV::FlagNSW));449 auto *AddWithNSWNUW_NUW = cast<SCEVAddExpr>(450 SE.getAddExpr(AddWithNSWNUW, SE.getSCEV(A5), SCEV::FlagNUW));451 EXPECT_EQ(AddWithNSWNUW_NUW->getNumOperands(), 3u);452 EXPECT_EQ(AddWithNSWNUW_NUW->getNoWrapFlags(), SCEV::FlagNUW);453 454 auto *AddWithNSW_NSWNUW = cast<SCEVAddExpr>(455 SE.getAddExpr(AddWithNSW, SE.getSCEV(A6),456 ScalarEvolution::setFlags(SCEV::FlagNUW, SCEV::FlagNSW)));457 EXPECT_EQ(AddWithNSW_NSWNUW->getNumOperands(), 3u);458 EXPECT_EQ(AddWithNSW_NSWNUW->getNoWrapFlags(), SCEV::FlagAnyWrap);459}460 461static Instruction &GetInstByName(Function &F, StringRef Name) {462 for (auto &I : instructions(F))463 if (I.getName() == Name)464 return I;465 llvm_unreachable("Could not find instructions!");466}467 468TEST_F(ScalarEvolutionsTest, SCEVNormalization) {469 LLVMContext C;470 SMDiagnostic Err;471 std::unique_ptr<Module> M = parseAssemblyString(472 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "473 " "474 "@var_0 = external global i32, align 4"475 "@var_1 = external global i32, align 4"476 "@var_2 = external global i32, align 4"477 " "478 "declare i32 @unknown(i32, i32, i32)"479 " "480 "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "481 " local_unnamed_addr { "482 "entry: "483 " br label %loop.ph "484 " "485 "loop.ph: "486 " br label %loop "487 " "488 "loop: "489 " %iv0 = phi i32 [ %iv0.inc, %loop ], [ 0, %loop.ph ] "490 " %iv1 = phi i32 [ %iv1.inc, %loop ], [ -2147483648, %loop.ph ] "491 " %iv0.inc = add i32 %iv0, 1 "492 " %iv1.inc = add i32 %iv1, 3 "493 " br i1 poison, label %for.end.loopexit, label %loop "494 " "495 "for.end.loopexit: "496 " ret void "497 "} "498 " "499 "define void @f_2(i32 %a, i32 %b, i32 %c, i32 %d) "500 " local_unnamed_addr { "501 "entry: "502 " br label %loop_0 "503 " "504 "loop_0: "505 " br i1 poison, label %loop_0, label %loop_1 "506 " "507 "loop_1: "508 " br i1 poison, label %loop_2, label %loop_1 "509 " "510 " "511 "loop_2: "512 " br i1 poison, label %end, label %loop_2 "513 " "514 "end: "515 " ret void "516 "} ",517 Err, C);518 519 assert(M && "Could not parse module?");520 assert(!verifyModule(*M) && "Must have been well formed!");521 522 runWithSE(*M, "f_1", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {523 auto &I0 = GetInstByName(F, "iv0");524 auto &I1 = *I0.getNextNode();525 526 auto *S0 = cast<SCEVAddRecExpr>(SE.getSCEV(&I0));527 PostIncLoopSet Loops;528 Loops.insert(S0->getLoop());529 auto *N0 = normalizeForPostIncUse(S0, Loops, SE);530 auto *D0 = denormalizeForPostIncUse(N0, Loops, SE);531 EXPECT_EQ(S0, D0) << *S0 << " " << *D0;532 533 auto *S1 = cast<SCEVAddRecExpr>(SE.getSCEV(&I1));534 Loops.clear();535 Loops.insert(S1->getLoop());536 auto *N1 = normalizeForPostIncUse(S1, Loops, SE);537 auto *D1 = denormalizeForPostIncUse(N1, Loops, SE);538 EXPECT_EQ(S1, D1) << *S1 << " " << *D1;539 });540 541 runWithSE(*M, "f_2", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {542 auto *L2 = *LI.begin();543 auto *L1 = *std::next(LI.begin());544 auto *L0 = *std::next(LI.begin(), 2);545 546 auto GetAddRec = [&SE](const Loop *L, std::initializer_list<const SCEV *> Ops) {547 SmallVector<const SCEV *, 4> OpsCopy(Ops);548 return SE.getAddRecExpr(OpsCopy, L, SCEV::FlagAnyWrap);549 };550 551 auto GetAdd = [&SE](std::initializer_list<const SCEV *> Ops) {552 SmallVector<const SCEV *, 4> OpsCopy(Ops);553 return SE.getAddExpr(OpsCopy, SCEV::FlagAnyWrap);554 };555 556 // We first populate the AddRecs vector with a few "interesting" SCEV557 // expressions, and then we go through the list and assert that each558 // expression in it has an invertible normalization.559 560 std::vector<const SCEV *> Exprs;561 {562 const SCEV *V0 = SE.getSCEV(&*F.arg_begin());563 const SCEV *V1 = SE.getSCEV(&*std::next(F.arg_begin(), 1));564 const SCEV *V2 = SE.getSCEV(&*std::next(F.arg_begin(), 2));565 const SCEV *V3 = SE.getSCEV(&*std::next(F.arg_begin(), 3));566 567 Exprs.push_back(GetAddRec(L0, {V0})); // 0568 Exprs.push_back(GetAddRec(L0, {V0, V1})); // 1569 Exprs.push_back(GetAddRec(L0, {V0, V1, V2})); // 2570 Exprs.push_back(GetAddRec(L0, {V0, V1, V2, V3})); // 3571 572 Exprs.push_back(573 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[3], Exprs[0]})); // 4574 Exprs.push_back(575 GetAddRec(L1, {Exprs[1], Exprs[2], Exprs[0], Exprs[3]})); // 5576 Exprs.push_back(577 GetAddRec(L1, {Exprs[1], Exprs[3], Exprs[3], Exprs[1]})); // 6578 579 Exprs.push_back(GetAdd({Exprs[6], Exprs[3], V2})); // 7580 581 Exprs.push_back(582 GetAddRec(L2, {Exprs[4], Exprs[3], Exprs[3], Exprs[5]})); // 8583 584 Exprs.push_back(585 GetAddRec(L2, {Exprs[4], Exprs[6], Exprs[7], Exprs[3], V0})); // 9586 }587 588 std::vector<PostIncLoopSet> LoopSets;589 for (int i = 0; i < 8; i++) {590 LoopSets.emplace_back();591 if (i & 1)592 LoopSets.back().insert(L0);593 if (i & 2)594 LoopSets.back().insert(L1);595 if (i & 4)596 LoopSets.back().insert(L2);597 }598 599 for (const auto &LoopSet : LoopSets)600 for (auto *S : Exprs) {601 {602 auto *N = llvm::normalizeForPostIncUse(S, LoopSet, SE);603 auto *D = llvm::denormalizeForPostIncUse(N, LoopSet, SE);604 605 // Normalization and then denormalizing better give us back the same606 // value.607 EXPECT_EQ(S, D) << "S = " << *S << " D = " << *D << " N = " << *N;608 }609 {610 auto *D = llvm::denormalizeForPostIncUse(S, LoopSet, SE);611 auto *N = llvm::normalizeForPostIncUse(D, LoopSet, SE);612 613 // Denormalization and then normalizing better give us back the same614 // value.615 EXPECT_EQ(S, N) << "S = " << *S << " N = " << *N;616 }617 }618 });619}620 621// Expect the call of getZeroExtendExpr will not cost exponential time.622TEST_F(ScalarEvolutionsTest, SCEVZeroExtendExpr) {623 LLVMContext C;624 SMDiagnostic Err;625 626 // Generate a function like below:627 // define void @foo() {628 // entry:629 // br label %for.cond630 //631 // for.cond:632 // %0 = phi i64 [ 100, %entry ], [ %dec, %for.inc ]633 // %cmp = icmp sgt i64 %0, 90634 // br i1 %cmp, label %for.inc, label %for.cond1635 //636 // for.inc:637 // %dec = add nsw i64 %0, -1638 // br label %for.cond639 //640 // for.cond1:641 // %1 = phi i64 [ 100, %for.cond ], [ %dec5, %for.inc2 ]642 // %cmp3 = icmp sgt i64 %1, 90643 // br i1 %cmp3, label %for.inc2, label %for.cond4644 //645 // for.inc2:646 // %dec5 = add nsw i64 %1, -1647 // br label %for.cond1648 //649 // ......650 //651 // for.cond89:652 // %19 = phi i64 [ 100, %for.cond84 ], [ %dec94, %for.inc92 ]653 // %cmp93 = icmp sgt i64 %19, 90654 // br i1 %cmp93, label %for.inc92, label %for.end655 //656 // for.inc92:657 // %dec94 = add nsw i64 %19, -1658 // br label %for.cond89659 //660 // for.end:661 // %gep = getelementptr i8, i8* null, i64 %dec662 // %gep6 = getelementptr i8, i8* %gep, i64 %dec5663 // ......664 // %gep95 = getelementptr i8, i8* %gep91, i64 %dec94665 // ret void666 // }667 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false);668 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M);669 670 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);671 BasicBlock *CondBB = BasicBlock::Create(Context, "for.cond", F);672 BasicBlock *EndBB = BasicBlock::Create(Context, "for.end", F);673 BranchInst::Create(CondBB, EntryBB);674 BasicBlock *PrevBB = EntryBB;675 676 Type *I64Ty = Type::getInt64Ty(Context);677 Type *I8Ty = Type::getInt8Ty(Context);678 Type *I8PtrTy = PointerType::getUnqual(Context);679 Value *Accum = Constant::getNullValue(I8PtrTy);680 int Iters = 20;681 for (int i = 0; i < Iters; i++) {682 BasicBlock *IncBB = BasicBlock::Create(Context, "for.inc", F, EndBB);683 auto *PN = PHINode::Create(I64Ty, 2, "", CondBB);684 PN->addIncoming(ConstantInt::get(Context, APInt(64, 100)), PrevBB);685 auto *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_SGT, PN,686 ConstantInt::get(Context, APInt(64, 90)), "cmp",687 CondBB);688 BasicBlock *NextBB;689 if (i != Iters - 1)690 NextBB = BasicBlock::Create(Context, "for.cond", F, EndBB);691 else692 NextBB = EndBB;693 BranchInst::Create(IncBB, NextBB, Cmp, CondBB);694 auto *Dec = BinaryOperator::CreateNSWAdd(695 PN, ConstantInt::get(Context, APInt(64, -1)), "dec", IncBB);696 PN->addIncoming(Dec, IncBB);697 BranchInst::Create(CondBB, IncBB);698 699 Accum = GetElementPtrInst::Create(I8Ty, Accum, PN, "gep", EndBB);700 701 PrevBB = CondBB;702 CondBB = NextBB;703 }704 ReturnInst::Create(Context, nullptr, EndBB);705 ScalarEvolution SE = buildSE(*F);706 const SCEV *S = SE.getSCEV(Accum);707 S = SE.getLosslessPtrToIntExpr(S);708 Type *I128Ty = Type::getInt128Ty(Context);709 SE.getZeroExtendExpr(S, I128Ty);710}711 712// Make sure that SCEV invalidates exit limits after invalidating the values it713// depends on when we forget a loop.714TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetLoop) {715 /*716 * Create the following code:717 * func(i64 addrspace(10)* %arg)718 * top:719 * br label %L.ph720 * L.ph:721 * br label %L722 * L:723 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]724 * %add = add i64 %phi2, 1725 * %cond = icmp slt i64 %add, 1000; then becomes 2000.726 * br i1 %cond, label %post, label %L2727 * post:728 * ret void729 *730 */731 732 // Create a module with non-integral pointers in it's datalayout733 Module NIM("nonintegral", Context);734 std::string DataLayout = M.getDataLayoutStr();735 if (!DataLayout.empty())736 DataLayout += "-";737 DataLayout += "ni:10";738 NIM.setDataLayout(DataLayout);739 740 Type *T_int64 = Type::getInt64Ty(Context);741 Type *T_pint64 = PointerType::get(Context, 10);742 743 FunctionType *FTy =744 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);745 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);746 747 BasicBlock *Top = BasicBlock::Create(Context, "top", F);748 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);749 BasicBlock *L = BasicBlock::Create(Context, "L", F);750 BasicBlock *Post = BasicBlock::Create(Context, "post", F);751 752 IRBuilder<> Builder(Top);753 Builder.CreateBr(LPh);754 755 Builder.SetInsertPoint(LPh);756 Builder.CreateBr(L);757 758 Builder.SetInsertPoint(L);759 PHINode *Phi = Builder.CreatePHI(T_int64, 2);760 auto *Add = cast<Instruction>(761 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));762 auto *Limit = ConstantInt::get(T_int64, 1000);763 auto *Cond = cast<Instruction>(764 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Limit, "cond"));765 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));766 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);767 Phi->addIncoming(Add, L);768 769 Builder.SetInsertPoint(Post);770 Builder.CreateRetVoid();771 772 ScalarEvolution SE = buildSE(*F);773 auto *Loop = LI->getLoopFor(L);774 const SCEV *EC = SE.getBackedgeTakenCount(Loop);775 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));776 EXPECT_TRUE(isa<SCEVConstant>(EC));777 EXPECT_EQ(cast<SCEVConstant>(EC)->getAPInt().getLimitedValue(), 999u);778 779 // The add recurrence {5,+,1} does not correspond to any PHI in the IR, and780 // that is relevant to this test.781 const SCEV *Five = SE.getConstant(APInt(/*numBits=*/64, 5));782 const SCEV *AR =783 SE.getAddRecExpr(Five, SE.getOne(T_int64), Loop, SCEV::FlagAnyWrap);784 const SCEV *ARAtLoopExit = SE.getSCEVAtScope(AR, nullptr);785 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ARAtLoopExit));786 EXPECT_TRUE(isa<SCEVConstant>(ARAtLoopExit));787 EXPECT_EQ(cast<SCEVConstant>(ARAtLoopExit)->getAPInt().getLimitedValue(),788 1004u);789 790 SE.forgetLoop(Loop);791 Br->eraseFromParent();792 Cond->eraseFromParent();793 794 Builder.SetInsertPoint(L);795 auto *NewCond = Builder.CreateICmp(796 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond");797 Builder.CreateCondBr(NewCond, L, Post);798 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);799 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));800 EXPECT_TRUE(isa<SCEVConstant>(NewEC));801 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);802 const SCEV *NewARAtLoopExit = SE.getSCEVAtScope(AR, nullptr);803 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewARAtLoopExit));804 EXPECT_TRUE(isa<SCEVConstant>(NewARAtLoopExit));805 EXPECT_EQ(cast<SCEVConstant>(NewARAtLoopExit)->getAPInt().getLimitedValue(),806 2004u);807}808 809// Make sure that SCEV invalidates exit limits after invalidating the values it810// depends on when we forget a value.811TEST_F(ScalarEvolutionsTest, SCEVExitLimitForgetValue) {812 /*813 * Create the following code:814 * func(i64 addrspace(10)* %arg)815 * top:816 * br label %L.ph817 * L.ph:818 * %load = load i64 addrspace(10)* %arg819 * br label %L820 * L:821 * %phi = phi i64 [i64 0, %L.ph], [ %add, %L2 ]822 * %add = add i64 %phi2, 1823 * %cond = icmp slt i64 %add, %load ; then becomes 2000.824 * br i1 %cond, label %post, label %L2825 * post:826 * ret void827 *828 */829 830 // Create a module with non-integral pointers in it's datalayout831 Module NIM("nonintegral", Context);832 std::string DataLayout = M.getDataLayoutStr();833 if (!DataLayout.empty())834 DataLayout += "-";835 DataLayout += "ni:10";836 NIM.setDataLayout(DataLayout);837 838 Type *T_int64 = Type::getInt64Ty(Context);839 Type *T_pint64 = PointerType::get(Context, 10);840 841 FunctionType *FTy =842 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);843 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);844 845 Argument *Arg = &*F->arg_begin();846 847 BasicBlock *Top = BasicBlock::Create(Context, "top", F);848 BasicBlock *LPh = BasicBlock::Create(Context, "L.ph", F);849 BasicBlock *L = BasicBlock::Create(Context, "L", F);850 BasicBlock *Post = BasicBlock::Create(Context, "post", F);851 852 IRBuilder<> Builder(Top);853 Builder.CreateBr(LPh);854 855 Builder.SetInsertPoint(LPh);856 auto *Load = cast<Instruction>(Builder.CreateLoad(T_int64, Arg, "load"));857 Builder.CreateBr(L);858 859 Builder.SetInsertPoint(L);860 PHINode *Phi = Builder.CreatePHI(T_int64, 2);861 auto *Add = cast<Instruction>(862 Builder.CreateAdd(Phi, ConstantInt::get(T_int64, 1), "add"));863 auto *Cond = cast<Instruction>(864 Builder.CreateICmp(ICmpInst::ICMP_SLT, Add, Load, "cond"));865 auto *Br = cast<Instruction>(Builder.CreateCondBr(Cond, L, Post));866 Phi->addIncoming(ConstantInt::get(T_int64, 0), LPh);867 Phi->addIncoming(Add, L);868 869 Builder.SetInsertPoint(Post);870 Builder.CreateRetVoid();871 872 ScalarEvolution SE = buildSE(*F);873 auto *Loop = LI->getLoopFor(L);874 const SCEV *EC = SE.getBackedgeTakenCount(Loop);875 EXPECT_FALSE(isa<SCEVCouldNotCompute>(EC));876 EXPECT_FALSE(isa<SCEVConstant>(EC));877 878 SE.forgetValue(Load);879 Br->eraseFromParent();880 Cond->eraseFromParent();881 Load->eraseFromParent();882 883 Builder.SetInsertPoint(L);884 auto *NewCond = Builder.CreateICmp(885 ICmpInst::ICMP_SLT, Add, ConstantInt::get(T_int64, 2000), "new.cond");886 Builder.CreateCondBr(NewCond, L, Post);887 const SCEV *NewEC = SE.getBackedgeTakenCount(Loop);888 EXPECT_FALSE(isa<SCEVCouldNotCompute>(NewEC));889 EXPECT_TRUE(isa<SCEVConstant>(NewEC));890 EXPECT_EQ(cast<SCEVConstant>(NewEC)->getAPInt().getLimitedValue(), 1999u);891}892 893TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstants) {894 // Reference: https://reviews.llvm.org/D37265895 // Make sure that SCEV does not blow up when constructing an AddRec896 // with predicates for a phi with the update pattern:897 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum898 // when either the initial value of the Phi or the InvariantAccum are899 // constants that are too large to fit in an ix but are zero when truncated to900 // ix.901 FunctionType *FTy =902 FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);903 Function *F =904 Function::Create(FTy, Function::ExternalLinkage, "addrecphitest", M);905 906 /*907 Create IR:908 entry:909 br label %loop910 loop:911 %0 = phi i64 [-9223372036854775808, %entry], [%3, %loop]912 %1 = shl i64 %0, 32913 %2 = ashr exact i64 %1, 32914 %3 = add i64 %2, -9223372036854775808915 br i1 poison, label %exit, label %loop916 exit:917 ret void918 */919 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);920 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);921 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);922 923 // entry:924 BranchInst::Create(LoopBB, EntryBB);925 // loop:926 auto *MinInt64 =927 ConstantInt::get(Context, APInt(64, 0x8000000000000000U, true));928 auto *Int64_32 = ConstantInt::get(Context, APInt(64, 32));929 auto *Br = BranchInst::Create(930 LoopBB, ExitBB, PoisonValue::get(Type::getInt1Ty(Context)), LoopBB);931 auto *Phi =932 PHINode::Create(Type::getInt64Ty(Context), 2, "", Br->getIterator());933 auto *Shl = BinaryOperator::CreateShl(Phi, Int64_32, "", Br->getIterator());934 auto *AShr =935 BinaryOperator::CreateExactAShr(Shl, Int64_32, "", Br->getIterator());936 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt64, "", Br->getIterator());937 Phi->addIncoming(MinInt64, EntryBB);938 Phi->addIncoming(Add, LoopBB);939 // exit:940 ReturnInst::Create(Context, nullptr, ExitBB);941 942 // Make sure that SCEV doesn't blow up943 ScalarEvolution SE = buildSE(*F);944 const SCEV *Expr = SE.getSCEV(Phi);945 EXPECT_NE(nullptr, Expr);946 EXPECT_TRUE(isa<SCEVUnknown>(Expr));947 auto Result = SE.createAddRecFromPHIWithCasts(cast<SCEVUnknown>(Expr));948}949 950TEST_F(ScalarEvolutionsTest, SCEVAddRecFromPHIwithLargeConstantAccum) {951 // Make sure that SCEV does not blow up when constructing an AddRec952 // with predicates for a phi with the update pattern:953 // (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum954 // when the InvariantAccum is a constant that is too large to fit in an955 // ix but are zero when truncated to ix, and the initial value of the956 // phi is not a constant.957 Type *Int32Ty = Type::getInt32Ty(Context);958 SmallVector<Type *, 1> Types;959 Types.push_back(Int32Ty);960 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false);961 Function *F =962 Function::Create(FTy, Function::ExternalLinkage, "addrecphitest", M);963 964 /*965 Create IR:966 define @addrecphitest(i32)967 entry:968 br label %loop969 loop:970 %1 = phi i32 [%0, %entry], [%4, %loop]971 %2 = shl i32 %1, 16972 %3 = ashr exact i32 %2, 16973 %4 = add i32 %3, -2147483648974 br i1 poison, label %exit, label %loop975 exit:976 ret void977 */978 BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);979 BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);980 BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);981 982 // entry:983 BranchInst::Create(LoopBB, EntryBB);984 // loop:985 auto *MinInt32 = ConstantInt::get(Context, APInt(32, 0x80000000U));986 auto *Int32_16 = ConstantInt::get(Context, APInt(32, 16));987 auto *Br = BranchInst::Create(988 LoopBB, ExitBB, PoisonValue::get(Type::getInt1Ty(Context)), LoopBB);989 auto *Phi = PHINode::Create(Int32Ty, 2, "", Br->getIterator());990 auto *Shl = BinaryOperator::CreateShl(Phi, Int32_16, "", Br->getIterator());991 auto *AShr =992 BinaryOperator::CreateExactAShr(Shl, Int32_16, "", Br->getIterator());993 auto *Add = BinaryOperator::CreateAdd(AShr, MinInt32, "", Br->getIterator());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 up1001 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 1008TEST_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 SCEV *ArgSCEV = SE.getSCEV(Arg);1024 1025 // Build the SCEV1026 const SCEV *A0 = SE.getNegativeSCEV(ArgSCEV);1027 const SCEV *A1 = SE.getTruncateExpr(A0, Int32Ty);1028 const SCEV *A = SE.getNegativeSCEV(A1);1029 1030 const SCEV *B0 = SE.getTruncateExpr(ArgSCEV, Int32Ty);1031 const SCEV *B = SE.getNegativeSCEV(B0);1032 1033 const SCEV *Expr = SE.getAddExpr(A, B);1034 // Verify that the SCEV was folded to 01035 const SCEV *ZeroConst = SE.getConstant(Int32Ty, 0);1036 EXPECT_EQ(Expr, ZeroConst);1037}1038 1039// Check logic of SCEV expression size computation.1040TEST_F(ScalarEvolutionsTest, SCEVComputeExpressionSize) {1041 /*1042 * Create the following code:1043 * void func(i64 %a, i64 %b)1044 * entry:1045 * %s1 = add i64 %a, 11046 * %s2 = udiv i64 %s1, %b1047 * br label %exit1048 * exit:1049 * ret1050 */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 1089TEST_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 const SCEV *ScevInc = SE.getSCEV(getInstructionByName(F, "inc"));1113 EXPECT_TRUE(isa<SCEVAddRecExpr>(ScevInc));1114 });1115}1116 1117TEST_F(ScalarEvolutionsTest, SCEVComputeConstantDifference) {1118 LLVMContext C;1119 SMDiagnostic Err;1120 std::unique_ptr<Module> M = parseAssemblyString(1121 R"(define void @foo(ptr %ptr, i32 %sz, i32 %pp, i32 %x) {1122 entry:1123 %v0 = add i32 %pp, 01124 %v3 = add i32 %pp, 31125 %vx = add i32 %pp, %x1126 %vx3 = add i32 %vx, 31127 br label %loop.body1128 loop.body:1129 %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ]1130 %xa = add nsw i32 %iv, %v01131 %yy = add nsw i32 %iv, %v31132 %xb = sub nsw i32 %yy, 31133 %iv.next = add nsw i32 %iv, 11134 %cmp = icmp sle i32 %iv.next, %sz1135 br i1 %cmp, label %loop.body, label %loop2.body1136 loop2.body:1137 %iv2 = phi i32 [ %iv2.next, %loop2.body ], [ %iv, %loop.body ]1138 %iv2.next = add nsw i32 %iv2, 11139 %iv2p3 = add i32 %iv2, 31140 %var = load i32, ptr %ptr1141 %iv2pvar = add i32 %iv2, %var1142 %iv2pvarp3 = add i32 %iv2pvar, 31143 %iv2pvarm3 = mul i32 %iv2pvar, 31144 %iv2pvarp3m3 = mul i32 %iv2pvarp3, 31145 %cmp2 = icmp sle i32 %iv2.next, %sz1146 br i1 %cmp2, label %loop2.body, label %exit1147 exit:1148 ret void1149 })",1150 Err, C);1151 1152 if (!M) {1153 Err.print("ScalarEvolutionTest", errs());1154 ASSERT_TRUE(M && "Could not parse module?");1155 }1156 ASSERT_TRUE(!verifyModule(*M, &errs()) && "Must have been well formed!");1157 1158 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1159 const SCEV *ScevV0 = SE.getSCEV(getInstructionByName(F, "v0")); // %pp1160 const SCEV *ScevV3 = SE.getSCEV(getInstructionByName(F, "v3")); // (3 + %pp)1161 const SCEV *ScevVX =1162 SE.getSCEV(getInstructionByName(F, "vx")); // (%pp + %x)1163 // (%pp + %x + 3)1164 const SCEV *ScevVX3 = SE.getSCEV(getInstructionByName(F, "vx3"));1165 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1}1166 const SCEV *ScevXA = SE.getSCEV(getInstructionByName(F, "xa")); // {%pp,+,1}1167 const SCEV *ScevYY =1168 SE.getSCEV(getInstructionByName(F, "yy")); // {(3 + %pp),+,1}1169 const SCEV *ScevXB = SE.getSCEV(getInstructionByName(F, "xb")); // {%pp,+,1}1170 const SCEV *ScevIVNext =1171 SE.getSCEV(getInstructionByName(F, "iv.next")); // {1,+,1}1172 // {{0,+,1},+,1}1173 const SCEV *ScevIV2 = SE.getSCEV(getInstructionByName(F, "iv2"));1174 // {{3,+,1},+,1}1175 const SCEV *ScevIV2P3 = SE.getSCEV(getInstructionByName(F, "iv2p3"));1176 // %var + {{0,+,1},+,1}1177 const SCEV *ScevIV2PVar = SE.getSCEV(getInstructionByName(F, "iv2pvar"));1178 // %var + {{3,+,1},+,1}1179 const SCEV *ScevIV2PVarP3 =1180 SE.getSCEV(getInstructionByName(F, "iv2pvarp3"));1181 // 3 * (%var + {{0,+,1},+,1})1182 const SCEV *ScevIV2PVarM3 =1183 SE.getSCEV(getInstructionByName(F, "iv2pvarm3"));1184 // 3 * (%var + {{3,+,1},+,1})1185 const SCEV *ScevIV2PVarP3M3 =1186 SE.getSCEV(getInstructionByName(F, "iv2pvarp3m3"));1187 1188 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> std::optional<int> {1189 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS);1190 if (!ConstantDiffOrNone)1191 return std::nullopt;1192 1193 auto ExtDiff = ConstantDiffOrNone->getSExtValue();1194 int Diff = ExtDiff;1195 assert(Diff == ExtDiff && "Integer overflow");1196 return Diff;1197 };1198 1199 EXPECT_EQ(diff(ScevV3, ScevV0), 3);1200 EXPECT_EQ(diff(ScevV0, ScevV3), -3);1201 EXPECT_EQ(diff(ScevV0, ScevV0), 0);1202 EXPECT_EQ(diff(ScevV3, ScevV3), 0);1203 EXPECT_EQ(diff(ScevVX3, ScevVX), 3);1204 EXPECT_EQ(diff(ScevIV, ScevIV), 0);1205 EXPECT_EQ(diff(ScevXA, ScevXB), 0);1206 EXPECT_EQ(diff(ScevXA, ScevYY), -3);1207 EXPECT_EQ(diff(ScevYY, ScevXB), 3);1208 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1);1209 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1);1210 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0);1211 EXPECT_EQ(diff(ScevIV2P3, ScevIV2), 3);1212 EXPECT_EQ(diff(ScevIV2PVar, ScevIV2PVarP3), -3);1213 EXPECT_EQ(diff(ScevIV2PVarP3M3, ScevIV2PVarM3), 9);1214 EXPECT_EQ(diff(ScevV0, ScevIV), std::nullopt);1215 EXPECT_EQ(diff(ScevIVNext, ScevV3), std::nullopt);1216 EXPECT_EQ(diff(ScevYY, ScevV3), std::nullopt);1217 });1218}1219 1220TEST_F(ScalarEvolutionsTest, SCEVrewriteUnknowns) {1221 LLVMContext C;1222 SMDiagnostic Err;1223 std::unique_ptr<Module> M = parseAssemblyString(1224 "define void @foo(i32 %i) { "1225 "entry: "1226 " %cmp3 = icmp ult i32 %i, 16 "1227 " br i1 %cmp3, label %loop.body, label %exit "1228 "loop.body: "1229 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] "1230 " %iv.next = add nsw i32 %iv, 1 "1231 " %cmp = icmp eq i32 %iv.next, 16 "1232 " br i1 %cmp, label %exit, label %loop.body "1233 "exit: "1234 " ret void "1235 "} ",1236 Err, C);1237 1238 ASSERT_TRUE(M && "Could not parse module?");1239 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1240 1241 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1242 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1}1243 const SCEV *ScevI = SE.getSCEV(getArgByName(F, "i")); // {0,+,1}1244 1245 ValueToSCEVMapTy RewriteMap;1246 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] =1247 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17));1248 const SCEV *WithUMin =1249 SCEVParameterRewriter::rewrite(ScevIV, SE, RewriteMap);1250 1251 EXPECT_NE(WithUMin, ScevIV);1252 const auto *AR = dyn_cast<SCEVAddRecExpr>(WithUMin);1253 EXPECT_TRUE(AR);1254 EXPECT_EQ(AR->getStart(),1255 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17)));1256 EXPECT_EQ(AR->getStepRecurrence(SE),1257 cast<SCEVAddRecExpr>(ScevIV)->getStepRecurrence(SE));1258 });1259}1260 1261TEST_F(ScalarEvolutionsTest, SCEVAddNUW) {1262 LLVMContext C;1263 SMDiagnostic Err;1264 std::unique_ptr<Module> M = parseAssemblyString("define void @foo(i32 %x) { "1265 " ret void "1266 "} ",1267 Err, C);1268 1269 ASSERT_TRUE(M && "Could not parse module?");1270 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1271 1272 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1273 const SCEV *X = SE.getSCEV(getArgByName(F, "x"));1274 const SCEV *One = SE.getOne(X->getType());1275 const SCEV *Sum = SE.getAddExpr(X, One, SCEV::FlagNUW);1276 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGE, Sum, X));1277 EXPECT_TRUE(SE.isKnownPredicate(ICmpInst::ICMP_UGT, Sum, X));1278 });1279}1280 1281TEST_F(ScalarEvolutionsTest, SCEVgetRanges) {1282 LLVMContext C;1283 SMDiagnostic Err;1284 std::unique_ptr<Module> M = parseAssemblyString(1285 "define void @foo(i32 %i) { "1286 "entry: "1287 " br label %loop.body "1288 "loop.body: "1289 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] "1290 " %iv.next = add nsw i32 %iv, 1 "1291 " %cmp = icmp eq i32 %iv.next, 16 "1292 " br i1 %cmp, label %exit, label %loop.body "1293 "exit: "1294 " ret void "1295 "} ",1296 Err, C);1297 1298 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1299 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1}1300 const SCEV *ScevI = SE.getSCEV(getArgByName(F, "i"));1301 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getLower(), 0);1302 EXPECT_EQ(SE.getUnsignedRange(ScevIV).getUpper(), 16);1303 1304 const SCEV *Add = SE.getAddExpr(ScevI, ScevIV);1305 ValueToSCEVMapTy RewriteMap;1306 RewriteMap[cast<SCEVUnknown>(ScevI)->getValue()] =1307 SE.getUMinExpr(ScevI, SE.getConstant(ScevI->getType(), 17));1308 const SCEV *AddWithUMin =1309 SCEVParameterRewriter::rewrite(Add, SE, RewriteMap);1310 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getLower(), 0);1311 EXPECT_EQ(SE.getUnsignedRange(AddWithUMin).getUpper(), 33);1312 });1313}1314 1315TEST_F(ScalarEvolutionsTest, SCEVgetExitLimitForGuardedLoop) {1316 LLVMContext C;1317 SMDiagnostic Err;1318 std::unique_ptr<Module> M = parseAssemblyString(1319 "define void @foo(i32 %i) { "1320 "entry: "1321 " %cmp3 = icmp ult i32 %i, 16 "1322 " br i1 %cmp3, label %loop.body, label %exit "1323 "loop.body: "1324 " %iv = phi i32 [ %iv.next, %loop.body ], [ %i, %entry ] "1325 " %iv.next = add nsw i32 %iv, 1 "1326 " %cmp = icmp eq i32 %iv.next, 16 "1327 " br i1 %cmp, label %exit, label %loop.body "1328 "exit: "1329 " ret void "1330 "} ",1331 Err, C);1332 1333 ASSERT_TRUE(M && "Could not parse module?");1334 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1335 1336 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1337 const SCEV *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); // {0,+,1}1338 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();1339 1340 const SCEV *BTC = SE.getBackedgeTakenCount(L);1341 EXPECT_FALSE(isa<SCEVConstant>(BTC));1342 const SCEV *MaxBTC = SE.getConstantMaxBackedgeTakenCount(L);1343 EXPECT_EQ(cast<SCEVConstant>(MaxBTC)->getAPInt(), 15);1344 });1345}1346 1347TEST_F(ScalarEvolutionsTest, ImpliedViaAddRecStart) {1348 LLVMContext C;1349 SMDiagnostic Err;1350 std::unique_ptr<Module> M = parseAssemblyString(1351 "define void @foo(i32* %p) { "1352 "entry: "1353 " %x = load i32, i32* %p, !range !0 "1354 " br label %loop "1355 "loop: "1356 " %iv = phi i32 [ %x, %entry], [%iv.next, %backedge] "1357 " %ne.check = icmp ne i32 %iv, 0 "1358 " br i1 %ne.check, label %backedge, label %exit "1359 "backedge: "1360 " %iv.next = add i32 %iv, -1 "1361 " br label %loop "1362 "exit:"1363 " ret void "1364 "} "1365 "!0 = !{i32 0, i32 2147483647}",1366 Err, C);1367 1368 ASSERT_TRUE(M && "Could not parse module?");1369 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1370 1371 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1372 const SCEV *X = SE.getSCEV(getInstructionByName(F, "x"));1373 auto *Context = getInstructionByName(F, "iv.next");1374 EXPECT_TRUE(SE.isKnownPredicateAt(ICmpInst::ICMP_NE, X,1375 SE.getZero(X->getType()), Context));1376 });1377}1378 1379TEST_F(ScalarEvolutionsTest, UnsignedIsImpliedViaOperations) {1380 LLVMContext C;1381 SMDiagnostic Err;1382 std::unique_ptr<Module> M =1383 parseAssemblyString("define void @foo(i32* %p1, i32* %p2) { "1384 "entry: "1385 " %x = load i32, i32* %p1, !range !0 "1386 " %cond = icmp ne i32 %x, 0 "1387 " br i1 %cond, label %guarded, label %exit "1388 "guarded: "1389 " %y = add i32 %x, -1 "1390 " ret void "1391 "exit: "1392 " ret void "1393 "} "1394 "!0 = !{i32 0, i32 2147483647}",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 const SCEV *X = SE.getSCEV(getInstructionByName(F, "x"));1402 const SCEV *Y = SE.getSCEV(getInstructionByName(F, "y"));1403 auto *Guarded = getInstructionByName(F, "y")->getParent();1404 ASSERT_TRUE(Guarded);1405 EXPECT_TRUE(1406 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_ULT, Y, X));1407 EXPECT_TRUE(1408 SE.isBasicBlockEntryGuardedByCond(Guarded, ICmpInst::ICMP_UGT, X, Y));1409 });1410}1411 1412TEST_F(ScalarEvolutionsTest, ProveImplicationViaNarrowing) {1413 LLVMContext C;1414 SMDiagnostic Err;1415 std::unique_ptr<Module> M = parseAssemblyString(1416 "define i32 @foo(i32 %start, i32* %q) { "1417 "entry: "1418 " %wide.start = zext i32 %start to i64 "1419 " br label %loop "1420 "loop: "1421 " %wide.iv = phi i64 [%wide.start, %entry], [%wide.iv.next, %backedge] "1422 " %iv = phi i32 [%start, %entry], [%iv.next, %backedge] "1423 " %cond = icmp eq i64 %wide.iv, 0 "1424 " br i1 %cond, label %exit, label %backedge "1425 "backedge: "1426 " %iv.next = add i32 %iv, -1 "1427 " %index = zext i32 %iv.next to i64 "1428 " %load.addr = getelementptr i32, i32* %q, i64 %index "1429 " %stop = load i32, i32* %load.addr "1430 " %loop.cond = icmp eq i32 %stop, 0 "1431 " %wide.iv.next = add nsw i64 %wide.iv, -1 "1432 " br i1 %loop.cond, label %loop, label %failure "1433 "exit: "1434 " ret i32 0 "1435 "failure: "1436 " unreachable "1437 "} ",1438 Err, C);1439 1440 ASSERT_TRUE(M && "Could not parse module?");1441 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1442 1443 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1444 const SCEV *IV = SE.getSCEV(getInstructionByName(F, "iv"));1445 const SCEV *Zero = SE.getZero(IV->getType());1446 auto *Backedge = getInstructionByName(F, "iv.next")->getParent();1447 ASSERT_TRUE(Backedge);1448 (void)IV;1449 (void)Zero;1450 // FIXME: This can only be proved with turned on option1451 // scalar-evolution-use-expensive-range-sharpening which is currently off.1452 // Enable the check once it's switched true by default.1453 // EXPECT_TRUE(SE.isBasicBlockEntryGuardedByCond(Backedge,1454 // ICmpInst::ICMP_UGT,1455 // IV, Zero));1456 });1457}1458 1459TEST_F(ScalarEvolutionsTest, ImpliedCond) {1460 LLVMContext C;1461 SMDiagnostic Err;1462 std::unique_ptr<Module> M = parseAssemblyString(1463 "define void @foo(i32 %len) { "1464 "entry: "1465 " br label %loop "1466 "loop: "1467 " %iv = phi i32 [ 0, %entry], [%iv.next, %loop] "1468 " %iv.next = add nsw i32 %iv, 1 "1469 " %cmp = icmp slt i32 %iv, %len "1470 " br i1 %cmp, label %loop, label %exit "1471 "exit:"1472 " ret void "1473 "}",1474 Err, C);1475 1476 ASSERT_TRUE(M && "Could not parse module?");1477 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1478 1479 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1480 Instruction *IV = getInstructionByName(F, "iv");1481 Type *Ty = IV->getType();1482 const SCEV *Zero = SE.getZero(Ty);1483 const SCEV *MinusOne = SE.getMinusOne(Ty);1484 // {0,+,1}<nuw><nsw>1485 const SCEV *AddRec_0_1 = SE.getSCEV(IV);1486 // {0,+,-1}<nw>1487 const SCEV *AddRec_0_N1 = SE.getNegativeSCEV(AddRec_0_1);1488 1489 // {0,+,1}<nuw><nsw> > 0 -> {0,+,-1}<nw> < 01490 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SLT, AddRec_0_N1, Zero,1491 ICmpInst::ICMP_SGT, AddRec_0_1, Zero));1492 // {0,+,-1}<nw> < -1 -> {0,+,1}<nuw><nsw> > 01493 EXPECT_TRUE(isImpliedCond(SE, ICmpInst::ICMP_SGT, AddRec_0_1, Zero,1494 ICmpInst::ICMP_SLT, AddRec_0_N1, MinusOne));1495 });1496}1497 1498TEST_F(ScalarEvolutionsTest, MatchURem) {1499 LLVMContext C;1500 SMDiagnostic Err;1501 std::unique_ptr<Module> M = parseAssemblyString(1502 "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "1503 " "1504 "define void @test(i32 %a, i32 %b, i16 %c, i64 %d) {"1505 "entry: "1506 " %rem1 = urem i32 %a, 2"1507 " %rem2 = urem i32 %a, 5"1508 " %rem3 = urem i32 %a, %b"1509 " %c.ext = zext i16 %c to i32"1510 " %rem4 = urem i32 %c.ext, 2"1511 " %ext = zext i32 %rem4 to i64"1512 " %rem5 = urem i64 %d, 17179869184"1513 " ret void "1514 "} ",1515 Err, C);1516 1517 assert(M && "Could not parse module?");1518 assert(!verifyModule(*M) && "Must have been well formed!");1519 1520 runWithSE(*M, "test", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1521 for (auto *N : {"rem1", "rem2", "rem3", "rem5"}) {1522 auto *URemI = getInstructionByName(F, N);1523 auto *S = SE.getSCEV(URemI);1524 const SCEV *LHS, *RHS;1525 EXPECT_TRUE(match(S, m_scev_URem(m_SCEV(LHS), m_SCEV(RHS), SE)));1526 EXPECT_EQ(LHS, SE.getSCEV(URemI->getOperand(0)));1527 EXPECT_EQ(RHS, SE.getSCEV(URemI->getOperand(1)));1528 EXPECT_EQ(LHS->getType(), S->getType());1529 EXPECT_EQ(RHS->getType(), S->getType());1530 }1531 1532 // Check the case where the urem operand is zero-extended. Make sure the1533 // match results are extended to the size of the input expression.1534 auto *Ext = getInstructionByName(F, "ext");1535 auto *URem1 = getInstructionByName(F, "rem4");1536 auto *S = SE.getSCEV(Ext);1537 const SCEV *LHS, *RHS;1538 EXPECT_TRUE(match(S, m_scev_URem(m_SCEV(LHS), m_SCEV(RHS), SE)));1539 EXPECT_NE(LHS, SE.getSCEV(URem1->getOperand(0)));1540 // RHS and URem1->getOperand(1) have different widths, so compare the1541 // integer values.1542 EXPECT_EQ(cast<SCEVConstant>(RHS)->getValue()->getZExtValue(),1543 cast<SCEVConstant>(SE.getSCEV(URem1->getOperand(1)))1544 ->getValue()1545 ->getZExtValue());1546 EXPECT_EQ(LHS->getType(), S->getType());1547 EXPECT_EQ(RHS->getType(), S->getType());1548 });1549}1550 1551TEST_F(ScalarEvolutionsTest, SCEVUDivFloorCeiling) {1552 LLVMContext C;1553 SMDiagnostic Err;1554 std::unique_ptr<Module> M = parseAssemblyString("define void @foo() { "1555 " ret void "1556 "} ",1557 Err, C);1558 1559 ASSERT_TRUE(M && "Could not parse module?");1560 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1561 1562 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1563 // Check that SCEV's udiv and uceil handling produce the correct results1564 // for all 8 bit options. Div-by-zero is deliberately excluded.1565 for (unsigned N = 0; N < 256; N++)1566 for (unsigned D = 1; D < 256; D++) {1567 APInt NInt(8, N);1568 APInt DInt(8, D);1569 using namespace llvm::APIntOps;1570 APInt FloorInt = RoundingUDiv(NInt, DInt, APInt::Rounding::DOWN);1571 APInt CeilingInt = RoundingUDiv(NInt, DInt, APInt::Rounding::UP);1572 const SCEV *NS = SE.getConstant(NInt);1573 const SCEV *DS = SE.getConstant(DInt);1574 auto *FloorS = cast<SCEVConstant>(SE.getUDivExpr(NS, DS));1575 auto *CeilingS = cast<SCEVConstant>(SE.getUDivCeilSCEV(NS, DS));1576 ASSERT_TRUE(FloorS->getAPInt() == FloorInt);1577 ASSERT_TRUE(CeilingS->getAPInt() == CeilingInt);1578 }1579 });1580}1581 1582TEST_F(ScalarEvolutionsTest, CheckGetPowerOfTwo) {1583 Module M("CheckGetPowerOfTwo", Context);1584 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false);1585 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M);1586 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);1587 IRBuilder<> Builder(Entry);1588 Builder.CreateRetVoid();1589 ScalarEvolution SE = buildSE(*F);1590 1591 for (unsigned short i = 0; i < 64; ++i)1592 EXPECT_TRUE(1593 dyn_cast<SCEVConstant>(SE.getPowerOfTwo(Type::getInt64Ty(Context), i))1594 ->getValue()1595 ->equalsInt(1ULL << i));1596}1597 1598TEST_F(ScalarEvolutionsTest, ApplyLoopGuards) {1599 LLVMContext C;1600 SMDiagnostic Err;1601 std::unique_ptr<Module> M = parseAssemblyString(1602 "declare void @llvm.assume(i1)\n"1603 "define void @test(i32 %num) {\n"1604 "entry:\n"1605 " %u = urem i32 %num, 4\n"1606 " %cmp = icmp eq i32 %u, 0\n"1607 " tail call void @llvm.assume(i1 %cmp)\n"1608 " %cmp.1 = icmp ugt i32 %num, 0\n"1609 " tail call void @llvm.assume(i1 %cmp.1)\n"1610 " br label %for.body\n"1611 "for.body:\n"1612 " %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"1613 " %inc = add nuw nsw i32 %i.010, 1\n"1614 " %cmp2 = icmp ult i32 %inc, %num\n"1615 " br i1 %cmp2, label %for.body, label %exit\n"1616 "exit:\n"1617 " ret void\n"1618 "}\n",1619 Err, C);1620 1621 ASSERT_TRUE(M && "Could not parse module?");1622 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1623 1624 runWithSE(*M, "test", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1625 const SCEV *TCScev = SE.getSCEV(getArgByName(F, "num"));1626 const SCEV *ApplyLoopGuardsTC = SE.applyLoopGuards(TCScev, *LI.begin());1627 // Assert that the new TC is (4 * ((4 umax %num) /u 4))1628 APInt Four(32, 4);1629 const SCEV *Constant4 = SE.getConstant(Four);1630 const SCEV *Max = SE.getUMaxExpr(TCScev, Constant4);1631 const SCEV *Mul = SE.getMulExpr(SE.getUDivExpr(Max, Constant4), Constant4);1632 ASSERT_TRUE(Mul == ApplyLoopGuardsTC);1633 });1634}1635 1636TEST_F(ScalarEvolutionsTest, ForgetValueWithOverflowInst) {1637 LLVMContext C;1638 SMDiagnostic Err;1639 std::unique_ptr<Module> M = parseAssemblyString(1640 "declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) "1641 "define void @foo(i32 %i) { "1642 "entry: "1643 " br label %loop.body "1644 "loop.body: "1645 " %iv = phi i32 [ %iv.next, %loop.body ], [ 0, %entry ] "1646 " %iv.next = add nsw i32 %iv, 1 "1647 " %call = call {i32, i1} @llvm.smul.with.overflow.i32(i32 %iv, i32 -2) "1648 " %extractvalue = extractvalue {i32, i1} %call, 0 "1649 " %cmp = icmp eq i32 %iv.next, 16 "1650 " br i1 %cmp, label %exit, label %loop.body "1651 "exit: "1652 " ret void "1653 "} ",1654 Err, C);1655 1656 ASSERT_TRUE(M && "Could not parse module?");1657 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1658 1659 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1660 auto *ExtractValue = getInstructionByName(F, "extractvalue");1661 auto *IV = getInstructionByName(F, "iv");1662 1663 auto *ExtractValueScev = SE.getSCEV(ExtractValue);1664 EXPECT_NE(ExtractValueScev, nullptr);1665 1666 SE.forgetValue(IV);1667 auto *ExtractValueScevForgotten = SE.getExistingSCEV(ExtractValue);1668 EXPECT_EQ(ExtractValueScevForgotten, nullptr);1669 });1670}1671 1672TEST_F(ScalarEvolutionsTest, ComplexityComparatorIsStrictWeakOrdering) {1673 // Regression test for a case where caching of equivalent values caused the1674 // comparator to get inconsistent.1675 LLVMContext C;1676 SMDiagnostic Err;1677 std::unique_ptr<Module> M = parseAssemblyString(R"(1678 define i32 @foo(i32 %arg0) {1679 %1 = add i32 %arg0, 11680 %2 = add i32 %arg0, 11681 %3 = xor i32 %2, %11682 %4 = add i32 %3, %21683 %5 = add i32 %arg0, 11684 %6 = xor i32 %5, %arg01685 %7 = add i32 %arg0, %61686 %8 = add i32 %5, %71687 %9 = xor i32 %8, %71688 %10 = add i32 %9, %81689 %11 = xor i32 %10, %91690 %12 = add i32 %11, %101691 %13 = xor i32 %12, %111692 %14 = add i32 %12, %131693 %15 = add i32 %14, %41694 ret i32 %151695 })",1696 Err, C);1697 1698 ASSERT_TRUE(M && "Could not parse module?");1699 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1700 1701 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1702 // When _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG, this will1703 // crash if the comparator has the specific caching bug.1704 SE.getSCEV(F.getEntryBlock().getTerminator()->getOperand(0));1705 });1706}1707 1708TEST_F(ScalarEvolutionsTest, ComplexityComparatorIsStrictWeakOrdering2) {1709 // Regression test for a case where caching of equivalent values caused the1710 // comparator to get inconsistent.1711 1712 Type *Int64Ty = Type::getInt64Ty(Context);1713 Type *PtrTy = PointerType::get(Context, 0);1714 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),1715 {PtrTy, PtrTy, PtrTy, Int64Ty}, false);1716 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);1717 BasicBlock *BB = BasicBlock::Create(Context, "entry", F);1718 ReturnInst::Create(Context, nullptr, BB);1719 1720 ScalarEvolution SE = buildSE(*F);1721 1722 const SCEV *S0 = SE.getSCEV(F->getArg(0));1723 const SCEV *S1 = SE.getSCEV(F->getArg(1));1724 const SCEV *S2 = SE.getSCEV(F->getArg(2));1725 1726 const SCEV *P0 = SE.getPtrToIntExpr(S0, Int64Ty);1727 const SCEV *P1 = SE.getPtrToIntExpr(S1, Int64Ty);1728 const SCEV *P2 = SE.getPtrToIntExpr(S2, Int64Ty);1729 1730 const SCEV *M0 = SE.getNegativeSCEV(P0);1731 const SCEV *M2 = SE.getNegativeSCEV(P2);1732 1733 SmallVector<const SCEV *, 6> Ops = {M2, P0, M0, P1, P2};1734 // When _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG, this will1735 // crash if the comparator has the specific caching bug.1736 SE.getAddExpr(Ops);1737}1738 1739TEST_F(ScalarEvolutionsTest, ComplexityComparatorIsStrictWeakOrdering3) {1740 Type *Int64Ty = Type::getInt64Ty(Context);1741 Constant *Init = Constant::getNullValue(Int64Ty);1742 Type *PtrTy = PointerType::get(Context, 0);1743 Constant *Null = Constant::getNullValue(PtrTy);1744 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false);1745 1746 Value *V0 = new GlobalVariable(M, Int64Ty, false,1747 GlobalValue::ExternalLinkage, Init, "V0");1748 Value *V1 = new GlobalVariable(M, Int64Ty, false,1749 GlobalValue::ExternalLinkage, Init, "V1");1750 Value *V2 = new GlobalVariable(M, Int64Ty, false,1751 GlobalValue::InternalLinkage, Init, "V2");1752 Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);1753 BasicBlock *BB = BasicBlock::Create(Context, "entry", F);1754 Value *C0 = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, V0, Null,1755 "c0", BB);1756 Value *C1 = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, V1, Null,1757 "c1", BB);1758 Value *C2 = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, V2, Null,1759 "c2", BB);1760 Value *Or0 = BinaryOperator::CreateOr(C0, C1, "or0", BB);1761 Value *Or1 = BinaryOperator::CreateOr(Or0, C2, "or1", BB);1762 ReturnInst::Create(Context, nullptr, BB);1763 ScalarEvolution SE = buildSE(*F);1764 // When _LIBCPP_HARDENING_MODE == _LIBCPP_HARDENING_MODE_DEBUG, this will1765 // crash if the comparator is inconsistent about global variable linkage.1766 SE.getSCEV(Or1);1767}1768 1769TEST_F(ScalarEvolutionsTest, SimplifyICmpOperands) {1770 LLVMContext C;1771 SMDiagnostic Err;1772 std::unique_ptr<Module> M =1773 parseAssemblyString("define i32 @foo(ptr %loc, i32 %a, i32 %b) {"1774 "entry: "1775 " ret i32 %a "1776 "} ",1777 Err, C);1778 1779 ASSERT_TRUE(M && "Could not parse module?");1780 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");1781 1782 // Remove common factor when there's no signed wrapping.1783 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1784 const SCEV *A = SE.getSCEV(getArgByName(F, "a"));1785 const SCEV *B = SE.getSCEV(getArgByName(F, "b"));1786 const SCEV *VS = SE.getVScale(A->getType());1787 const SCEV *VSxA = SE.getMulExpr(VS, A, SCEV::FlagNSW);1788 const SCEV *VSxB = SE.getMulExpr(VS, B, SCEV::FlagNSW);1789 1790 {1791 CmpPredicate NewPred = ICmpInst::ICMP_SLT;1792 const SCEV *NewLHS = VSxA;1793 const SCEV *NewRHS = VSxB;1794 EXPECT_TRUE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1795 EXPECT_EQ(NewPred, ICmpInst::ICMP_SLT);1796 EXPECT_EQ(NewLHS, A);1797 EXPECT_EQ(NewRHS, B);1798 }1799 1800 {1801 CmpPredicate NewPred = ICmpInst::ICMP_ULT;1802 const SCEV *NewLHS = VSxA;1803 const SCEV *NewRHS = VSxB;1804 EXPECT_TRUE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1805 EXPECT_EQ(NewPred, ICmpInst::ICMP_ULT);1806 EXPECT_EQ(NewLHS, A);1807 EXPECT_EQ(NewRHS, B);1808 }1809 1810 {1811 CmpPredicate NewPred = ICmpInst::ICMP_EQ;1812 const SCEV *NewLHS = VSxA;1813 const SCEV *NewRHS = VSxB;1814 EXPECT_TRUE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1815 EXPECT_EQ(NewPred, ICmpInst::ICMP_EQ);1816 EXPECT_EQ(NewLHS, A);1817 EXPECT_EQ(NewRHS, B);1818 }1819 1820 // Verify the common factor's position doesn't impede simplification.1821 {1822 const SCEV *C = SE.getConstant(A->getType(), 100);1823 const SCEV *CxVS = SE.getMulExpr(C, VS, SCEV::FlagNSW);1824 1825 // Verify common factor is available at different indices.1826 ASSERT_TRUE(isa<SCEVVScale>(cast<SCEVMulExpr>(VSxA)->getOperand(0)) !=1827 isa<SCEVVScale>(cast<SCEVMulExpr>(CxVS)->getOperand(0)));1828 1829 CmpPredicate NewPred = ICmpInst::ICMP_SLT;1830 const SCEV *NewLHS = VSxA;1831 const SCEV *NewRHS = CxVS;1832 EXPECT_TRUE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1833 EXPECT_EQ(NewPred, ICmpInst::ICMP_SLT);1834 EXPECT_EQ(NewLHS, A);1835 EXPECT_EQ(NewRHS, C);1836 }1837 });1838 1839 // Remove common factor when there's no unsigned wrapping.1840 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1841 const SCEV *A = SE.getSCEV(getArgByName(F, "a"));1842 const SCEV *B = SE.getSCEV(getArgByName(F, "b"));1843 const SCEV *VS = SE.getVScale(A->getType());1844 const SCEV *VSxA = SE.getMulExpr(VS, A, SCEV::FlagNUW);1845 const SCEV *VSxB = SE.getMulExpr(VS, B, SCEV::FlagNUW);1846 1847 {1848 CmpPredicate NewPred = ICmpInst::ICMP_SLT;1849 const SCEV *NewLHS = VSxA;1850 const SCEV *NewRHS = VSxB;1851 EXPECT_FALSE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1852 }1853 1854 {1855 CmpPredicate NewPred = ICmpInst::ICMP_ULT;1856 const SCEV *NewLHS = VSxA;1857 const SCEV *NewRHS = VSxB;1858 EXPECT_TRUE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1859 EXPECT_EQ(NewPred, ICmpInst::ICMP_ULT);1860 EXPECT_EQ(NewLHS, A);1861 EXPECT_EQ(NewRHS, B);1862 }1863 1864 {1865 CmpPredicate NewPred = ICmpInst::ICMP_EQ;1866 const SCEV *NewLHS = VSxA;1867 const SCEV *NewRHS = VSxB;1868 EXPECT_TRUE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1869 EXPECT_EQ(NewPred, ICmpInst::ICMP_EQ);1870 EXPECT_EQ(NewLHS, A);1871 EXPECT_EQ(NewRHS, B);1872 }1873 });1874 1875 // Do not remove common factor due to wrap flag mismatch.1876 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {1877 const SCEV *A = SE.getSCEV(getArgByName(F, "a"));1878 const SCEV *B = SE.getSCEV(getArgByName(F, "b"));1879 const SCEV *VS = SE.getVScale(A->getType());1880 const SCEV *VSxA = SE.getMulExpr(VS, A, SCEV::FlagNSW);1881 const SCEV *VSxB = SE.getMulExpr(VS, B, SCEV::FlagNUW);1882 1883 {1884 CmpPredicate NewPred = ICmpInst::ICMP_SLT;1885 const SCEV *NewLHS = VSxA;1886 const SCEV *NewRHS = VSxB;1887 EXPECT_FALSE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1888 }1889 1890 {1891 CmpPredicate NewPred = ICmpInst::ICMP_ULT;1892 const SCEV *NewLHS = VSxA;1893 const SCEV *NewRHS = VSxB;1894 EXPECT_FALSE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1895 }1896 1897 {1898 CmpPredicate NewPred = ICmpInst::ICMP_EQ;1899 const SCEV *NewLHS = VSxA;1900 const SCEV *NewRHS = VSxB;1901 EXPECT_FALSE(SE.SimplifyICmpOperands(NewPred, NewLHS, NewRHS));1902 }1903 });1904}1905 1906} // end namespace llvm1907