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 } 320