321 lines · 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-exception6//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 19using namespace llvm;20 21/// Build the loop nest analysis for a loop nest and run the given test \p Test.22static 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(M.getTargetTriple());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 38static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,39 const char *ModuleStr) {40 SMDiagnostic Err;41 return parseAssemblyString(ModuleStr, Err, Context);42}43 44static 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 52TEST(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 back119 // 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 136TEST(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 222TEST(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 recognized303 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}321