unittests/Analysis/LoopInfoTest.cpp

   1 //===- LoopInfoTest.cpp - LoopInfo unit tests -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/LoopInfo.h"
  11 #include "llvm/AsmParser/Parser.h"
  12 #include "llvm/IR/Dominators.h"
  13 #include "llvm/Support/SourceMgr.h"
  14 #include "gtest/gtest.h"
  15
  16 using namespace llvm;
  17
  18 /// Build the loop info for the function and run the Test.
  19 static void
  20 runWithLoopInfo(Module &M, StringRef FuncName,
  21                 function_ref<void(Function &F, LoopInfo &LI)> Test) {
  22   auto *F = M.getFunction(FuncName);
  23   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
  24   // Compute the dominator tree and the loop info for the function.
  25   DominatorTree DT(*F);
  26   LoopInfo LI(DT);
  27   Test(*F, LI);
  28 }
  29
  30 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
  31                                               const char *ModuleStr) {
  32   SMDiagnostic Err;
  33   return parseAssemblyString(ModuleStr, Err, Context);
  34 }
  35
  36 // This tests that for a loop with a single latch, we get the loop id from
  37 // its only latch, even in case the loop may not be in a simplified form.
  38 TEST(LoopInfoTest, LoopWithSingleLatch) {
  39   const char *ModuleStr =
  40       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
  41       "define void @foo(i32 %n) {\n"
  42       "entry:\n"
  43       "  br i1 undef, label %for.cond, label %for.end\n"
  44       "for.cond:\n"
  45       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
  46       "  %cmp = icmp slt i32 %i.0, %n\n"
  47       "  br i1 %cmp, label %for.inc, label %for.end\n"
  48       "for.inc:\n"
  49       "  %inc = add nsw i32 %i.0, 1\n"
  50       "  br label %for.cond, !llvm.loop !0\n"
  51       "for.end:\n"
  52       "  ret void\n"
  53       "}\n"
  54       "!0 = distinct !{!0, !1}\n"
  55       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
  56
  57   // Parse the module.
  58   LLVMContext Context;
  59   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
  60
  61   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
  62     Function::iterator FI = F.begin();
  63     // First basic block is entry - skip it.
  64     BasicBlock *Header = &*(++FI);
  65     assert(Header->getName() == "for.cond");
  66     Loop *L = LI.getLoopFor(Header);
  67
  68     // This loop is not in simplified form.
  69     EXPECT_FALSE(L->isLoopSimplifyForm());
  70
  71     // Analyze the loop metadata id.
  72     bool loopIDFoundAndSet = false;
  73     // Try to get and set the metadata id for the loop.
  74     if (MDNode *D = L->getLoopID()) {
  75       L->setLoopID(D);
  76       loopIDFoundAndSet = true;
  77     }
  78
  79     // We must have successfully found and set the loop id in the
  80     // only latch the loop has.
  81     EXPECT_TRUE(loopIDFoundAndSet);
  82   });
  83 }
  84
  85 TEST(LoopInfoTest, PreorderTraversals) {
  86   const char *ModuleStr = "define void @f() {\n"
  87                           "entry:\n"
  88                           "  br label %loop.0\n"
  89                           "loop.0:\n"
  90                           "  br i1 undef, label %loop.0.0, label %loop.1\n"
  91                           "loop.0.0:\n"
  92                           "  br i1 undef, label %loop.0.0, label %loop.0.1\n"
  93                           "loop.0.1:\n"
  94                           "  br i1 undef, label %loop.0.1, label %loop.0.2\n"
  95                           "loop.0.2:\n"
  96                           "  br i1 undef, label %loop.0.2, label %loop.0\n"
  97                           "loop.1:\n"
  98                           "  br i1 undef, label %loop.1.0, label %end\n"
  99                           "loop.1.0:\n"
 100                           "  br i1 undef, label %loop.1.0, label %loop.1.1\n"
 101                           "loop.1.1:\n"
 102                           "  br i1 undef, label %loop.1.1, label %loop.1.2\n"
 103                           "loop.1.2:\n"
 104                           "  br i1 undef, label %loop.1.2, label %loop.1\n"
 105                           "end:\n"
 106                           "  ret void\n"
 107                           "}\n";
 108   // Parse the module.
 109   LLVMContext Context;
 110   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 111   Function &F = *M->begin();
 112
 113   DominatorTree DT(F);
 114   LoopInfo LI;
 115   LI.analyze(DT);
 116
 117   Function::iterator I = F.begin();
 118   ASSERT_EQ("entry", I->getName());
 119   ++I;
 120   Loop &L_0 = *LI.getLoopFor(&*I++);
 121   ASSERT_EQ("loop.0", L_0.getHeader()->getName());
 122   Loop &L_0_0 = *LI.getLoopFor(&*I++);
 123   ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName());
 124   Loop &L_0_1 = *LI.getLoopFor(&*I++);
 125   ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName());
 126   Loop &L_0_2 = *LI.getLoopFor(&*I++);
 127   ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName());
 128   Loop &L_1 = *LI.getLoopFor(&*I++);
 129   ASSERT_EQ("loop.1", L_1.getHeader()->getName());
 130   Loop &L_1_0 = *LI.getLoopFor(&*I++);
 131   ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName());
 132   Loop &L_1_1 = *LI.getLoopFor(&*I++);
 133   ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName());
 134   Loop &L_1_2 = *LI.getLoopFor(&*I++);
 135   ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName());
 136
 137   auto Preorder = LI.getLoopsInPreorder();
 138   ASSERT_EQ(8u, Preorder.size());
 139   EXPECT_EQ(&L_0, Preorder[0]);
 140   EXPECT_EQ(&L_0_0, Preorder[1]);
 141   EXPECT_EQ(&L_0_1, Preorder[2]);
 142   EXPECT_EQ(&L_0_2, Preorder[3]);
 143   EXPECT_EQ(&L_1, Preorder[4]);
 144   EXPECT_EQ(&L_1_0, Preorder[5]);
 145   EXPECT_EQ(&L_1_1, Preorder[6]);
 146   EXPECT_EQ(&L_1_2, Preorder[7]);
 147
 148   auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder();
 149   ASSERT_EQ(8u, ReverseSiblingPreorder.size());
 150   EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]);
 151   EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]);
 152   EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]);
 153   EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]);
 154   EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]);
 155   EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]);
 156   EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]);
 157   EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]);
 158 }