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