llvm/unittests/Analysis/LoopNestTest.cpp

   1 //===- LoopNestTest.cpp - LoopNestAnalysis 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/AssumptionCache.h"
  10 #include "llvm/Analysis/LoopNestAnalysis.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/IR/Module.h"
  16 #include "llvm/Support/SourceMgr.h"
  17 #include "gtest/gtest.h"
  18
  19 using namespace llvm;
  20
  21 /// Build the loop nest analysis for a loop nest and run the given test \p Test.
  22 static void runTest(
  23     Module &M, StringRef FuncName,
  24     function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
  25   auto *F = M.getFunction(FuncName);
  26   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
  27
  28   TargetLibraryInfoImpl TLII;
  29   TargetLibraryInfo TLI(TLII);
  30   AssumptionCache AC(*F);
  31   DominatorTree DT(*F);
  32   LoopInfo LI(DT);
  33   ScalarEvolution SE(*F, TLI, AC, DT, LI);
  34
  35   Test(*F, LI, SE);
  36 }
  37
  38 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
  39                                               const char *ModuleStr) {
  40   SMDiagnostic Err;
  41   return parseAssemblyString(ModuleStr, Err, Context);
  42 }
  43
  44 static Instruction *getInstructionByName(Function &F, StringRef Name) {
  45   for (BasicBlock &BB : F)
  46     for (Instruction &I : BB)
  47       if (I.getName() == Name)
  48         return &I;
  49   llvm_unreachable("Expected to find instruction!");
  50 }
  51
  52 TEST(LoopNestTest, PerfectLoopNest) {
  53   const char *ModuleStr =
  54     "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
  55     "define void @foo(i64 signext %nx, i64 signext %ny) {\n"
  56     "entry:\n"
  57     "  br label %for.outer\n"
  58     "for.outer:\n"
  59     "  %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n"
  60     "  %cmp21 = icmp slt i64 0, %ny\n"
  61     "  br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n"
  62     "for.inner.preheader:\n"
  63     "  br label %for.inner\n"
  64     "for.inner:\n"
  65     "  %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n"
  66     "  br label %for.inner.latch\n"
  67     "for.inner.latch:\n"
  68     "  %inc = add nsw i64 %j, 1\n"
  69     "  %cmp2 = icmp slt i64 %inc, %ny\n"
  70     "  br i1 %cmp2, label %for.inner, label %for.inner.exit\n"
  71     "for.inner.exit:\n"
  72     "  br label %for.outer.latch\n"
  73     "for.outer.latch:\n"
  74     "  %inc13 = add nsw i64 %i, 1\n"
  75     "  %cmp = icmp slt i64 %inc13, %nx\n"
  76     "  br i1 %cmp, label %for.outer, label %for.outer.exit\n"
  77     "for.outer.exit:\n"
  78     "  br label %for.end\n"
  79     "for.end:\n"
  80     "  ret void\n"
  81     "}\n";
  82
  83   LLVMContext Context;
  84   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
  85
  86   runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
  87     Function::iterator FI = F.begin();
  88     // Skip the first basic block (entry), get to the outer loop header.
  89     BasicBlock *Header = &*(++FI);
  90     assert(Header->getName() == "for.outer");
  91     Loop *L = LI.getLoopFor(Header);
  92     EXPECT_NE(L, nullptr);
  93
  94     LoopNest LN(*L, SE);
  95     EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
  96
  97     // Ensure that we can identify the outermost loop in the nest.
  98     const Loop &OL = LN.getOutermostLoop();
  99     EXPECT_EQ(OL.getName(), "for.outer");
 100
 101     // Ensure that we can identify the innermost loop in the nest.
 102     const Loop *IL = LN.getInnermostLoop();
 103     EXPECT_NE(IL, nullptr);
 104     EXPECT_EQ(IL->getName(), "for.inner");
 105
 106     // Ensure the loop nest is recognized as having 2 loops.
 107     const ArrayRef<Loop*> Loops = LN.getLoops();
 108     EXPECT_EQ(Loops.size(), 2ull);
 109
 110     // Ensure that we can obtain loops by depth.
 111     LoopVectorTy LoopsAtDepth1 = LN.getLoopsAtDepth(1);
 112     EXPECT_EQ(LoopsAtDepth1.size(), 1u);
 113     EXPECT_EQ(LoopsAtDepth1[0], &OL);
 114     LoopVectorTy LoopsAtDepth2 = LN.getLoopsAtDepth(2);
 115     EXPECT_EQ(LoopsAtDepth2.size(), 1u);
 116     EXPECT_EQ(LoopsAtDepth2[0], IL);
 117
 118     // Ensure that we can obtain the loop index of a given loop, and get back
 119     // the loop with that index.
 120     EXPECT_EQ(LN.getLoop(LN.getLoopIndex(OL)), &OL);
 121     EXPECT_EQ(LN.getLoop(LN.getLoopIndex(*IL)), IL);
 122
 123     // Ensure the loop nest is recognized as perfect in its entirety.
 124     const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
 125     EXPECT_EQ(PLV.size(), 1ull);
 126     EXPECT_EQ(PLV.front().size(), 2ull);
 127
 128     // Ensure the nest depth and perfect nest depth are computed correctly.
 129     EXPECT_EQ(LN.getNestDepth(), 2u);
 130     EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
 131
 132     EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty());
 133   });
 134 }
 135
 136 TEST(LoopNestTest, ImperfectLoopNest) {
 137   const char *ModuleStr =
 138       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
 139       "define void @foo(i32 signext %nx, i32 signext %ny, i32 signext %nk) {\n"
 140       "entry:\n"
 141       "  br label %loop.i\n"
 142       "loop.i:\n"
 143       "  %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]\n"
 144       "  %cmp21 = icmp slt i32 0, %ny\n"
 145       "  br i1 %cmp21, label %loop.j.preheader, label %for.inci\n"
 146       "loop.j.preheader:\n"
 147       "  br label %loop.j\n"
 148       "loop.j:\n"
 149       "  %j = phi i32 [ %incj, %for.incj ], [ 0, %loop.j.preheader ]\n"
 150       "  %cmp22 = icmp slt i32 0, %nk\n"
 151       "  br i1 %cmp22, label %loop.k.preheader, label %for.incj\n"
 152       "loop.k.preheader:\n"
 153       "  call void @bar()\n"
 154       "  br label %loop.k\n"
 155       "loop.k:\n"
 156       "  %k = phi i32 [ %inck, %for.inck ], [ 0, %loop.k.preheader ]\n"
 157       "  br label %for.inck\n"
 158       "for.inck:\n"
 159       "  %inck = add nsw i32 %k, 1\n"
 160       "  %cmp5 = icmp slt i32 %inck, %nk\n"
 161       "  br i1 %cmp5, label %loop.k, label %for.incj.loopexit\n"
 162       "for.incj.loopexit:\n"
 163       "  br label %for.incj\n"
 164       "for.incj:\n"
 165       "  %incj = add nsw i32 %j, 1\n"
 166       "  %cmp2 = icmp slt i32 %incj, %ny\n"
 167       "  br i1 %cmp2, label %loop.j, label %for.inci.loopexit\n"
 168       "for.inci.loopexit:\n"
 169       "  br label %for.inci\n"
 170       "for.inci:\n"
 171       "  %inci = add nsw i32 %i, 1\n"
 172       "  %cmp = icmp slt i32 %inci, %nx\n"
 173       "  br i1 %cmp, label %loop.i, label %loop.i.end\n"
 174       "loop.i.end:\n"
 175       "  ret void\n"
 176       "}\n"
 177       "declare void @bar()\n";
 178
 179   LLVMContext Context;
 180   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 181
 182   runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 183     Function::iterator FI = F.begin();
 184     // Skip the first basic block (entry), get to the outermost loop header.
 185     BasicBlock *Header = &*(++FI);
 186     assert(Header->getName() == "loop.i");
 187     Loop *L = LI.getLoopFor(Header);
 188     EXPECT_NE(L, nullptr);
 189
 190     LoopNest LN(*L, SE);
 191     EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
 192
 193     dbgs() << "LN: " << LN << "\n";
 194
 195     // Ensure that we can identify the outermost loop in the nest.
 196     const Loop &OL = LN.getOutermostLoop();
 197     EXPECT_EQ(OL.getName(), "loop.i");
 198
 199     // Ensure that we can identify the innermost loop in the nest.
 200     const Loop *IL = LN.getInnermostLoop();
 201     EXPECT_NE(IL, nullptr);
 202     EXPECT_EQ(IL->getName(), "loop.k");
 203
 204     // Ensure the loop nest is recognized as having 3 loops.
 205     const ArrayRef<Loop*> Loops = LN.getLoops();
 206     EXPECT_EQ(Loops.size(), 3ull);
 207
 208     // Ensure the loop nest is recognized as having 2 separate perfect loops groups.
 209     const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
 210     EXPECT_EQ(PLV.size(), 2ull);
 211     EXPECT_EQ(PLV.front().size(), 2ull);
 212     EXPECT_EQ(PLV.back().size(), 1ull);
 213
 214     // Ensure the nest depth and perfect nest depth are computed correctly.
 215     EXPECT_EQ(LN.getNestDepth(), 3u);
 216     EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
 217
 218     EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty());
 219   });
 220 }
 221
 222 TEST(LoopNestTest, InterveningInstrLoopNest) {
 223   const char *ModuleStr =
 224       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
 225       "define void @foo(i64 signext %nx, i64 signext %ny, i32* noalias %A, i32 "
 226       "%op0, i32 %op1){\n"
 227       "entry:\n"
 228       "  br label %for.outer\n"
 229       "for.outer:\n"
 230       "  %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n"
 231       "  %cmp21 = icmp slt i64 0, %ny\n"
 232       "  call void @outerheader()\n"
 233       "  br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n"
 234       "for.inner.preheader:\n"
 235       "  %varr = getelementptr inbounds i32, i32* %A, i64 5\n"
 236       "  store i32 5, i32* %varr, align 4\n"
 237       "  call void @innerpreheader()\n"
 238       "  br label %for.inner\n"
 239       "for.inner:\n"
 240       "  %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n"
 241       "  br label %for.inner.latch\n"
 242       "for.inner.latch:\n"
 243       "  %inc = add nsw i64 %j, 1\n"
 244       "  %cmp2 = icmp slt i64 %inc, %ny\n"
 245       "  br i1 %cmp2, label %for.inner, label %for.inner.exit\n"
 246       "for.inner.exit:\n"
 247       "  %varr1 = getelementptr inbounds i32, i32* %A, i64 5\n"
 248       "  call void @innerexit()\n"
 249       "  br label %for.outer.latch\n"
 250       "for.outer.latch:\n"
 251       "  %inc13 = add nsw i64 %i, 1\n"
 252       "  call void @outerlatch()\n"
 253       "  %cmp = icmp slt i64 %inc13, %nx\n"
 254       "  br i1 %cmp, label %for.outer, label %for.outer.exit\n"
 255       "for.outer.exit:\n"
 256       "  br label %for.end\n"
 257       "for.end:\n"
 258       "  ret void\n"
 259       "}\n"
 260       "declare void @innerpreheader()\n"
 261       "declare void @outerheader()\n"
 262       "declare void @outerlatch()\n"
 263       "declare void @innerexit()\n";
 264
 265   LLVMContext Context;
 266   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
 267
 268   runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
 269     Function::iterator FI = F.begin();
 270     // Skip the first basic block (entry), get to the outer loop header.
 271     BasicBlock *Header = &*(++FI);
 272     assert(Header->getName() == "for.outer");
 273     Loop *L = LI.getLoopFor(Header);
 274     EXPECT_NE(L, nullptr);
 275
 276     LoopNest LN(*L, SE);
 277     EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
 278
 279     // Ensure that we can identify the outermost loop in the nest.
 280     const Loop &OL = LN.getOutermostLoop();
 281     EXPECT_EQ(OL.getName(), "for.outer");
 282
 283     // Ensure that we can identify the innermost loop in the nest.
 284     const Loop *IL = LN.getInnermostLoop();
 285     EXPECT_NE(IL, nullptr);
 286     EXPECT_EQ(IL->getName(), "for.inner");
 287
 288     // Ensure the loop nest is recognized as having 2 loops.
 289     const ArrayRef<Loop *> Loops = LN.getLoops();
 290     EXPECT_EQ(Loops.size(), 2ull);
 291
 292     // Ensure the loop nest is not recognized as perfect in its entirety.
 293     const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
 294     EXPECT_EQ(PLV.size(), 2ull);
 295     EXPECT_EQ(PLV.front().size(), 1ull);
 296     EXPECT_EQ(PLV.back().size(), 1ull);
 297
 298     // Ensure the nest depth and perfect nest depth are computed correctly.
 299     EXPECT_EQ(LN.getNestDepth(), 2u);
 300     EXPECT_EQ(LN.getMaxPerfectDepth(), 1u);
 301
 302     // Ensure enclosed instructions are recognized
 303     const LoopNest::InstrVectorTy InstrV =
 304         LN.getInterveningInstructions(OL, *IL, SE);
 305     EXPECT_EQ(InstrV.size(), 5u);
 306
 307     Instruction *SI = getInstructionByName(F, "varr")->getNextNode();
 308     Instruction *CI = SI->getNextNode();
 309     Instruction *OLH =
 310         getInstructionByName(F, "i")->getNextNode()->getNextNode();
 311     Instruction *OLL = getInstructionByName(F, "inc13")->getNextNode();
 312     Instruction *IE = getInstructionByName(F, "varr1")->getNextNode();
 313
 314     EXPECT_EQ(InstrV.front(), OLH);
 315     EXPECT_EQ(InstrV[1], OLL);
 316     EXPECT_EQ(InstrV[2], IE);
 317     EXPECT_EQ(InstrV[3], SI);
 318     EXPECT_EQ(InstrV.back(), CI);
 319   });
 320 }