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/Support/SourceMgr.h"
16 #include "gtest/gtest.h"
17 
18 using namespace llvm;
19 
20 /// Build the loop nest analysis for a loop nest and run the given test \p Test.
21 static void runTest(
22     Module &M, StringRef FuncName,
23     function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
24   auto *F = M.getFunction(FuncName);
25   ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
26 
27   TargetLibraryInfoImpl TLII;
28   TargetLibraryInfo TLI(TLII);
29   AssumptionCache AC(*F);
30   DominatorTree DT(*F);
31   LoopInfo LI(DT);
32   ScalarEvolution SE(*F, TLI, AC, DT, LI);
33 
34   Test(*F, LI, SE);
35 }
36 
37 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
38                                               const char *ModuleStr) {
39   SMDiagnostic Err;
40   return parseAssemblyString(ModuleStr, Err, Context);
41 }
42 
43 TEST(LoopNestTest, PerfectLoopNest) {
44   const char *ModuleStr =
45     "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
46     "define void @foo(i64 signext %nx, i64 signext %ny) {\n"
47     "entry:\n"
48     "  br label %for.outer\n"
49     "for.outer:\n"
50     "  %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n"
51     "  %cmp21 = icmp slt i64 0, %ny\n"
52     "  br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n"
53     "for.inner.preheader:\n"
54     "  br label %for.inner\n"
55     "for.inner:\n"
56     "  %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n"
57     "  br label %for.inner.latch\n"
58     "for.inner.latch:\n"
59     "  %inc = add nsw i64 %j, 1\n"
60     "  %cmp2 = icmp slt i64 %inc, %ny\n"
61     "  br i1 %cmp2, label %for.inner, label %for.inner.exit\n"
62     "for.inner.exit:\n"
63     "  br label %for.outer.latch\n"
64     "for.outer.latch:\n"
65     "  %inc13 = add nsw i64 %i, 1\n"
66     "  %cmp = icmp slt i64 %inc13, %nx\n"
67     "  br i1 %cmp, label %for.outer, label %for.outer.exit\n"
68     "for.outer.exit:\n"
69     "  br label %for.end\n"
70     "for.end:\n"
71     "  ret void\n"
72     "}\n";
73 
74   LLVMContext Context;
75   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
76 
77   runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
78     Function::iterator FI = F.begin();
79     // Skip the first basic block (entry), get to the outer loop header.
80     BasicBlock *Header = &*(++FI);
81     assert(Header->getName() == "for.outer");
82     Loop *L = LI.getLoopFor(Header);
83     EXPECT_NE(L, nullptr);
84 
85     LoopNest LN(*L, SE);
86     EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
87 
88     // Ensure that we can identify the outermost loop in the nest.
89     const Loop &OL = LN.getOutermostLoop();
90     EXPECT_EQ(OL.getName(), "for.outer");
91 
92     // Ensure that we can identify the innermost loop in the nest.
93     const Loop *IL = LN.getInnermostLoop();
94     EXPECT_NE(IL, nullptr);
95     EXPECT_EQ(IL->getName(), "for.inner");
96 
97     // Ensure the loop nest is recognized as having 2 loops.
98     const ArrayRef<Loop*> Loops = LN.getLoops();
99     EXPECT_EQ(Loops.size(), 2ull);
100 
101     // Ensure the loop nest is recognized as perfect in its entirety.
102     const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
103     EXPECT_EQ(PLV.size(), 1ull);
104     EXPECT_EQ(PLV.front().size(), 2ull);
105 
106     // Ensure the nest depth and perfect nest depth are computed correctly.
107     EXPECT_EQ(LN.getNestDepth(), 2u);
108     EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
109   });
110 }
111 
112 TEST(LoopNestTest, ImperfectLoopNest) {
113   const char *ModuleStr =
114       "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n"
115       "define void @foo(i32 signext %nx, i32 signext %ny, i32 signext %nk) {\n"
116       "entry:\n"
117       "  br label %loop.i\n"
118       "loop.i:\n"
119       "  %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]\n"
120       "  %cmp21 = icmp slt i32 0, %ny\n"
121       "  br i1 %cmp21, label %loop.j.preheader, label %for.inci\n"
122       "loop.j.preheader:\n"
123       "  br label %loop.j\n"
124       "loop.j:\n"
125       "  %j = phi i32 [ %incj, %for.incj ], [ 0, %loop.j.preheader ]\n"
126       "  %cmp22 = icmp slt i32 0, %nk\n"
127       "  br i1 %cmp22, label %loop.k.preheader, label %for.incj\n"
128       "loop.k.preheader:\n"
129       "  call void @bar()\n"
130       "  br label %loop.k\n"
131       "loop.k:\n"
132       "  %k = phi i32 [ %inck, %for.inck ], [ 0, %loop.k.preheader ]\n"
133       "  br label %for.inck\n"
134       "for.inck:\n"
135       "  %inck = add nsw i32 %k, 1\n"
136       "  %cmp5 = icmp slt i32 %inck, %nk\n"
137       "  br i1 %cmp5, label %loop.k, label %for.incj.loopexit\n"
138       "for.incj.loopexit:\n"
139       "  br label %for.incj\n"
140       "for.incj:\n"
141       "  %incj = add nsw i32 %j, 1\n"
142       "  %cmp2 = icmp slt i32 %incj, %ny\n"
143       "  br i1 %cmp2, label %loop.j, label %for.inci.loopexit\n"
144       "for.inci.loopexit:\n"
145       "  br label %for.inci\n"
146       "for.inci:\n"
147       "  %inci = add nsw i32 %i, 1\n"
148       "  %cmp = icmp slt i32 %inci, %nx\n"
149       "  br i1 %cmp, label %loop.i, label %loop.i.end\n"
150       "loop.i.end:\n"
151       "  ret void\n"
152       "}\n"
153       "declare void @bar()\n";
154 
155   LLVMContext Context;
156   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr);
157 
158   runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
159     Function::iterator FI = F.begin();
160     // Skip the first basic block (entry), get to the outermost loop header.
161     BasicBlock *Header = &*(++FI);
162     assert(Header->getName() == "loop.i");
163     Loop *L = LI.getLoopFor(Header);
164     EXPECT_NE(L, nullptr);
165 
166     LoopNest LN(*L, SE);
167     EXPECT_TRUE(LN.areAllLoopsSimplifyForm());
168 
169     dbgs() << "LN: " << LN << "\n";
170 
171     // Ensure that we can identify the outermost loop in the nest.
172     const Loop &OL = LN.getOutermostLoop();
173     EXPECT_EQ(OL.getName(), "loop.i");
174 
175     // Ensure that we can identify the innermost loop in the nest.
176     const Loop *IL = LN.getInnermostLoop();
177     EXPECT_NE(IL, nullptr);
178     EXPECT_EQ(IL->getName(), "loop.k");
179 
180     // Ensure the loop nest is recognized as having 3 loops.
181     const ArrayRef<Loop*> Loops = LN.getLoops();
182     EXPECT_EQ(Loops.size(), 3ull);
183 
184     // Ensure the loop nest is recognized as having 2 separate perfect loops groups.
185     const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE);
186     EXPECT_EQ(PLV.size(), 2ull);
187     EXPECT_EQ(PLV.front().size(), 2ull);
188     EXPECT_EQ(PLV.back().size(), 1ull);
189 
190     // Ensure the nest depth and perfect nest depth are computed correctly.
191     EXPECT_EQ(LN.getNestDepth(), 3u);
192     EXPECT_EQ(LN.getMaxPerfectDepth(), 2u);
193   });
194 }
195 
196