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/AsmParser/Parser.h"
  11 #include "llvm/IR/Dominators.h"
  12 #include "llvm/Support/SourceMgr.h"
  13 #include "gtest/gtest.h"
  14
  15 using namespace llvm;
  16
  17 /// Build the loop info for the function and run the Test.
  18 static void
  19 runWithLoopInfo(Module &M, StringRef FuncName,
  20                 function_ref<void(Function &F, LoopInfo &LI)> Test) {
  21   auto *F = M.getFunction(FuncName);
  22   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
  23   // Compute the dominator tree and the loop info for the function.
  24   DominatorTree DT(*F);
  25   LoopInfo LI(DT);
  26   Test(*F, LI);
  27 }
  28
  29 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
  30                                               const char *ModuleStr) {
  31   SMDiagnostic Err;
  32   return parseAssemblyString(ModuleStr, Err, Context);
  33 }
  34
  35 // This tests that for a loop with a single latch, we get the loop id from
  36 // its only latch, even in case the loop may not be in a simplified form.
  37 TEST(LoopInfoTest, LoopWithSingleLatch) {
  38   const char *ModuleStr =
  39       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
  40       "define void @foo(i32 %n) {\n"
  41       "entry:\n"
  42       "  br i1 undef, label %for.cond, label %for.end\n"
  43       "for.cond:\n"
  44       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]\n"
  45       "  %cmp = icmp slt i32 %i.0, %n\n"
  46       "  br i1 %cmp, label %for.inc, label %for.end\n"
  47       "for.inc:\n"
  48       "  %inc = add nsw i32 %i.0, 1\n"
  49       "  br label %for.cond, !llvm.loop !0\n"
  50       "for.end:\n"
  51       "  ret void\n"
  52       "}\n"
  53       "!0 = distinct !{!0, !1}\n"
  54       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
  55
  56   // Parse the module.
  57   LLVMContext Context;
  58   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
  59
  60   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
  61     Function::iterator FI = F.begin();
  62     // First basic block is entry - skip it.
  63     BasicBlock *Header = &*(++FI);
  64     assert(Header->getName() == "for.cond");
  65     Loop *L = LI.getLoopFor(Header);
  66
  67     // This loop is not in simplified form.
  68     EXPECT_FALSE(L->isLoopSimplifyForm());
  69
  70     // Analyze the loop metadata id.
  71     bool loopIDFoundAndSet = false;
  72     // Try to get and set the metadata id for the loop.
  73     if (MDNode *D = L->getLoopID()) {
  74       L->setLoopID(D);
  75       loopIDFoundAndSet = true;
  76     }
  77
  78     // We must have successfully found and set the loop id in the
  79     // only latch the loop has.
  80     EXPECT_TRUE(loopIDFoundAndSet);
  81   });
  82 }
  83
  84 // Test loop id handling for a loop with multiple latches.
  85 TEST(LoopInfoTest, LoopWithMultipleLatches) {
  86   const char *ModuleStr =
  87       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
  88       "define void @foo(i32 %n) {\n"
  89       "entry:\n"
  90       "  br i1 undef, label %for.cond, label %for.end\n"
  91       "for.cond:\n"
  92       "  %i.0 = phi i32 [ 0, %entry ], [ %inc, %latch.1 ], [ %inc, %latch.2 ]\n"
  93       "  %inc = add nsw i32 %i.0, 1\n"
  94       "  %cmp = icmp slt i32 %i.0, %n\n"
  95       "  br i1 %cmp, label %latch.1, label %for.end\n"
  96       "latch.1:\n"
  97       "  br i1 undef, label %for.cond, label %latch.2, !llvm.loop !0\n"
  98       "latch.2:\n"
  99       "  br label %for.cond, !llvm.loop !0\n"
 100       "for.end:\n"
 101       "  ret void\n"
 102       "}\n"
 103       "!0 = distinct !{!0, !1}\n"
 104       "!1 = !{!\"llvm.loop.distribute.enable\", i1 true}\n";
 105
 106   // Parse the module.
 107   LLVMContext Context;
 108   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 109
 110   runWithLoopInfo(*M, "foo", [&](Function &F, LoopInfo &LI) {
 111     Function::iterator FI = F.begin();
 112     // First basic block is entry - skip it.
 113     BasicBlock *Header = &*(++FI);
 114     assert(Header->getName() == "for.cond");
 115     Loop *L = LI.getLoopFor(Header);
 116     EXPECT_NE(L, nullptr);
 117
 118     // This loop is not in simplified form.
 119     EXPECT_FALSE(L->isLoopSimplifyForm());
 120
 121     // Try to get and set the metadata id for the loop.
 122     MDNode *OldLoopID = L->getLoopID();
 123     EXPECT_NE(OldLoopID, nullptr);
 124
 125     MDNode *NewLoopID = MDNode::get(Context, {nullptr});
 126     // Set operand 0 to refer to the loop id itself.
 127     NewLoopID->replaceOperandWith(0, NewLoopID);
 128
 129     L->setLoopID(NewLoopID);
 130     EXPECT_EQ(L->getLoopID(), NewLoopID);
 131     EXPECT_NE(L->getLoopID(), OldLoopID);
 132
 133     L->setLoopID(OldLoopID);
 134     EXPECT_EQ(L->getLoopID(), OldLoopID);
 135     EXPECT_NE(L->getLoopID(), NewLoopID);
 136   });
 137 }
 138
 139 TEST(LoopInfoTest, PreorderTraversals) {
 140   const char *ModuleStr = "define void @f() {\n"
 141                           "entry:\n"
 142                           "  br label %loop.0\n"
 143                           "loop.0:\n"
 144                           "  br i1 undef, label %loop.0.0, label %loop.1\n"
 145                           "loop.0.0:\n"
 146                           "  br i1 undef, label %loop.0.0, label %loop.0.1\n"
 147                           "loop.0.1:\n"
 148                           "  br i1 undef, label %loop.0.1, label %loop.0.2\n"
 149                           "loop.0.2:\n"
 150                           "  br i1 undef, label %loop.0.2, label %loop.0\n"
 151                           "loop.1:\n"
 152                           "  br i1 undef, label %loop.1.0, label %end\n"
 153                           "loop.1.0:\n"
 154                           "  br i1 undef, label %loop.1.0, label %loop.1.1\n"
 155                           "loop.1.1:\n"
 156                           "  br i1 undef, label %loop.1.1, label %loop.1.2\n"
 157                           "loop.1.2:\n"
 158                           "  br i1 undef, label %loop.1.2, label %loop.1\n"
 159                           "end:\n"
 160                           "  ret void\n"
 161                           "}\n";
 162   // Parse the module.
 163   LLVMContext Context;
 164   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 165   Function &F = *M->begin();
 166
 167   DominatorTree DT(F);
 168   LoopInfo LI;
 169   LI.analyze(DT);
 170
 171   Function::iterator I = F.begin();
 172   ASSERT_EQ("entry", I->getName());
 173   ++I;
 174   Loop &L_0 = *LI.getLoopFor(&*I++);
 175   ASSERT_EQ("loop.0", L_0.getHeader()->getName());
 176   Loop &L_0_0 = *LI.getLoopFor(&*I++);
 177   ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName());
 178   Loop &L_0_1 = *LI.getLoopFor(&*I++);
 179   ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName());
 180   Loop &L_0_2 = *LI.getLoopFor(&*I++);
 181   ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName());
 182   Loop &L_1 = *LI.getLoopFor(&*I++);
 183   ASSERT_EQ("loop.1", L_1.getHeader()->getName());
 184   Loop &L_1_0 = *LI.getLoopFor(&*I++);
 185   ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName());
 186   Loop &L_1_1 = *LI.getLoopFor(&*I++);
 187   ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName());
 188   Loop &L_1_2 = *LI.getLoopFor(&*I++);
 189   ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName());
 190
 191   auto Preorder = LI.getLoopsInPreorder();
 192   ASSERT_EQ(8u, Preorder.size());
 193   EXPECT_EQ(&L_0, Preorder[0]);
 194   EXPECT_EQ(&L_0_0, Preorder[1]);
 195   EXPECT_EQ(&L_0_1, Preorder[2]);
 196   EXPECT_EQ(&L_0_2, Preorder[3]);
 197   EXPECT_EQ(&L_1, Preorder[4]);
 198   EXPECT_EQ(&L_1_0, Preorder[5]);
 199   EXPECT_EQ(&L_1_1, Preorder[6]);
 200   EXPECT_EQ(&L_1_2, Preorder[7]);
 201
 202   auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder();
 203   ASSERT_EQ(8u, ReverseSiblingPreorder.size());
 204   EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]);
 205   EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]);
 206   EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]);
 207   EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]);
 208   EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]);
 209   EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]);
 210   EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]);
 211   EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]);
 212 }