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