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