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 the loop nest is recognized as perfect in its entirety. 110 const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE); 111 EXPECT_EQ(PLV.size(), 1ull); 112 EXPECT_EQ(PLV.front().size(), 2ull); 113 114 // Ensure the nest depth and perfect nest depth are computed correctly. 115 EXPECT_EQ(LN.getNestDepth(), 2u); 116 EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); 117 118 EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty()); 119 }); 120 } 121 122 TEST(LoopNestTest, ImperfectLoopNest) { 123 const char *ModuleStr = 124 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 125 "define void @foo(i32 signext %nx, i32 signext %ny, i32 signext %nk) {\n" 126 "entry:\n" 127 " br label %loop.i\n" 128 "loop.i:\n" 129 " %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]\n" 130 " %cmp21 = icmp slt i32 0, %ny\n" 131 " br i1 %cmp21, label %loop.j.preheader, label %for.inci\n" 132 "loop.j.preheader:\n" 133 " br label %loop.j\n" 134 "loop.j:\n" 135 " %j = phi i32 [ %incj, %for.incj ], [ 0, %loop.j.preheader ]\n" 136 " %cmp22 = icmp slt i32 0, %nk\n" 137 " br i1 %cmp22, label %loop.k.preheader, label %for.incj\n" 138 "loop.k.preheader:\n" 139 " call void @bar()\n" 140 " br label %loop.k\n" 141 "loop.k:\n" 142 " %k = phi i32 [ %inck, %for.inck ], [ 0, %loop.k.preheader ]\n" 143 " br label %for.inck\n" 144 "for.inck:\n" 145 " %inck = add nsw i32 %k, 1\n" 146 " %cmp5 = icmp slt i32 %inck, %nk\n" 147 " br i1 %cmp5, label %loop.k, label %for.incj.loopexit\n" 148 "for.incj.loopexit:\n" 149 " br label %for.incj\n" 150 "for.incj:\n" 151 " %incj = add nsw i32 %j, 1\n" 152 " %cmp2 = icmp slt i32 %incj, %ny\n" 153 " br i1 %cmp2, label %loop.j, label %for.inci.loopexit\n" 154 "for.inci.loopexit:\n" 155 " br label %for.inci\n" 156 "for.inci:\n" 157 " %inci = add nsw i32 %i, 1\n" 158 " %cmp = icmp slt i32 %inci, %nx\n" 159 " br i1 %cmp, label %loop.i, label %loop.i.end\n" 160 "loop.i.end:\n" 161 " ret void\n" 162 "}\n" 163 "declare void @bar()\n"; 164 165 LLVMContext Context; 166 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 167 168 runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 169 Function::iterator FI = F.begin(); 170 // Skip the first basic block (entry), get to the outermost loop header. 171 BasicBlock *Header = &*(++FI); 172 assert(Header->getName() == "loop.i"); 173 Loop *L = LI.getLoopFor(Header); 174 EXPECT_NE(L, nullptr); 175 176 LoopNest LN(*L, SE); 177 EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); 178 179 dbgs() << "LN: " << LN << "\n"; 180 181 // Ensure that we can identify the outermost loop in the nest. 182 const Loop &OL = LN.getOutermostLoop(); 183 EXPECT_EQ(OL.getName(), "loop.i"); 184 185 // Ensure that we can identify the innermost loop in the nest. 186 const Loop *IL = LN.getInnermostLoop(); 187 EXPECT_NE(IL, nullptr); 188 EXPECT_EQ(IL->getName(), "loop.k"); 189 190 // Ensure the loop nest is recognized as having 3 loops. 191 const ArrayRef<Loop*> Loops = LN.getLoops(); 192 EXPECT_EQ(Loops.size(), 3ull); 193 194 // Ensure the loop nest is recognized as having 2 separate perfect loops groups. 195 const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE); 196 EXPECT_EQ(PLV.size(), 2ull); 197 EXPECT_EQ(PLV.front().size(), 2ull); 198 EXPECT_EQ(PLV.back().size(), 1ull); 199 200 // Ensure the nest depth and perfect nest depth are computed correctly. 201 EXPECT_EQ(LN.getNestDepth(), 3u); 202 EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); 203 204 EXPECT_TRUE(LN.getInterveningInstructions(OL, *IL, SE).empty()); 205 }); 206 } 207 208 TEST(LoopNestTest, InterveningInstrLoopNest) { 209 const char *ModuleStr = 210 "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" 211 "define void @foo(i64 signext %nx, i64 signext %ny, i32* noalias %A, i32 " 212 "%op0, i32 %op1){\n" 213 "entry:\n" 214 " br label %for.outer\n" 215 "for.outer:\n" 216 " %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n" 217 " %cmp21 = icmp slt i64 0, %ny\n" 218 " call void @outerheader()\n" 219 " br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n" 220 "for.inner.preheader:\n" 221 " %varr = getelementptr inbounds i32, i32* %A, i64 5\n" 222 " store i32 5, i32* %varr, align 4\n" 223 " call void @innerpreheader()\n" 224 " br label %for.inner\n" 225 "for.inner:\n" 226 " %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n" 227 " br label %for.inner.latch\n" 228 "for.inner.latch:\n" 229 " %inc = add nsw i64 %j, 1\n" 230 " %cmp2 = icmp slt i64 %inc, %ny\n" 231 " br i1 %cmp2, label %for.inner, label %for.inner.exit\n" 232 "for.inner.exit:\n" 233 " %varr1 = getelementptr inbounds i32, i32* %A, i64 5\n" 234 " call void @innerexit()\n" 235 " br label %for.outer.latch\n" 236 "for.outer.latch:\n" 237 " %inc13 = add nsw i64 %i, 1\n" 238 " call void @outerlatch()\n" 239 " %cmp = icmp slt i64 %inc13, %nx\n" 240 " br i1 %cmp, label %for.outer, label %for.outer.exit\n" 241 "for.outer.exit:\n" 242 " br label %for.end\n" 243 "for.end:\n" 244 " ret void\n" 245 "}\n" 246 "declare void @innerpreheader()\n" 247 "declare void @outerheader()\n" 248 "declare void @outerlatch()\n" 249 "declare void @innerexit()\n"; 250 251 LLVMContext Context; 252 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 253 254 runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 255 Function::iterator FI = F.begin(); 256 // Skip the first basic block (entry), get to the outer loop header. 257 BasicBlock *Header = &*(++FI); 258 assert(Header->getName() == "for.outer"); 259 Loop *L = LI.getLoopFor(Header); 260 EXPECT_NE(L, nullptr); 261 262 LoopNest LN(*L, SE); 263 EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); 264 265 // Ensure that we can identify the outermost loop in the nest. 266 const Loop &OL = LN.getOutermostLoop(); 267 EXPECT_EQ(OL.getName(), "for.outer"); 268 269 // Ensure that we can identify the innermost loop in the nest. 270 const Loop *IL = LN.getInnermostLoop(); 271 EXPECT_NE(IL, nullptr); 272 EXPECT_EQ(IL->getName(), "for.inner"); 273 274 // Ensure the loop nest is recognized as having 2 loops. 275 const ArrayRef<Loop *> Loops = LN.getLoops(); 276 EXPECT_EQ(Loops.size(), 2ull); 277 278 // Ensure the loop nest is not recognized as perfect in its entirety. 279 const SmallVector<LoopVectorTy, 4> &PLV = LN.getPerfectLoops(SE); 280 EXPECT_EQ(PLV.size(), 2ull); 281 EXPECT_EQ(PLV.front().size(), 1ull); 282 EXPECT_EQ(PLV.back().size(), 1ull); 283 284 // Ensure the nest depth and perfect nest depth are computed correctly. 285 EXPECT_EQ(LN.getNestDepth(), 2u); 286 EXPECT_EQ(LN.getMaxPerfectDepth(), 1u); 287 288 // Ensure enclosed instructions are recognized 289 const LoopNest::InstrVectorTy InstrV = 290 LN.getInterveningInstructions(OL, *IL, SE); 291 EXPECT_EQ(InstrV.size(), 5u); 292 293 Instruction *SI = getInstructionByName(F, "varr")->getNextNode(); 294 Instruction *CI = SI->getNextNode(); 295 Instruction *OLH = 296 getInstructionByName(F, "i")->getNextNode()->getNextNode(); 297 Instruction *OLL = getInstructionByName(F, "inc13")->getNextNode(); 298 Instruction *IE = getInstructionByName(F, "varr1")->getNextNode(); 299 300 EXPECT_EQ(InstrV.front(), OLH); 301 EXPECT_EQ(InstrV[1], OLL); 302 EXPECT_EQ(InstrV[2], IE); 303 EXPECT_EQ(InstrV[3], SI); 304 EXPECT_EQ(InstrV.back(), CI); 305 }); 306 } 307