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, MultiExitingLoop) {
 872   const char *ModuleStr =
 873       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
 874       "entry:\n"
 875       "  %guardcmp = icmp slt i32 0, %ub\n"
 876       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 877       "for.preheader:\n"
 878       "  br label %for.body\n"
 879       "for.body:\n"
 880       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n"
 881       "  br i1 %cond, label %for.body.1, label %for.exit\n"
 882       "for.body.1:\n"
 883       "  %idxprom = sext i32 %i to i64\n"
 884       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 885       "  store i32 %i, i32* %arrayidx, align 4\n"
 886       "  %inc = add nsw i32 %i, 1\n"
 887       "  %cmp = icmp slt i32 %inc, %ub\n"
 888       "  br i1 %cmp, label %for.body, label %for.exit\n"
 889       "for.exit:\n"
 890       "  br label %for.end\n"
 891       "for.end:\n"
 892       "  ret void\n"
 893       "}\n";
 894
 895   // Parse the module.
 896   LLVMContext Context;
 897   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 898
 899   runWithLoopInfoPlus(
 900       *M, "foo",
 901       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 902         Function::iterator FI = F.begin();
 903         BasicBlock *Entry = &*(FI);
 904         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
 905         // First two basic block are entry and for.preheader - skip them.
 906         ++FI;
 907         BasicBlock *Header = &*(++FI);
 908         assert(Header->getName() == "for.body");
 909         Loop *L = LI.getLoopFor(Header);
 910         EXPECT_NE(L, nullptr);
 911
 912         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 913         EXPECT_NE(Bounds, None);
 914         ConstantInt *InitialIVValue =
 915             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 916         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 917         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 918         ConstantInt *StepValue =
 919             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 920         EXPECT_TRUE(StepValue && StepValue->isOne());
 921         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 922         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 923         EXPECT_EQ(Bounds->getDirection(),
 924                   Loop::LoopBounds::Direction::Increasing);
 925         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 926         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
 927         EXPECT_TRUE(L->isGuarded());
 928       });
 929 }
 930
 931 TEST(LoopInfoTest, MultiExitLoop) {
 932   const char *ModuleStr =
 933       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
 934       "entry:\n"
 935       "  %guardcmp = icmp slt i32 0, %ub\n"
 936       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
 937       "for.preheader:\n"
 938       "  br label %for.body\n"
 939       "for.body:\n"
 940       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body.1 ]\n"
 941       "  br i1 %cond, label %for.body.1, label %for.exit\n"
 942       "for.body.1:\n"
 943       "  %idxprom = sext i32 %i to i64\n"
 944       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
 945       "  store i32 %i, i32* %arrayidx, align 4\n"
 946       "  %inc = add nsw i32 %i, 1\n"
 947       "  %cmp = icmp slt i32 %inc, %ub\n"
 948       "  br i1 %cmp, label %for.body, label %for.exit.1\n"
 949       "for.exit:\n"
 950       "  br label %for.end\n"
 951       "for.exit.1:\n"
 952       "  br label %for.end\n"
 953       "for.end:\n"
 954       "  ret void\n"
 955       "}\n";
 956
 957   // Parse the module.
 958   LLVMContext Context;
 959   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 960
 961   runWithLoopInfoPlus(
 962       *M, "foo",
 963       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 964         Function::iterator FI = F.begin();
 965         // First two basic block are entry and for.preheader - skip them.
 966         ++FI;
 967         BasicBlock *Header = &*(++FI);
 968         assert(Header->getName() == "for.body");
 969         Loop *L = LI.getLoopFor(Header);
 970         EXPECT_NE(L, nullptr);
 971
 972         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
 973         EXPECT_NE(Bounds, None);
 974         ConstantInt *InitialIVValue =
 975             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
 976         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
 977         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
 978         ConstantInt *StepValue =
 979             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
 980         EXPECT_TRUE(StepValue && StepValue->isOne());
 981         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
 982         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
 983         EXPECT_EQ(Bounds->getDirection(),
 984                   Loop::LoopBounds::Direction::Increasing);
 985         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
 986         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
 987         EXPECT_FALSE(L->isGuarded());
 988       });
 989 }
 990
 991 TEST(LoopInfoTest, UnguardedLoop) {
 992   const char *ModuleStr =
 993       "define void @foo(i32* %A, i32 %ub) {\n"
 994       "entry:\n"
 995       "  br label %for.body\n"
 996       "for.body:\n"
 997       "  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
 998       "  %idxprom = sext i32 %i to i64\n"
 999       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1000       "  store i32 %i, i32* %arrayidx, align 4\n"
1001       "  %inc = add nsw i32 %i, 1\n"
1002       "  %cmp = icmp slt i32 %inc, %ub\n"
1003       "  br i1 %cmp, label %for.body, label %for.exit\n"
1004       "for.exit:\n"
1005       "  br label %for.end\n"
1006       "for.end:\n"
1007       "  ret void\n"
1008       "}\n";
1009
1010   // Parse the module.
1011   LLVMContext Context;
1012   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1013
1014   runWithLoopInfoPlus(
1015       *M, "foo",
1016       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1017         Function::iterator FI = F.begin();
1018         // First basic block is entry - skip it.
1019         BasicBlock *Header = &*(++FI);
1020         assert(Header->getName() == "for.body");
1021         Loop *L = LI.getLoopFor(Header);
1022         EXPECT_NE(L, nullptr);
1023
1024         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1025         EXPECT_NE(Bounds, None);
1026         ConstantInt *InitialIVValue =
1027             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1028         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1029         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1030         ConstantInt *StepValue =
1031             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1032         EXPECT_TRUE(StepValue && StepValue->isOne());
1033         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1034         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1035         EXPECT_EQ(Bounds->getDirection(),
1036                   Loop::LoopBounds::Direction::Increasing);
1037         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1038         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1039         EXPECT_FALSE(L->isGuarded());
1040       });
1041 }
1042
1043 TEST(LoopInfoTest, UnguardedLoopWithControlFlow) {
1044   const char *ModuleStr =
1045       "define void @foo(i32* %A, i32 %ub, i1 %cond) {\n"
1046       "entry:\n"
1047       "  br i1 %cond, label %for.preheader, label %for.end\n"
1048       "for.preheader:\n"
1049       "  br label %for.body\n"
1050       "for.body:\n"
1051       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1052       "  %idxprom = sext i32 %i to i64\n"
1053       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1054       "  store i32 %i, i32* %arrayidx, align 4\n"
1055       "  %inc = add nsw i32 %i, 1\n"
1056       "  %cmp = icmp slt i32 %inc, %ub\n"
1057       "  br i1 %cmp, label %for.body, label %for.exit\n"
1058       "for.exit:\n"
1059       "  br label %for.end\n"
1060       "for.end:\n"
1061       "  ret void\n"
1062       "}\n";
1063
1064   // Parse the module.
1065   LLVMContext Context;
1066   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1067
1068   runWithLoopInfoPlus(
1069       *M, "foo",
1070       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1071         Function::iterator FI = F.begin();
1072         BasicBlock *Entry = &*(FI);
1073         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
1074         // First two basic block are entry and for.preheader - skip them.
1075         ++FI;
1076         BasicBlock *Header = &*(++FI);
1077         assert(Header->getName() == "for.body");
1078         Loop *L = LI.getLoopFor(Header);
1079         EXPECT_NE(L, nullptr);
1080
1081         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1082         EXPECT_NE(Bounds, None);
1083         ConstantInt *InitialIVValue =
1084             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1085         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1086         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1087         ConstantInt *StepValue =
1088             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1089         EXPECT_TRUE(StepValue && StepValue->isOne());
1090         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1091         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1092         EXPECT_EQ(Bounds->getDirection(),
1093                   Loop::LoopBounds::Direction::Increasing);
1094         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1095         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
1096         EXPECT_TRUE(L->isGuarded());
1097       });
1098 }
1099
1100 TEST(LoopInfoTest, LoopNest) {
1101   const char *ModuleStr =
1102       "define void @foo(i32* %A, i32 %ub) {\n"
1103       "entry:\n"
1104       "  %guardcmp = icmp slt i32 0, %ub\n"
1105       "  br i1 %guardcmp, label %for.outer.preheader, label %for.end\n"
1106       "for.outer.preheader:\n"
1107       "  br label %for.outer\n"
1108       "for.outer:\n"
1109       "  %j = phi i32 [ 0, %for.outer.preheader ], [ %inc.outer, %for.outer.latch ]\n"
1110       "  br i1 %guardcmp, label %for.inner.preheader, label %for.outer.latch\n"
1111       "for.inner.preheader:\n"
1112       "  br label %for.inner\n"
1113       "for.inner:\n"
1114       "  %i = phi i32 [ 0, %for.inner.preheader ], [ %inc, %for.inner ]\n"
1115       "  %idxprom = sext i32 %i to i64\n"
1116       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1117       "  store i32 %i, i32* %arrayidx, align 4\n"
1118       "  %inc = add nsw i32 %i, 1\n"
1119       "  %cmp = icmp slt i32 %inc, %ub\n"
1120       "  br i1 %cmp, label %for.inner, label %for.inner.exit\n"
1121       "for.inner.exit:\n"
1122       "  br label %for.outer.latch\n"
1123       "for.outer.latch:\n"
1124       "  %inc.outer = add nsw i32 %j, 1\n"
1125       "  %cmp.outer = icmp slt i32 %inc.outer, %ub\n"
1126       "  br i1 %cmp.outer, label %for.outer, label %for.outer.exit\n"
1127       "for.outer.exit:\n"
1128       "  br label %for.end\n"
1129       "for.end:\n"
1130       "  ret void\n"
1131       "}\n";
1132
1133   // Parse the module.
1134   LLVMContext Context;
1135   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1136
1137   runWithLoopInfoPlus(
1138       *M, "foo",
1139       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1140         Function::iterator FI = F.begin();
1141         BasicBlock *Entry = &*(FI);
1142         BranchInst *OuterGuard = dyn_cast<BranchInst>(Entry->getTerminator());
1143         // First two basic block are entry and for.outer.preheader - skip them.
1144         ++FI;
1145         BasicBlock *Header = &*(++FI);
1146         assert(Header->getName() == "for.outer");
1147         BranchInst *InnerGuard = dyn_cast<BranchInst>(Header->getTerminator());
1148         Loop *L = LI.getLoopFor(Header);
1149         EXPECT_NE(L, nullptr);
1150
1151         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1152         EXPECT_NE(Bounds, None);
1153         ConstantInt *InitialIVValue =
1154             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1155         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1156         EXPECT_EQ(Bounds->getStepInst().getName(), "inc.outer");
1157         ConstantInt *StepValue =
1158             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1159         EXPECT_TRUE(StepValue && StepValue->isOne());
1160         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1161         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1162         EXPECT_EQ(Bounds->getDirection(),
1163                   Loop::LoopBounds::Direction::Increasing);
1164         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "j");
1165         EXPECT_EQ(L->getLoopGuardBranch(), OuterGuard);
1166         EXPECT_TRUE(L->isGuarded());
1167
1168         // Next two basic blocks are for.outer and for.inner.preheader - skip
1169         // them.
1170         ++FI;
1171         Header = &*(++FI);
1172         assert(Header->getName() == "for.inner");
1173         L = LI.getLoopFor(Header);
1174         EXPECT_NE(L, nullptr);
1175
1176         Optional<Loop::LoopBounds> InnerBounds = L->getBounds(SE);
1177         EXPECT_NE(InnerBounds, None);
1178         InitialIVValue =
1179             dyn_cast<ConstantInt>(&InnerBounds->getInitialIVValue());
1180         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1181         EXPECT_EQ(InnerBounds->getStepInst().getName(), "inc");
1182         StepValue = dyn_cast_or_null<ConstantInt>(InnerBounds->getStepValue());
1183         EXPECT_TRUE(StepValue && StepValue->isOne());
1184         EXPECT_EQ(InnerBounds->getFinalIVValue().getName(), "ub");
1185         EXPECT_EQ(InnerBounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1186         EXPECT_EQ(InnerBounds->getDirection(),
1187                   Loop::LoopBounds::Direction::Increasing);
1188         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1189         EXPECT_EQ(L->getLoopGuardBranch(), InnerGuard);
1190         EXPECT_TRUE(L->isGuarded());
1191       });
1192 }
1193
1194 TEST(LoopInfoTest, AuxiliaryIV) {
1195   const char *ModuleStr =
1196       "define void @foo(i32* %A, i32 %ub) {\n"
1197       "entry:\n"
1198       "  %guardcmp = icmp slt i32 0, %ub\n"
1199       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
1200       "for.preheader:\n"
1201       "  br label %for.body\n"
1202       "for.body:\n"
1203       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1204       "  %aux = phi i32 [ 0, %for.preheader ], [ %auxinc, %for.body ]\n"
1205       "  %loopvariant = phi i32 [ 0, %for.preheader ], [ %loopvariantinc, %for.body ]\n"
1206       "  %usedoutside = phi i32 [ 0, %for.preheader ], [ %usedoutsideinc, %for.body ]\n"
1207       "  %mulopcode = phi i32 [ 0, %for.preheader ], [ %mulopcodeinc, %for.body ]\n"
1208       "  %idxprom = sext i32 %i to i64\n"
1209       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1210       "  store i32 %i, i32* %arrayidx, align 4\n"
1211       "  %mulopcodeinc = mul nsw i32 %mulopcode, 5\n"
1212       "  %usedoutsideinc = add nsw i32 %usedoutside, 5\n"
1213       "  %loopvariantinc = add nsw i32 %loopvariant, %i\n"
1214       "  %auxinc = add nsw i32 %aux, 5\n"
1215       "  %inc = add nsw i32 %i, 1\n"
1216       "  %cmp = icmp slt i32 %inc, %ub\n"
1217       "  br i1 %cmp, label %for.body, label %for.exit\n"
1218       "for.exit:\n"
1219       "  %lcssa = phi i32 [ %usedoutside, %for.body ]\n"
1220       "  br label %for.end\n"
1221       "for.end:\n"
1222       "  ret void\n"
1223       "}\n";
1224
1225   // Parse the module.
1226   LLVMContext Context;
1227   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1228
1229   runWithLoopInfoPlus(
1230       *M, "foo",
1231       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1232         Function::iterator FI = F.begin();
1233         BasicBlock *Entry = &*(FI);
1234         BranchInst *Guard = dyn_cast<BranchInst>(Entry->getTerminator());
1235         // First two basic block are entry and for.preheader - skip them.
1236         ++FI;
1237         BasicBlock *Header = &*(++FI);
1238         assert(Header->getName() == "for.body");
1239         Loop *L = LI.getLoopFor(Header);
1240         EXPECT_NE(L, nullptr);
1241
1242         Optional<Loop::LoopBounds> Bounds = L->getBounds(SE);
1243         EXPECT_NE(Bounds, None);
1244         ConstantInt *InitialIVValue =
1245             dyn_cast<ConstantInt>(&Bounds->getInitialIVValue());
1246         EXPECT_TRUE(InitialIVValue && InitialIVValue->isZero());
1247         EXPECT_EQ(Bounds->getStepInst().getName(), "inc");
1248         ConstantInt *StepValue =
1249             dyn_cast_or_null<ConstantInt>(Bounds->getStepValue());
1250         EXPECT_TRUE(StepValue && StepValue->isOne());
1251         EXPECT_EQ(Bounds->getFinalIVValue().getName(), "ub");
1252         EXPECT_EQ(Bounds->getCanonicalPredicate(), ICmpInst::ICMP_SLT);
1253         EXPECT_EQ(Bounds->getDirection(),
1254                   Loop::LoopBounds::Direction::Increasing);
1255         EXPECT_EQ(L->getInductionVariable(SE)->getName(), "i");
1256         BasicBlock::iterator II = Header->begin();
1257         PHINode &Instruction_i = cast<PHINode>(*(II));
1258         EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_i, SE));
1259         PHINode &Instruction_aux = cast<PHINode>(*(++II));
1260         EXPECT_TRUE(L->isAuxiliaryInductionVariable(Instruction_aux, SE));
1261         PHINode &Instruction_loopvariant = cast<PHINode>(*(++II));
1262         EXPECT_FALSE(
1263             L->isAuxiliaryInductionVariable(Instruction_loopvariant, SE));
1264         PHINode &Instruction_usedoutside = cast<PHINode>(*(++II));
1265         EXPECT_FALSE(
1266             L->isAuxiliaryInductionVariable(Instruction_usedoutside, SE));
1267         PHINode &Instruction_mulopcode = cast<PHINode>(*(++II));
1268         EXPECT_FALSE(
1269             L->isAuxiliaryInductionVariable(Instruction_mulopcode, SE));
1270         EXPECT_EQ(L->getLoopGuardBranch(), Guard);
1271         EXPECT_TRUE(L->isGuarded());
1272       });
1273 }
1274
1275 TEST(LoopInfoTest, LoopNotInSimplifyForm) {
1276   const char *ModuleStr =
1277       "define void @foo(i32 %n) {\n"
1278       "entry:\n"
1279       "  %guard.cmp = icmp sgt i32 %n, 0\n"
1280       "  br i1 %guard.cmp, label %for.cond, label %for.end\n"
1281       "for.cond:\n"
1282       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n"
1283       "  %inc = add nsw i32 %i.0, 1\n"
1284       "  %cmp = icmp slt i32 %i.0, %n\n"
1285       "  br i1 %cmp, label %latch.1, label %for.end\n"
1286       "latch.1:\n"
1287       "  br i1 undef, label %for.cond, label %latch.2\n"
1288       "latch.2:\n"
1289       "  br label %for.cond\n"
1290       "for.end:\n"
1291       "  ret void\n"
1292       "}\n";
1293
1294   // Parse the module.
1295   LLVMContext Context;
1296   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1297
1298   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1299     Function::iterator FI = F.begin();
1300     // First basic block is entry - skip it.
1301     BasicBlock *Header = &*(++FI);
1302     assert(Header && "No header");
1303     Loop *L = LI.getLoopFor(Header);
1304     EXPECT_NE(L, nullptr);
1305     EXPECT_FALSE(L->isLoopSimplifyForm());
1306     // No loop guard because loop in not in simplify form.
1307     EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1308     EXPECT_FALSE(L->isGuarded());
1309   });
1310 }
1311
1312 TEST(LoopInfoTest, LoopLatchNotExiting) {
1313   const char *ModuleStr =
1314       "define void @foo(i32* %A, i32 %ub) {\n"
1315       "entry:\n"
1316       "  %guardcmp = icmp slt i32 0, %ub\n"
1317       "  br i1 %guardcmp, label %for.preheader, label %for.end\n"
1318       "for.preheader:\n"
1319       "  br label %for.body\n"
1320       "for.body:\n"
1321       "  %i = phi i32 [ 0, %for.preheader ], [ %inc, %for.body ]\n"
1322       "  %idxprom = sext i32 %i to i64\n"
1323       "  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom\n"
1324       "  store i32 %i, i32* %arrayidx, align 4\n"
1325       "  %inc = add nsw i32 %i, 1\n"
1326       "  %cmp = icmp slt i32 %inc, %ub\n"
1327       "  br i1 %cmp, label %for.latch, label %for.exit\n"
1328       "for.latch:\n"
1329       "  br label %for.body\n"
1330       "for.exit:\n"
1331       "  br label %for.end\n"
1332       "for.end:\n"
1333       "  ret void\n"
1334       "}\n";
1335
1336   // Parse the module.
1337   LLVMContext Context;
1338   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1339
1340   runWithLoopInfoPlus(
1341       *M, "foo",
1342       [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1343         Function::iterator FI = F.begin();
1344         // First two basic block are entry and for.preheader - skip them.
1345         ++FI;
1346         BasicBlock *Header = &*(++FI);
1347         BasicBlock *Latch = &*(++FI);
1348         assert(Header && "No header");
1349         Loop *L = LI.getLoopFor(Header);
1350         EXPECT_NE(L, nullptr);
1351         EXPECT_TRUE(L->isLoopSimplifyForm());
1352         EXPECT_EQ(L->getLoopLatch(), Latch);
1353         EXPECT_FALSE(L->isLoopExiting(Latch));
1354         // No loop guard becuase loop is not exiting on latch.
1355         EXPECT_EQ(L->getLoopGuardBranch(), nullptr);
1356         EXPECT_FALSE(L->isGuarded());
1357       });
1358 }
1359
1360 // Examine getUniqueExitBlocks/getUniqueNonLatchExitBlocks functions.
1361 TEST(LoopInfoTest, LoopUniqueExitBlocks) {
1362   const char *ModuleStr =
1363       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1364       "define void @foo(i32 %n, i1 %cond) {\n"
1365       "entry:\n"
1366       "  br label %for.cond\n"
1367       "for.cond:\n"
1368       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1369       "  %cmp = icmp slt i32 %i.0, %n\n"
1370       "  br i1 %cond, label %for.inc, label %for.end1\n"
1371       "for.inc:\n"
1372       "  %inc = add nsw i32 %i.0, 1\n"
1373       "  br i1 %cmp, label %for.cond, label %for.end2, !llvm.loop !0\n"
1374       "for.end1:\n"
1375       "  br label %for.end\n"
1376       "for.end2:\n"
1377       "  br label %for.end\n"
1378       "for.end:\n"
1379       "  ret void\n"
1380       "}\n"
1381       "!0 = distinct !{!0, !1}\n"
1382       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1383
1384   // Parse the module.
1385   LLVMContext Context;
1386   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1387
1388   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1389     Function::iterator FI = F.begin();
1390     // First basic block is entry - skip it.
1391     BasicBlock *Header = &*(++FI);
1392     assert(Header->getName() == "for.cond");
1393     Loop *L = LI.getLoopFor(Header);
1394
1395     SmallVector<BasicBlock *, 2> Exits;
1396     // This loop has 2 unique exits.
1397     L->getUniqueExitBlocks(Exits);
1398     EXPECT_TRUE(Exits.size() == 2);
1399     // And one unique non latch exit.
1400     Exits.clear();
1401     L->getUniqueNonLatchExitBlocks(Exits);
1402     EXPECT_TRUE(Exits.size() == 1);
1403   });
1404 }
1405
1406 // Regression test for  getUniqueNonLatchExitBlocks functions.
1407 // It should detect the exit if it comes from both latch and non-latch blocks.
1408 TEST(LoopInfoTest, LoopNonLatchUniqueExitBlocks) {
1409   const char *ModuleStr =
1410       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
1411       "define void @foo(i32 %n, i1 %cond) {\n"
1412       "entry:\n"
1413       "  br label %for.cond\n"
1414       "for.cond:\n"
1415       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
1416       "  %cmp = icmp slt i32 %i.0, %n\n"
1417       "  br i1 %cond, label %for.inc, label %for.end\n"
1418       "for.inc:\n"
1419       "  %inc = add nsw i32 %i.0, 1\n"
1420       "  br i1 %cmp, label %for.cond, label %for.end, !llvm.loop !0\n"
1421       "for.end:\n"
1422       "  ret void\n"
1423       "}\n"
1424       "!0 = distinct !{!0, !1}\n"
1425       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
1426
1427   // Parse the module.
1428   LLVMContext Context;
1429   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
1430
1431   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
1432     Function::iterator FI = F.begin();
1433     // First basic block is entry - skip it.
1434     BasicBlock *Header = &*(++FI);
1435     assert(Header->getName() == "for.cond");
1436     Loop *L = LI.getLoopFor(Header);
1437
1438     SmallVector<BasicBlock *, 2> Exits;
1439     // This loop has 1 unique exit.
1440     L->getUniqueExitBlocks(Exits);
1441     EXPECT_TRUE(Exits.size() == 1);
1442     // And one unique non latch exit.
1443     Exits.clear();
1444     L->getUniqueNonLatchExitBlocks(Exits);
1445     EXPECT_TRUE(Exits.size() == 1);
1446   });
1447 }