279 lines · cpp
1//===- LoopUtilsTest.cpp - Unit tests for LoopUtils -----------------------===//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/Transforms/Utils/LoopUtils.h"10#include "llvm/Analysis/AssumptionCache.h"11#include "llvm/Analysis/LoopInfo.h"12#include "llvm/Analysis/ScalarEvolution.h"13#include "llvm/Analysis/TargetLibraryInfo.h"14#include "llvm/AsmParser/Parser.h"15#include "llvm/IR/Dominators.h"16#include "llvm/IR/Module.h"17#include "llvm/IR/ProfDataUtils.h"18#include "llvm/Support/SourceMgr.h"19#include "gtest/gtest.h"20 21using namespace llvm;22 23static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {24 SMDiagnostic Err;25 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);26 if (!Mod)27 Err.print("LoopUtilsTests", errs());28 return Mod;29}30 31static void run(Module &M, StringRef FuncName,32 function_ref<void(Function &F, DominatorTree &DT,33 ScalarEvolution &SE, LoopInfo &LI)>34 Test) {35 Function *F = M.getFunction(FuncName);36 DominatorTree DT(*F);37 TargetLibraryInfoImpl TLII(M.getTargetTriple());38 TargetLibraryInfo TLI(TLII);39 AssumptionCache AC(*F);40 LoopInfo LI(DT);41 ScalarEvolution SE(*F, TLI, AC, DT, LI);42 Test(*F, DT, SE, LI);43}44 45TEST(LoopUtils, DeleteDeadLoopNest) {46 LLVMContext C;47 std::unique_ptr<Module> M =48 parseIR(C, "define void @foo() {\n"49 "entry:\n"50 " br label %for.i\n"51 "for.i:\n"52 " %i = phi i64 [ 0, %entry ], [ %inc.i, %for.i.latch ]\n"53 " br label %for.j\n"54 "for.j:\n"55 " %j = phi i64 [ 0, %for.i ], [ %inc.j, %for.j ]\n"56 " %inc.j = add nsw i64 %j, 1\n"57 " %cmp.j = icmp slt i64 %inc.j, 100\n"58 " br i1 %cmp.j, label %for.j, label %for.k.preheader\n"59 "for.k.preheader:\n"60 " br label %for.k\n"61 "for.k:\n"62 " %k = phi i64 [ %inc.k, %for.k ], [ 0, %for.k.preheader ]\n"63 " %inc.k = add nsw i64 %k, 1\n"64 " %cmp.k = icmp slt i64 %inc.k, 100\n"65 " br i1 %cmp.k, label %for.k, label %for.i.latch\n"66 "for.i.latch:\n"67 " %inc.i = add nsw i64 %i, 1\n"68 " %cmp.i = icmp slt i64 %inc.i, 100\n"69 " br i1 %cmp.i, label %for.i, label %for.end\n"70 "for.end:\n"71 " ret void\n"72 "}\n");73 74 run(*M, "foo",75 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) {76 assert(LI.begin() != LI.end() && "Expecting loops in function F");77 Loop *L = *LI.begin();78 assert(L && L->getName() == "for.i" && "Expecting loop for.i");79 80 deleteDeadLoop(L, &DT, &SE, &LI);81 82 assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&83 "Expecting valid dominator tree");84 LI.verify(DT);85 assert(LI.begin() == LI.end() &&86 "Expecting no loops left in function F");87 SE.verify();88 89 Function::iterator FI = F.begin();90 BasicBlock *Entry = &*(FI++);91 assert(Entry->getName() == "entry" && "Expecting BasicBlock entry");92 const BranchInst *BI = dyn_cast<BranchInst>(Entry->getTerminator());93 assert(BI && "Expecting valid branch instruction");94 EXPECT_EQ(BI->getNumSuccessors(), (unsigned)1);95 EXPECT_EQ(BI->getSuccessor(0)->getName(), "for.end");96 });97}98 99TEST(LoopUtils, IsKnownPositiveInLoopTest) {100 LLVMContext C;101 std::unique_ptr<Module> M =102 parseIR(C, "define void @foo(i32 %n, i1 %c) {\n"103 "entry:\n"104 " %is.positive = icmp sgt i32 %n, 0\n"105 " br i1 %is.positive, label %loop, label %exit\n"106 "loop:\n"107 " br i1 %c, label %loop, label %exit\n"108 "exit:\n"109 " ret void\n"110 "}\n");111 112 run(*M, "foo",113 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) {114 assert(LI.begin() != LI.end() && "Expecting loops in function F");115 Loop *L = *LI.begin();116 assert(L && L->getName() == "loop" && "Expecting loop 'loop'");117 auto *Arg = F.getArg(0);118 const SCEV *ArgSCEV = SE.getSCEV(Arg);119 EXPECT_EQ(isKnownPositiveInLoop(ArgSCEV, L, SE), true);120 });121}122 123TEST(LoopUtils, IsKnownNonPositiveInLoopTest) {124 LLVMContext C;125 std::unique_ptr<Module> M =126 parseIR(C, "define void @foo(i32 %n, i1 %c) {\n"127 "entry:\n"128 " %is.non.positive = icmp sle i32 %n, 0\n"129 " br i1 %is.non.positive, label %loop, label %exit\n"130 "loop:\n"131 " br i1 %c, label %loop, label %exit\n"132 "exit:\n"133 " ret void\n"134 "}\n");135 136 run(*M, "foo",137 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) {138 assert(LI.begin() != LI.end() && "Expecting loops in function F");139 Loop *L = *LI.begin();140 assert(L && L->getName() == "loop" && "Expecting loop 'loop'");141 auto *Arg = F.getArg(0);142 const SCEV *ArgSCEV = SE.getSCEV(Arg);143 EXPECT_EQ(isKnownNonPositiveInLoop(ArgSCEV, L, SE), true);144 });145}146 147// The inner and outer loop here share a latch. Because any loop metadata must148// be attached to that latch, loop metadata cannot distinguish between the two149// loops. Until that problem is solved (by moving loop metadata to loops'150// header blocks instead), getLoopEstimatedTripCount and151// setLoopEstimatedTripCount must refuse to operate on at least one of the two152// loops. They choose to reject the outer loop here because the latch does not153// exit it.154TEST(LoopUtils, nestedLoopSharedLatchEstimatedTripCount) {155 LLVMContext C;156 std::unique_ptr<Module> M =157 parseIR(C, "declare i1 @f()\n"158 "declare i1 @g()\n"159 "define void @foo() {\n"160 "entry:\n"161 " br label %outer\n"162 "outer:\n"163 " %c0 = call i1 @f()"164 " br i1 %c0, label %inner, label %exit, !prof !0\n"165 "inner:\n"166 " %c1 = call i1 @g()"167 " br i1 %c1, label %inner, label %outer, !prof !1\n"168 "exit:\n"169 " ret void\n"170 "}\n"171 "!0 = !{!\"branch_weights\", i32 100, i32 1}\n"172 "!1 = !{!\"branch_weights\", i32 4, i32 1}\n"173 "\n");174 175 run(*M, "foo",176 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) {177 assert(LI.end() - LI.begin() == 1 && "Expected one outer loop");178 Loop *Outer = *LI.begin();179 assert(Outer->end() - Outer->begin() == 1 && "Expected one inner loop");180 Loop *Inner = *Outer->begin();181 182 // Even before llvm.loop.estimated_trip_count is added to either loop,183 // getLoopEstimatedTripCount rejects the outer loop.184 EXPECT_EQ(getLoopEstimatedTripCount(Inner), 5);185 EXPECT_EQ(getLoopEstimatedTripCount(Outer), std::nullopt);186 187 // setLoopEstimatedTripCount for the inner loop does not affect188 // getLoopEstimatedTripCount for the outer loop.189 EXPECT_EQ(setLoopEstimatedTripCount(Inner, 100), true);190 EXPECT_EQ(getLoopEstimatedTripCount(Inner), 100);191 EXPECT_EQ(getLoopEstimatedTripCount(Outer), std::nullopt);192 193 // setLoopEstimatedTripCount rejects the outer loop.194 EXPECT_EQ(setLoopEstimatedTripCount(Outer, 999), false);195 EXPECT_EQ(getLoopEstimatedTripCount(Inner), 100);196 EXPECT_EQ(getLoopEstimatedTripCount(Outer), std::nullopt);197 });198}199 200// {get,set}LoopEstimatedTripCount implement special handling of zero.201TEST(LoopUtils, zeroEstimatedTripCount) {202 LLVMContext C;203 const char *IR =204 "define void @foo(i1 %c) {\n"205 "entry:\n"206 " br label %loop0\n"207 "loop0:\n"208 " br i1 %c, label %loop0, label %loop1\n"209 "loop1:\n"210 " br i1 %c, label %loop1, label %loop2, !llvm.loop !1\n"211 "loop2:\n"212 " br i1 %c, label %loop2, label %exit, !prof !5, !llvm.loop !2\n"213 "exit:\n"214 " ret void\n"215 "}\n"216 "!1 = distinct !{!1, !3}\n"217 "!2 = distinct !{!2, !3, !4}\n"218 "!3 = !{!\"foo\", i32 5}\n"219 "!4 = !{!\"llvm.loop.estimated_trip_count\", i32 10}\n"220 "!5 = !{!\"branch_weights\", i32 1, i32 9}\n"221 "\n";222 223 // With EstimatedLoopInvocationWeight, setLoopEstimatedTripCount sets branch224 // weights and llvm.loop.estimated_trip_count all to 0, so225 // getLoopEstimatedTripCount returns std::nullopt. It does not touch other226 // loop metadata, if any.227 std::unique_ptr<Module> M = parseIR(C, IR);228 run(*M, "foo",229 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) {230 assert(LI.end() - LI.begin() == 3 && "Expected three loops");231 for (Loop *L : LI) {232 Instruction &LatchBranch = *L->getLoopLatch()->getTerminator();233 std::optional<int> Foo = getOptionalIntLoopAttribute(L, "foo");234 235 EXPECT_EQ(setLoopEstimatedTripCount(236 L, 0, /*EstimatedLoopInvocationWeight=*/1),237 true);238 239 SmallVector<uint32_t, 2> Weights;240 EXPECT_EQ(extractBranchWeights(LatchBranch, Weights), true);241 EXPECT_EQ(Weights[0], 0u);242 EXPECT_EQ(Weights[1], 0u);243 EXPECT_EQ(getOptionalIntLoopAttribute(L, "foo"), Foo);244 EXPECT_EQ(getOptionalIntLoopAttribute(L, LLVMLoopEstimatedTripCount),245 0);246 EXPECT_EQ(getLoopEstimatedTripCount(L), std::nullopt);247 }248 });249 250 // Without EstimatedLoopInvocationWeight, setLoopEstimatedTripCount sets251 // llvm.loop.estimated_trip_count to 0, so getLoopEstimatedTripCount returns252 // std::nullopt. It does not touch branch weights or other loop metadata, if253 // any.254 M = parseIR(C, IR);255 run(*M, "foo",256 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) {257 assert(LI.end() - LI.begin() == 3 && "Expected three loops");258 for (Loop *L : LI) {259 Instruction &LatchBranch = *L->getLoopLatch()->getTerminator();260 std::optional<int> Foo = getOptionalIntLoopAttribute(L, "foo");261 SmallVector<uint32_t, 2> WeightsOld;262 bool HasWeights = extractBranchWeights(LatchBranch, WeightsOld);263 264 EXPECT_EQ(setLoopEstimatedTripCount(L, 0), true);265 266 SmallVector<uint32_t, 2> WeightsNew;267 EXPECT_EQ(extractBranchWeights(LatchBranch, WeightsNew), HasWeights);268 if (HasWeights) {269 EXPECT_EQ(WeightsNew[0], WeightsOld[0]);270 EXPECT_EQ(WeightsNew[1], WeightsOld[1]);271 }272 EXPECT_EQ(getOptionalIntLoopAttribute(L, "foo"), Foo);273 EXPECT_EQ(getOptionalIntLoopAttribute(L, LLVMLoopEstimatedTripCount),274 0);275 EXPECT_EQ(getLoopEstimatedTripCount(L), std::nullopt);276 }277 });278}279