unittests/Analysis/LoopInfoTest.cpp

   1 //===- LoopInfoTest.cpp - LoopInfo 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/Analysis/LoopInfo.h"
  10 #include "llvm/Analysis/AssumptionCache.h"
  11 #include "llvm/Analysis/ScalarEvolution.h"
  12 #include "llvm/Analysis/TargetLibraryInfo.h"
  13 #include "llvm/AsmParser/Parser.h"
  14 #include "llvm/IR/Dominators.h"
  15 #include "llvm/Support/SourceMgr.h"
  16 #include "gtest/gtest.h"
  17
  18 using namespace llvm;
  19
  20 /// Build the loop info for the function and run the Test.
  21 static void
  22 runWithLoopInfo(Module &M, StringRef FuncName,
  23                 function_ref<void(Function &F, LoopInfo &LI)> Test) {
  24   auto *F = M.getFunction(FuncName);
  25   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
  26   // Compute the dominator tree and the loop info for the function.
  27   DominatorTree DT(*F);
  28   LoopInfo LI(DT);
  29   Test(*F, LI);
  30 }
  31
  32 /// Build the loop info and scalar evolution for the function and run the Test.
  33 static void runWithLoopInfoPlus(
  34     Module &M, StringRef FuncName,
  35     function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
  36   auto *F = M.getFunction(FuncName);
  37   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
  38
  39   TargetLibraryInfoImpl TLII;
  40   TargetLibraryInfo TLI(TLII);
  41   AssumptionCache AC(*F);
  42   DominatorTree DT(*F);
  43   LoopInfo LI(DT);
  44   ScalarEvolution SE(*F, TLI, AC, DT, LI);
  45   Test(*F, LI, SE);
  46 }
  47
  48 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
  49                                               const char *ModuleStr) {
  50   SMDiagnostic Err;
  51   return parseAssemblyString(ModuleStr, Err, Context);
  52 }
  53
  54 // This tests that for a loop with a single latch, we get the loop id from
  55 // its only latch, even in case the loop may not be in a simplified form.
  56 TEST(LoopInfoTest, LoopWithSingleLatch) {
  57   const char *ModuleStr =
  58       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
  59       "define void @foo(i32 %n) {\n"
  60       "entry:\n"
  61       "  br i1 undef, label %for.cond, label %for.end\n"
  62       "for.cond:\n"
  63       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
  64       "  %cmp = icmp slt i32 %i.0, %n\n"
  65       "  br i1 %cmp, label %for.inc, label %for.end\n"
  66       "for.inc:\n"
  67       "  %inc = add nsw i32 %i.0, 1\n"
  68       "  br label %for.cond, !llvm.loop !0\n"
  69       "for.end:\n"
  70       "  ret void\n"
  71       "}\n"
  72       "!0 = distinct !{!0, !1}\n"
  73       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
  74
  75   // Parse the module.
  76   LLVMContext Context;
  77   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
  78
  79   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
  80     Function::iterator FI = F.begin();
  81     // First basic block is entry - skip it.
  82     BasicBlock *Header = &*(++FI);
  83     assert(Header->getName() == "for.cond");
  84     Loop *L = LI.getLoopFor(Header);
  85
  86     // This loop is not in simplified form.
  87     EXPECT_FALSE(L->isLoopSimplifyForm());
  88
  89     // Analyze the loop metadata id.
  90     bool loopIDFoundAndSet = false;
  91     // Try to get and set the metadata id for the loop.
  92     if (MDNode *D = L->getLoopID()) {
  93       L->setLoopID(D);
  94       loopIDFoundAndSet = true;
  95     }
  96
  97     // We must have successfully found and set the loop id in the
  98     // only latch the loop has.
  99     EXPECT_TRUE(loopIDFoundAndSet);
 100   });
 101 }
 102
 103 // Test loop id handling for a loop with multiple latches.
 104 TEST(LoopInfoTest, LoopWithMultipleLatches) {
 105   const char *ModuleStr =
 106       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
 107       "define void @foo(i32 %n) {\n"
 108       "entry:\n"
 109       "  br i1 undef, label %for.cond, label %for.end\n"
 110       "for.cond:\n"
 111       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n"
 112       "  %inc = add nsw i32 %i.0, 1\n"
 113       "  %cmp = icmp slt i32 %i.0, %n\n"
 114       "  br i1 %cmp, label %latch.1, label %for.end\n"
 115       "latch.1:\n"
 116       "  br i1 undef, label %for.cond, label %latch.2, !llvm.loop !0\n"
 117       "latch.2:\n"
 118       "  br label %for.cond, !llvm.loop !0\n"
 119       "for.end:\n"
 120       "  ret void\n"
 121       "}\n"
 122       "!0 = distinct !{!0, !1}\n"
 123       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
 124
 125   // Parse the module.
 126   LLVMContext Context;
 127   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 128
 129   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
 130     Function::iterator FI = F.begin();
 131     // First basic block is entry - skip it.
 132     BasicBlock *Header = &*(++FI);
 133     assert(Header->getName() == "for.cond");
 134     Loop *L = LI.getLoopFor(Header);
 135     EXPECT_NE(L, nullptr);
 136
 137     // This loop is not in simplified form.
 138     EXPECT_FALSE(L->isLoopSimplifyForm());
 139
 140     // Try to get and set the metadata id for the loop.
 141     MDNode *OldLoopID = L->getLoopID();
 142     EXPECT_NE(OldLoopID, nullptr);
 143
 144     MDNode *NewLoopID = MDNode::get(Context, {nullptr});
 145     // Set operand 0 to refer to the loop id itself.
 146     NewLoopID->replaceOperandWith(0, NewLoopID);
 147
 148     L->setLoopID(NewLoopID);
 149     EXPECT_EQ(L->getLoopID(), NewLoopID);
 150     EXPECT_NE(L->getLoopID(), OldLoopID);
 151
 152     L->setLoopID(OldLoopID);
 153     EXPECT_EQ(L->getLoopID(), OldLoopID);
 154     EXPECT_NE(L->getLoopID(), NewLoopID);
 155   });
 156 }
 157
 158 TEST(LoopInfoTest, PreorderTraversals) {
 159   const char *ModuleStr = "define void @f() {\n"
 160                           "entry:\n"
 161                           "  br label %loop.0\n"
 162                           "loop.0:\n"
 163                           "  br i1 undef, label %loop.0.0, label %loop.1\n"
 164                           "loop.0.0:\n"
 165                           "  br i1 undef, label %loop.0.0, label %loop.0.1\n"
 166                           "loop.0.1:\n"
 167                           "  br i1 undef, label %loop.0.1, label %loop.0.2\n"
 168                           "loop.0.2:\n"
 169                           "  br i1 undef, label %loop.0.2, label %loop.0\n"
 170                           "loop.1:\n"
 171                           "  br i1 undef, label %loop.1.0, label %end\n"
 172                           "loop.1.0:\n"
 173                           "  br i1 undef, label %loop.1.0, label %loop.1.1\n"
 174                           "loop.1.1:\n"
 175                           "  br i1 undef, label %loop.1.1, label %loop.1.2\n"
 176                           "loop.1.2:\n"
 177                           "  br i1 undef, label %loop.1.2, label %loop.1\n"
 178                           "end:\n"
 179                           "  ret void\n"
 180                           "}\n";
 181   // Parse the module.
 182   LLVMContext Context;
 183   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 184   Function &F = *M->begin();
 185
 186   DominatorTree DT(F);
 187   LoopInfo LI;
 188   LI.analyze(DT);
 189
 190   Function::iterator I = F.begin();
 191   ASSERT_EQ("entry", I->getName());
 192   ++I;
 193   Loop &L_0 = *LI.getLoopFor(&*I++);
 194   ASSERT_EQ("loop.0", L_0.getHeader()->getName());
 195   Loop &L_0_0 = *LI.getLoopFor(&*I++);
 196   ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName());
 197   Loop &L_0_1 = *LI.getLoopFor(&*I++);
 198   ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName());
 199   Loop &L_0_2 = *LI.getLoopFor(&*I++);
 200   ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName());
 201   Loop &L_1 = *LI.getLoopFor(&*I++);
 202   ASSERT_EQ("loop.1", L_1.getHeader()->getName());
 203   Loop &L_1_0 = *LI.getLoopFor(&*I++);
 204   ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName());
 205   Loop &L_1_1 = *LI.getLoopFor(&*I++);
 206   ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName());
 207   Loop &L_1_2 = *LI.getLoopFor(&*I++);
 208   ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName());
 209
 210   auto Preorder = LI.getLoopsInPreorder();
 211   ASSERT_EQ(8u, Preorder.size());
 212   EXPECT_EQ(&L_0, Preorder[0]);
 213   EXPECT_EQ(&L_0_0, Preorder[1]);
 214   EXPECT_EQ(&L_0_1, Preorder[2]);
 215   EXPECT_EQ(&L_0_2, Preorder[3]);
 216   EXPECT_EQ(&L_1, Preorder[4]);
 217   EXPECT_EQ(&L_1_0, Preorder[5]);
 218   EXPECT_EQ(&L_1_1, Preorder[6]);
 219   EXPECT_EQ(&L_1_2, Preorder[7]);
 220
 221   auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder();
 222   ASSERT_EQ(8u, ReverseSiblingPreorder.size());
 223   EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]);
 224   EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]);
 225   EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]);
 226   EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]);
 227   EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]);
 228   EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]);
 229   EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]);
 230   EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]);
 231 }
 232
 233 TEST(LoopInfoTest, CanonicalLoop) {
 234   const char *ModuleStr =
 235       "define void @foo(i32* %A, i32 %ub) {\n"
 236       "entry:\n"
 237       "  %guardcmp = icmp slt i32 0, %ub\n"
 238       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 239       "for.preheader:\n"
 240       "  br label %for.body\n"
 241       "for.body:\n"
 242       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 243       "  %idxprom = sext i32 %i to i64\n"
 244       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 245       "  store i32 %i, i32* %arrayidx, align 4\n"
 246       "  %inc = add nsw i32 %i, 1\n"
 247       "  %cmp = icmp slt i32 %inc, %ub\n"
 248       "  br i1 %cmp, label %for.body, label %for.exit\n"
 249       "for.exit:\n"
 250       "  br label %for.end\n"
 251       "for.end:\n"
 252       "  ret void\n"
 253       "}\n";
 254
 255   // Parse the module.
 256   LLVMContext Context;
 257   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 258
 259   runWithLoopInfoPlus(
 260       *M, "foo",
 261       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 262         Function::iterator FI = F.begin();
 263         BasicBlock *Entry = &*(FI);
 264         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 265         // First two basic block are entry and for.preheader - skip them.
 266         ++FI;
 267         BasicBlock *Header = &*(++FI);
 268         assert(Header->getName() == "for.body");
 269         Loop *L = LI.getLoopFor(Header);
 270         EXPECT_NE(L, nullptr);
 271
 272         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 273         EXPECT_NE(Bounds, None);
 274         ConstantInt *InitialIVValue =
 275             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 276         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 277         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 278         ConstantInt *StepValue =
 279             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 280         EXPECT_TRUE(StepValue && StepValue->isOne());
 281         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 282         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 283         EXPECT_EQ(Bounds->getDirection(),
 284                   Loop::LoopBounds::Direction::Increasing);
 285         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 286         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 287         EXPECT_TRUE(L->isGuarded());
 288       });
 289 }
 290
 291 TEST(LoopInfoTest, LoopWithInverseGuardSuccs) {
 292   const char *ModuleStr =
 293       "define void @foo(i32* %A, i32 %ub) {\n"
 294       "entry:\n"
 295       "  %guardcmp = icmp sge i32 0, %ub\n"
 296       "  br i1 %guardcmp, label %for.end, label %for.preheader\n"
 297       "for.preheader:\n"
 298       "  br label %for.body\n"
 299       "for.body:\n"
 300       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 301       "  %idxprom = sext i32 %i to i64\n"
 302       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 303       "  store i32 %i, i32* %arrayidx, align 4\n"
 304       "  %inc = add nsw i32 %i, 1\n"
 305       "  %cmp = icmp slt i32 %inc, %ub\n"
 306       "  br i1 %cmp, label %for.body, label %for.exit\n"
 307       "for.exit:\n"
 308       "  br label %for.end\n"
 309       "for.end:\n"
 310       "  ret void\n"
 311       "}\n";
 312
 313   // Parse the module.
 314   LLVMContext Context;
 315   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 316
 317   runWithLoopInfoPlus(
 318       *M, "foo",
 319       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 320         Function::iterator FI = F.begin();
 321         BasicBlock *Entry = &*(FI);
 322         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 323         // First two basic block are entry and for.preheader - skip them.
 324         ++FI;
 325         BasicBlock *Header = &*(++FI);
 326         assert(Header->getName() == "for.body");
 327         Loop *L = LI.getLoopFor(Header);
 328         EXPECT_NE(L, nullptr);
 329
 330         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 331         EXPECT_NE(Bounds, None);
 332         ConstantInt *InitialIVValue =
 333             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 334         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 335         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 336         ConstantInt *StepValue =
 337             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 338         EXPECT_TRUE(StepValue && StepValue->isOne());
 339         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 340         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 341         EXPECT_EQ(Bounds->getDirection(),
 342                   Loop::LoopBounds::Direction::Increasing);
 343         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 344         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 345         EXPECT_TRUE(L->isGuarded());
 346       });
 347 }
 348
 349 TEST(LoopInfoTest, LoopWithSwappedGuardCmp) {
 350   const char *ModuleStr =
 351       "define void @foo(i32* %A, i32 %ub) {\n"
 352       "entry:\n"
 353       "  %guardcmp = icmp sgt i32 %ub, 0\n"
 354       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 355       "for.preheader:\n"
 356       "  br label %for.body\n"
 357       "for.body:\n"
 358       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 359       "  %idxprom = sext i32 %i to i64\n"
 360       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 361       "  store i32 %i, i32* %arrayidx, align 4\n"
 362       "  %inc = add nsw i32 %i, 1\n"
 363       "  %cmp = icmp sge i32 %inc, %ub\n"
 364       "  br i1 %cmp, label %for.exit, label %for.body\n"
 365       "for.exit:\n"
 366       "  br label %for.end\n"
 367       "for.end:\n"
 368       "  ret void\n"
 369       "}\n";
 370
 371   // Parse the module.
 372   LLVMContext Context;
 373   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 374
 375   runWithLoopInfoPlus(
 376       *M, "foo",
 377       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 378         Function::iterator FI = F.begin();
 379         BasicBlock *Entry = &*(FI);
 380         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 381         // First two basic block are entry and for.preheader - skip them.
 382         ++FI;
 383         BasicBlock *Header = &*(++FI);
 384         assert(Header->getName() == "for.body");
 385         Loop *L = LI.getLoopFor(Header);
 386         EXPECT_NE(L, nullptr);
 387
 388         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 389         EXPECT_NE(Bounds, None);
 390         ConstantInt *InitialIVValue =
 391             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 392         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 393         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 394         ConstantInt *StepValue =
 395             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 396         EXPECT_TRUE(StepValue && StepValue->isOne());
 397         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 398         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 399         EXPECT_EQ(Bounds->getDirection(),
 400                   Loop::LoopBounds::Direction::Increasing);
 401         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 402         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 403         EXPECT_TRUE(L->isGuarded());
 404       });
 405 }
 406
 407 TEST(LoopInfoTest, LoopWithInverseLatchSuccs) {
 408   const char *ModuleStr =
 409       "define void @foo(i32* %A, i32 %ub) {\n"
 410       "entry:\n"
 411       "  %guardcmp = icmp slt i32 0, %ub\n"
 412       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 413       "for.preheader:\n"
 414       "  br label %for.body\n"
 415       "for.body:\n"
 416       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 417       "  %idxprom = sext i32 %i to i64\n"
 418       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 419       "  store i32 %i, i32* %arrayidx, align 4\n"
 420       "  %inc = add nsw i32 %i, 1\n"
 421       "  %cmp = icmp sge i32 %inc, %ub\n"
 422       "  br i1 %cmp, label %for.exit, label %for.body\n"
 423       "for.exit:\n"
 424       "  br label %for.end\n"
 425       "for.end:\n"
 426       "  ret void\n"
 427       "}\n";
 428
 429   // Parse the module.
 430   LLVMContext Context;
 431   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 432
 433   runWithLoopInfoPlus(
 434       *M, "foo",
 435       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 436         Function::iterator FI = F.begin();
 437         BasicBlock *Entry = &*(FI);
 438         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 439         // First two basic block are entry and for.preheader - skip them.
 440         ++FI;
 441         BasicBlock *Header = &*(++FI);
 442         assert(Header->getName() == "for.body");
 443         Loop *L = LI.getLoopFor(Header);
 444         EXPECT_NE(L, nullptr);
 445
 446         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 447         EXPECT_NE(Bounds, None);
 448         ConstantInt *InitialIVValue =
 449             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 450         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 451         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 452         ConstantInt *StepValue =
 453             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 454         EXPECT_TRUE(StepValue && StepValue->isOne());
 455         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 456         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 457         EXPECT_EQ(Bounds->getDirection(),
 458                   Loop::LoopBounds::Direction::Increasing);
 459         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 460         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 461         EXPECT_TRUE(L->isGuarded());
 462       });
 463 }
 464
 465 TEST(LoopInfoTest, LoopWithLatchCmpNE) {
 466   const char *ModuleStr =
 467       "define void @foo(i32* %A, i32 %ub) {\n"
 468       "entry:\n"
 469       "  %guardcmp = icmp slt i32 0, %ub\n"
 470       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 471       "for.preheader:\n"
 472       "  br label %for.body\n"
 473       "for.body:\n"
 474       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 475       "  %idxprom = sext i32 %i to i64\n"
 476       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 477       "  store i32 %i, i32* %arrayidx, align 4\n"
 478       "  %inc = add nsw i32 %i, 1\n"
 479       "  %cmp = icmp ne i32 %i, %ub\n"
 480       "  br i1 %cmp, label %for.body, label %for.exit\n"
 481       "for.exit:\n"
 482       "  br label %for.end\n"
 483       "for.end:\n"
 484       "  ret void\n"
 485       "}\n";
 486
 487   // Parse the module.
 488   LLVMContext Context;
 489   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 490
 491   runWithLoopInfoPlus(
 492       *M, "foo",
 493       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 494         Function::iterator FI = F.begin();
 495         BasicBlock *Entry = &*(FI);
 496         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 497         // First two basic block are entry and for.preheader - skip them.
 498         ++FI;
 499         BasicBlock *Header = &*(++FI);
 500         assert(Header->getName() == "for.body");
 501         Loop *L = LI.getLoopFor(Header);
 502         EXPECT_NE(L, nullptr);
 503
 504         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 505         EXPECT_NE(Bounds, None);
 506         ConstantInt *InitialIVValue =
 507             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 508         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 509         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 510         ConstantInt *StepValue =
 511             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 512         EXPECT_TRUE(StepValue && StepValue->isOne());
 513         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 514         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 515         EXPECT_EQ(Bounds->getDirection(),
 516                   Loop::LoopBounds::Direction::Increasing);
 517         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 518         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 519         EXPECT_TRUE(L->isGuarded());
 520       });
 521 }
 522
 523 TEST(LoopInfoTest, LoopWithGuardCmpSLE) {
 524   const char *ModuleStr =
 525       "define void @foo(i32* %A, i32 %ub) {\n"
 526       "entry:\n"
 527       "  %ubPlusOne = add i32 %ub, 1\n"
 528       "  %guardcmp = icmp sle i32 0, %ub\n"
 529       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 530       "for.preheader:\n"
 531       "  br label %for.body\n"
 532       "for.body:\n"
 533       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 534       "  %idxprom = sext i32 %i to i64\n"
 535       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 536       "  store i32 %i, i32* %arrayidx, align 4\n"
 537       "  %inc = add nsw i32 %i, 1\n"
 538       "  %cmp = icmp ne i32 %i, %ubPlusOne\n"
 539       "  br i1 %cmp, label %for.body, label %for.exit\n"
 540       "for.exit:\n"
 541       "  br label %for.end\n"
 542       "for.end:\n"
 543       "  ret void\n"
 544       "}\n";
 545
 546   // Parse the module.
 547   LLVMContext Context;
 548   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 549
 550   runWithLoopInfoPlus(
 551       *M, "foo",
 552       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 553         Function::iterator FI = F.begin();
 554         BasicBlock *Entry = &*(FI);
 555         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 556         // First two basic block are entry and for.preheader - skip them.
 557         ++FI;
 558         BasicBlock *Header = &*(++FI);
 559         assert(Header->getName() == "for.body");
 560         Loop *L = LI.getLoopFor(Header);
 561         EXPECT_NE(L, nullptr);
 562
 563         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 564         EXPECT_NE(Bounds, None);
 565         ConstantInt *InitialIVValue =
 566             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 567         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 568         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 569         ConstantInt *StepValue =
 570             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 571         EXPECT_TRUE(StepValue && StepValue->isOne());
 572         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ubPlusOne");
 573         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 574         EXPECT_EQ(Bounds->getDirection(),
 575                   Loop::LoopBounds::Direction::Increasing);
 576         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 577         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 578         EXPECT_TRUE(L->isGuarded());
 579       });
 580 }
 581
 582 TEST(LoopInfoTest, LoopNonConstantStep) {
 583   const char *ModuleStr =
 584       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
 585       "entry:\n"
 586       "  %guardcmp = icmp slt i32 0, %ub\n"
 587       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 588       "for.preheader:\n"
 589       "  br label %for.body\n"
 590       "for.body:\n"
 591       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 592       "  %idxprom = zext i32 %i to i64\n"
 593       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 594       "  store i32 %i, i32* %arrayidx, align 4\n"
 595       "  %inc = add nsw i32 %i, %step\n"
 596       "  %cmp = icmp slt i32 %inc, %ub\n"
 597       "  br i1 %cmp, label %for.body, label %for.exit\n"
 598       "for.exit:\n"
 599       "  br label %for.end\n"
 600       "for.end:\n"
 601       "  ret void\n"
 602       "}\n";
 603
 604   // Parse the module.
 605   LLVMContext Context;
 606   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 607
 608   runWithLoopInfoPlus(
 609       *M, "foo",
 610       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 611         Function::iterator FI = F.begin();
 612         BasicBlock *Entry = &*(FI);
 613         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 614         // First two basic block are entry and for.preheader - skip them.
 615         ++FI;
 616         BasicBlock *Header = &*(++FI);
 617         assert(Header->getName() == "for.body");
 618         Loop *L = LI.getLoopFor(Header);
 619         EXPECT_NE(L, nullptr);
 620
 621         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 622         EXPECT_NE(Bounds, None);
 623         ConstantInt *InitialIVValue =
 624             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 625         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 626         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 627         EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
 628         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 629         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 630         EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
 631         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 632         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 633         EXPECT_TRUE(L->isGuarded());
 634       });
 635 }
 636
 637 TEST(LoopInfoTest, LoopUnsignedBounds) {
 638   const char *ModuleStr =
 639       "define void @foo(i32* %A, i32 %ub) {\n"
 640       "entry:\n"
 641       "  %guardcmp = icmp ult i32 0, %ub\n"
 642       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 643       "for.preheader:\n"
 644       "  br label %for.body\n"
 645       "for.body:\n"
 646       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 647       "  %idxprom = zext i32 %i to i64\n"
 648       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 649       "  store i32 %i, i32* %arrayidx, align 4\n"
 650       "  %inc = add i32 %i, 1\n"
 651       "  %cmp = icmp ult i32 %inc, %ub\n"
 652       "  br i1 %cmp, label %for.body, label %for.exit\n"
 653       "for.exit:\n"
 654       "  br label %for.end\n"
 655       "for.end:\n"
 656       "  ret void\n"
 657       "}\n";
 658
 659   // Parse the module.
 660   LLVMContext Context;
 661   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 662
 663   runWithLoopInfoPlus(
 664       *M, "foo",
 665       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 666         Function::iterator FI = F.begin();
 667         BasicBlock *Entry = &*(FI);
 668         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 669         // First two basic block are entry and for.preheader - skip them.
 670         ++FI;
 671         BasicBlock *Header = &*(++FI);
 672         assert(Header->getName() == "for.body");
 673         Loop *L = LI.getLoopFor(Header);
 674         EXPECT_NE(L, nullptr);
 675
 676         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 677         EXPECT_NE(Bounds, None);
 678         ConstantInt *InitialIVValue =
 679             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 680         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 681         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 682         ConstantInt *StepValue =
 683             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 684         EXPECT_TRUE(StepValue && StepValue->isOne());
 685         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 686         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_ULT);
 687         EXPECT_EQ(Bounds->getDirection(),
 688                   Loop::LoopBounds::Direction::Increasing);
 689         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 690         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 691         EXPECT_TRUE(L->isGuarded());
 692       });
 693 }
 694
 695 TEST(LoopInfoTest, DecreasingLoop) {
 696   const char *ModuleStr =
 697       "define void @foo(i32* %A, i32 %ub) {\n"
 698       "entry:\n"
 699       "  %guardcmp = icmp slt i32 0, %ub\n"
 700       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 701       "for.preheader:\n"
 702       "  br label %for.body\n"
 703       "for.body:\n"
 704       "  %i = phi i32 [ %ub, %for.preheader ], [ %inc, %for.body ]\n"
 705       "  %idxprom = sext i32 %i to i64\n"
 706       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 707       "  store i32 %i, i32* %arrayidx, align 4\n"
 708       "  %inc = sub nsw i32 %i, 1\n"
 709       "  %cmp = icmp sgt i32 %inc, 0\n"
 710       "  br i1 %cmp, label %for.body, label %for.exit\n"
 711       "for.exit:\n"
 712       "  br label %for.end\n"
 713       "for.end:\n"
 714       "  ret void\n"
 715       "}\n";
 716
 717   // Parse the module.
 718   LLVMContext Context;
 719   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 720
 721   runWithLoopInfoPlus(
 722       *M, "foo",
 723       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 724         Function::iterator FI = F.begin();
 725         BasicBlock *Entry = &*(FI);
 726         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 727         // First two basic block are entry and for.preheader - skip them.
 728         ++FI;
 729         BasicBlock *Header = &*(++FI);
 730         assert(Header->getName() == "for.body");
 731         Loop *L = LI.getLoopFor(Header);
 732         EXPECT_NE(L, nullptr);
 733
 734         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 735         EXPECT_NE(Bounds, None);
 736         EXPECT_EQ(Bounds->getInitialIVValue().getName(), "ub");
 737         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 738         ConstantInt *StepValue =
 739             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 740         EXPECT_EQ(StepValue, nullptr);
 741         ConstantInt *FinalIVValue =
 742             dyn_cast<ConstantInt>(&Bounds->getFinalIVValue());
 743         EXPECT_TRUE(FinalIVValue && FinalIVValue->isZero());
 744         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SGT);
 745         EXPECT_EQ(Bounds->getDirection(),
 746                   Loop::LoopBounds::Direction::Decreasing);
 747         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 748         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 749         EXPECT_TRUE(L->isGuarded());
 750       });
 751 }
 752
 753 TEST(LoopInfoTest, CannotFindDirection) {
 754   const char *ModuleStr =
 755       "define void @foo(i32* %A, i32 %ub, i32 %step) {\n"
 756       "entry:\n"
 757       "  %guardcmp = icmp slt i32 0, %ub\n"
 758       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 759       "for.preheader:\n"
 760       "  br label %for.body\n"
 761       "for.body:\n"
 762       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 763       "  %idxprom = sext i32 %i to i64\n"
 764       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 765       "  store i32 %i, i32* %arrayidx, align 4\n"
 766       "  %inc = add nsw i32 %i, %step\n"
 767       "  %cmp = icmp ne i32 %i, %ub\n"
 768       "  br i1 %cmp, label %for.body, label %for.exit\n"
 769       "for.exit:\n"
 770       "  br label %for.end\n"
 771       "for.end:\n"
 772       "  ret void\n"
 773       "}\n";
 774
 775   // Parse the module.
 776   LLVMContext Context;
 777   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 778
 779   runWithLoopInfoPlus(
 780       *M, "foo",
 781       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 782         Function::iterator FI = F.begin();
 783         BasicBlock *Entry = &*(FI);
 784         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 785         // First two basic block are entry and for.preheader
 786         // - skip them.
 787         ++FI;
 788         BasicBlock *Header = &*(++FI);
 789         assert(Header->getName() == "for.body");
 790         Loop *L = LI.getLoopFor(Header);
 791         EXPECT_NE(L, nullptr);
 792
 793         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 794         EXPECT_NE(Bounds, None);
 795         ConstantInt *InitialIVValue =
 796             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 797         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 798         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 799         EXPECT_EQ(Bounds->getStepValue()->getName(), "step");
 800         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 801         EXPECT_EQ(Bounds->getCanonicalPredicate(),
 802                   ICmpInst::BAD_ICMP_PREDICATE);
 803         EXPECT_EQ(Bounds->getDirection(), Loop::LoopBounds::Direction::Unknown);
 804         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 805         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 806         EXPECT_TRUE(L->isGuarded());
 807       });
 808 }
 809
 810 TEST(LoopInfoTest, ZextIndVar) {
 811   const char *ModuleStr =
 812       "define void @foo(i32* %A, i32 %ub) {\n"
 813       "entry:\n"
 814       "  %guardcmp = icmp slt i32 0, %ub\n"
 815       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 816       "for.preheader:\n"
 817       "  br label %for.body\n"
 818       "for.body:\n"
 819       "  %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %for.body ]\n"
 820       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 821       "  %idxprom = sext i32 %i to i64\n"
 822       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 823       "  store i32 %i, i32* %arrayidx, align 4\n"
 824       "  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n"
 825       "  %inc = add nsw i32 %i, 1\n"
 826       "  %wide.trip.count = zext i32 %ub to i64\n"
 827       "  %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n"
 828       "  br i1 %exitcond, label %for.body, label %for.exit\n"
 829       "for.exit:\n"
 830       "  br label %for.end\n"
 831       "for.end:\n"
 832       "  ret void\n"
 833       "}\n";
 834
 835   // Parse the module.
 836   LLVMContext Context;
 837   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 838
 839   runWithLoopInfoPlus(
 840       *M, "foo",
 841       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 842         Function::iterator FI = F.begin();
 843         BasicBlock *Entry = &*(FI);
 844         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 845         // First two basic block are entry and for.preheader - skip them.
 846         ++FI;
 847         BasicBlock *Header = &*(++FI);
 848         assert(Header->getName() == "for.body");
 849         Loop *L = LI.getLoopFor(Header);
 850         EXPECT_NE(L, nullptr);
 851
 852         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 853         EXPECT_NE(Bounds, None);
 854         ConstantInt *InitialIVValue =
 855             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 856         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 857         EXPECT_EQ(Bounds->getStepInst().getName(), "indvars.iv.next");
 858         ConstantInt *StepValue =
 859             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 860         EXPECT_TRUE(StepValue && StepValue->isOne());
 861         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "wide.trip.count");
 862         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_NE);
 863         EXPECT_EQ(Bounds->getDirection(),
 864                   Loop::LoopBounds::Direction::Increasing);
 865         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "indvars.iv");
 866         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 867         EXPECT_TRUE(L->isGuarded());
 868       });
 869 }
 870
 871 TEST(LoopInfoTest, UnguardedLoop) {
 872   const char *ModuleStr =
 873       "define void @foo(i32* %A, i32 %ub) {\n"
 874       "entry:\n"
 875       "  br label %for.body\n"
 876       "for.body:\n"
 877       "  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
 878       "  %idxprom = sext i32 %i to i64\n"
 879       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 880       "  store i32 %i, i32* %arrayidx, align 4\n"
 881       "  %inc = add nsw i32 %i, 1\n"
 882       "  %cmp = icmp slt i32 %inc, %ub\n"
 883       "  br i1 %cmp, label %for.body, label %for.exit\n"
 884       "for.exit:\n"
 885       "  br label %for.end\n"
 886       "for.end:\n"
 887       "  ret void\n"
 888       "}\n";
 889
 890   // Parse the module.
 891   LLVMContext Context;
 892   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 893
 894   runWithLoopInfoPlus(
 895       *M, "foo",
 896       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 897         Function::iterator FI = F.begin();
 898         // First basic block is entry - skip it.
 899         BasicBlock *Header = &*(++FI);
 900         assert(Header->getName() == "for.body");
 901         Loop *L = LI.getLoopFor(Header);
 902         EXPECT_NE(L, nullptr);
 903
 904         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 905         EXPECT_NE(Bounds, None);
 906         ConstantInt *InitialIVValue =
 907             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 908         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 909         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 910         ConstantInt *StepValue =
 911             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 912         EXPECT_TRUE(StepValue && StepValue->isOne());
 913         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 914         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 915         EXPECT_EQ(Bounds->getDirection(),
 916                   Loop::LoopBounds::Direction::Increasing);
 917         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 918         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
 919         EXPECT_FALSE(L->isGuarded());
 920       });
 921 }
 922
 923 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) {
 924   const char *ModuleStr =
 925       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
 926       "entry:\n"
 927       "  br i1 %cond, label %for.preheader, label %for.end\n"
 928       "for.preheader:\n"
 929       "  br label %for.body\n"
 930       "for.body:\n"
 931       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
 932       "  %idxprom = sext i32 %i to i64\n"
 933       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 934       "  store i32 %i, i32* %arrayidx, align 4\n"
 935       "  %inc = add nsw i32 %i, 1\n"
 936       "  %cmp = icmp slt i32 %inc, %ub\n"
 937       "  br i1 %cmp, label %for.body, label %for.exit\n"
 938       "for.exit:\n"
 939       "  br label %for.end\n"
 940       "for.end:\n"
 941       "  ret void\n"
 942       "}\n";
 943
 944   // Parse the module.
 945   LLVMContext Context;
 946   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 947
 948   runWithLoopInfoPlus(
 949       *M, "foo",
 950       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 951         Function::iterator FI = F.begin();
 952         BasicBlock *Entry = &*(FI);
 953         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 954         // First two basic block are entry and for.preheader - skip them.
 955         ++FI;
 956         BasicBlock *Header = &*(++FI);
 957         assert(Header->getName() == "for.body");
 958         Loop *L = LI.getLoopFor(Header);
 959         EXPECT_NE(L, nullptr);
 960
 961         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 962         EXPECT_NE(Bounds, None);
 963         ConstantInt *InitialIVValue =
 964             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 965         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 966         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 967         ConstantInt *StepValue =
 968             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 969         EXPECT_TRUE(StepValue && StepValue->isOne());
 970         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 971         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 972         EXPECT_EQ(Bounds->getDirection(),
 973                   Loop::LoopBounds::Direction::Increasing);
 974         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 975         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 976         EXPECT_TRUE(L->isGuarded());
 977       });
 978 }
 979
 980 TEST(LoopInfoTest, LoopNest) {
 981   const char *ModuleStr =
 982       "define void @foo(i32* %A, i32 %ub) {\n"
 983       "entry:\n"
 984       "  %guardcmp = icmp slt i32 0, %ub\n"
 985       "  br i1 %guardcmp, label %for.outer.preheader, label %for.end\n"
 986       "for.outer.preheader:\n"
 987       "  br label %for.outer\n"
 988       "for.outer:\n"
 989       "  %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n"
 990       "  br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n"
 991       "for.inner.preheader:\n"
 992       "  br label %for.inner\n"
 993       "for.inner:\n"
 994       "  %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n"
 995       "  %idxprom = sext i32 %i to i64\n"
 996       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 997       "  store i32 %i, i32* %arrayidx, align 4\n"
 998       "  %inc = add nsw i32 %i, 1\n"
 999       "  %cmp = icmp slt i32 %inc, %ub\n"
1000       "  br i1 %cmp, label %for.inner, label %for.inner.exit\n"
1001       "for.inner.exit:\n"
1002       "  br label %for.outer.latch\n"
1003       "for.outer.latch:\n"
1004       "  %inc.outer = add nsw i32 %j, 1\n"
1005       "  %cmp.outer = icmp slt i32 %inc.outer, %ub\n"
1006       "  br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n"
1007       "for.outer.exit:\n"
1008       "  br label %for.end\n"
1009       "for.end:\n"
1010       "  ret void\n"
1011       "}\n";
1012
1013   // Parse the module.
1014   LLVMContext Context;
1015   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1016
1017   runWithLoopInfoPlus(
1018       *M, "foo",
1019       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1020         Function::iterator FI = F.begin();
1021         BasicBlock *Entry = &*(FI);
1022         BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator());
1023         // First two basic block are entry and for.outer.preheader - skip them.
1024         ++FI;
1025         BasicBlock *Header = &*(++FI);
1026         assert(Header->getName() == "for.outer");
1027         BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator());
1028         Loop *L = LI.getLoopFor(Header);
1029         EXPECT_NE(L, nullptr);
1030
1031         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1032         EXPECT_NE(Bounds, None);
1033         ConstantInt *InitialIVValue =
1034             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1035         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1036         EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer");
1037         ConstantInt *StepValue =
1038             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1039         EXPECT_TRUE(StepValue && StepValue->isOne());
1040         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1041         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1042         EXPECT_EQ(Bounds->getDirection(),
1043                   Loop::LoopBounds::Direction::Increasing);
1044         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j");
1045         EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard);
1046         EXPECT_TRUE(L->isGuarded());
1047
1048         // Next two basic blocks are for.outer and for.inner.preheader - skip
1049         // them.
1050         ++FI;
1051         Header = &*(++FI);
1052         assert(Header->getName() == "for.inner");
1053         L = LI.getLoopFor(Header);
1054         EXPECT_NE(L, nullptr);
1055
1056         Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE);
1057         EXPECT_NE(InnerBounds, None);
1058         InitialIVValue =
1059             dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue());
1060         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1061         EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc");
1062         StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue());
1063         EXPECT_TRUE(StepValue && StepValue->isOne());
1064         EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub");
1065         EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1066         EXPECT_EQ(InnerBounds->getDirection(),
1067                   Loop::LoopBounds::Direction::Increasing);
1068         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1069         EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard);
1070         EXPECT_TRUE(L->isGuarded());
1071       });
1072 }
1073
1074 TEST(LoopInfoTest, AuxiliaryIV) {
1075   const char *ModuleStr =
1076       "define void @foo(i32* %A, i32 %ub) {\n"
1077       "entry:\n"
1078       "  %guardcmp = icmp slt i32 0, %ub\n"
1079       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
1080       "for.preheader:\n"
1081       "  br label %for.body\n"
1082       "for.body:\n"
1083       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1084       "  %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n"
1085       "  %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n"
1086       "  %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n"
1087       "  %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n"
1088       "  %idxprom = sext i32 %i to i64\n"
1089       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1090       "  store i32 %i, i32* %arrayidx, align 4\n"
1091       "  %mulopcodeinc = mul nsw i32 %mulopcode, 5\n"
1092       "  %usedoutsideinc = add nsw i32 %usedoutside, 5\n"
1093       "  %loopvariantinc = add nsw i32 %loopvariant, %i\n"
1094       "  %auxinc = add nsw i32 %aux, 5\n"
1095       "  %inc = add nsw i32 %i, 1\n"
1096       "  %cmp = icmp slt i32 %inc, %ub\n"
1097       "  br i1 %cmp, label %for.body, label %for.exit\n"
1098       "for.exit:\n"
1099       "  %lcssa = phi i32 [ %usedoutside, %for.body ]\n"
1100       "  br label %for.end\n"
1101       "for.end:\n"
1102       "  ret void\n"
1103       "}\n";
1104
1105   // Parse the module.
1106   LLVMContext Context;
1107   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1108
1109   runWithLoopInfoPlus(
1110       *M, "foo",
1111       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1112         Function::iterator FI = F.begin();
1113         BasicBlock *Entry = &*(FI);
1114         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
1115         // First two basic block are entry and for.preheader - skip them.
1116         ++FI;
1117         BasicBlock *Header = &*(++FI);
1118         assert(Header->getName() == "for.body");
1119         Loop *L = LI.getLoopFor(Header);
1120         EXPECT_NE(L, nullptr);
1121
1122         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1123         EXPECT_NE(Bounds, None);
1124         ConstantInt *InitialIVValue =
1125             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1126         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1127         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1128         ConstantInt *StepValue =
1129             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1130         EXPECT_TRUE(StepValue && StepValue->isOne());
1131         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1132         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1133         EXPECT_EQ(Bounds->getDirection(),
1134                   Loop::LoopBounds::Direction::Increasing);
1135         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1136         BasicBlock::iterator II = Header->begin();
1137         PHINode &Instruction_i = cast<PHINode>(*(II));
1138         EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE));
1139         PHINode &Instruction_aux = cast<PHINode>(*(++II));
1140         EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE));
1141         PHINode &Instruction_loopvariant = cast<PHINode>(*(++II));
1142         EXPECT_FALSE(
1143             L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE));
1144         PHINode &Instruction_usedoutside = cast<PHINode>(*(++II));
1145         EXPECT_FALSE(
1146             L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE));
1147         PHINode &Instruction_mulopcode = cast<PHINode>(*(++II));
1148         EXPECT_FALSE(
1149             L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE));
1150         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
1151         EXPECT_TRUE(L->isGuarded());
1152       });
1153 }
1154
1155 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions.
1156 TEST(LoopInfoTest, LoopUniqueExitBlocks) {
1157   const char *ModuleStr =
1158       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1159       "define void @foo(i32 %n, i1 %cond) {\n"
1160       "entry:\n"
1161       "  br label %for.cond\n"
1162       "for.cond:\n"
1163       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1164       "  %cmp = icmp slt i32 %i.0, %n\n"
1165       "  br i1 %cond, label %for.inc, label %for.end1\n"
1166       "for.inc:\n"
1167       "  %inc = add nsw i32 %i.0, 1\n"
1168       "  br i1 %cmp, label %for.cond, label %for.end2, !llvm.loop !0\n"
1169       "for.end1:\n"
1170       "  br label %for.end\n"
1171       "for.end2:\n"
1172       "  br label %for.end\n"
1173       "for.end:\n"
1174       "  ret void\n"
1175       "}\n"
1176       "!0 = distinct !{!0, !1}\n"
1177       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1178
1179   // Parse the module.
1180   LLVMContext Context;
1181   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1182
1183   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1184     Function::iterator FI = F.begin();
1185     // First basic block is entry - skip it.
1186     BasicBlock *Header = &*(++FI);
1187     assert(Header->getName() == "for.cond");
1188     Loop *L = LI.getLoopFor(Header);
1189
1190     SmallVector<BasicBlock *, 2> Exits;
1191     // This loop has 2 unique exits.
1192     L->getUniqueExitBlocks(Exits);
1193     EXPECT_TRUE(Exits.size() == 2);
1194     // And one unique non latch exit.
1195     Exits.clear();
1196     L->getUniqueNonLatchExitBlocks(Exits);
1197     EXPECT_TRUE(Exits.size() == 1);
1198   });
1199 }
1200
1201 // Regression test for  getUniqueNonLatchExitBlocks functions.
1202 // It should detect the exit if it comes from both latch and non-latch blocks.
1203 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) {
1204   const char *ModuleStr =
1205       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1206       "define void @foo(i32 %n, i1 %cond) {\n"
1207       "entry:\n"
1208       "  br label %for.cond\n"
1209       "for.cond:\n"
1210       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1211       "  %cmp = icmp slt i32 %i.0, %n\n"
1212       "  br i1 %cond, label %for.inc, label %for.end\n"
1213       "for.inc:\n"
1214       "  %inc = add nsw i32 %i.0, 1\n"
1215       "  br i1 %cmp, label %for.cond, label %for.end, !llvm.loop !0\n"
1216       "for.end:\n"
1217       "  ret void\n"
1218       "}\n"
1219       "!0 = distinct !{!0, !1}\n"
1220       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1221
1222   // Parse the module.
1223   LLVMContext Context;
1224   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1225
1226   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1227     Function::iterator FI = F.begin();
1228     // First basic block is entry - skip it.
1229     BasicBlock *Header = &*(++FI);
1230     assert(Header->getName() == "for.cond");
1231     Loop *L = LI.getLoopFor(Header);
1232
1233     SmallVector<BasicBlock *, 2> Exits;
1234     // This loop has 1 unique exit.
1235     L->getUniqueExitBlocks(Exits);
1236     EXPECT_TRUE(Exits.size() == 1);
1237     // And one unique non latch exit.
1238     Exits.clear();
1239     L->getUniqueNonLatchExitBlocks(Exits);
1240     EXPECT_TRUE(Exits.size() == 1);
1241   });
1242 }