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