From 4d6f3ee2ba5b3ea6d9f80e7baf9a746848c790aa Mon Sep 17 00:00:00 2001 From: Hiroshi Yamauchi Date: Thu, 27 Feb 2020 10:49:04 -0800 Subject: [PATCH] [PSI] Add the isCold query support with a given percentile value. Summary: This follows up D67377 that added the isHot side. Reviewers: davidxl Subscribers: eraman, hiraditya, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D75283 --- llvm/include/llvm/Analysis/ProfileSummaryInfo.h | 23 ++++ llvm/lib/Analysis/ProfileSummaryInfo.cpp | 77 ++++++++++--- llvm/unittests/Analysis/ProfileSummaryInfoTest.cpp | 126 +++++++++++++++++++++ 3 files changed, 213 insertions(+), 13 deletions(-) diff --git a/llvm/include/llvm/Analysis/ProfileSummaryInfo.h b/llvm/include/llvm/Analysis/ProfileSummaryInfo.h index 6693e40..f90dcf6 100644 --- a/llvm/include/llvm/Analysis/ProfileSummaryInfo.h +++ b/llvm/include/llvm/Analysis/ProfileSummaryInfo.h @@ -120,6 +120,11 @@ public: bool isFunctionHotInCallGraphNthPercentile(int PercentileCutoff, const Function *F, BlockFrequencyInfo &BFI); + /// Returns true if \p F contains cold code with regard to a given cold + /// percentile cutoff value. + bool isFunctionColdInCallGraphNthPercentile(int PercentileCutoff, + const Function *F, + BlockFrequencyInfo &BFI); /// Returns true if count \p C is considered hot. bool isHotCount(uint64_t C); /// Returns true if count \p C is considered cold. @@ -127,6 +132,9 @@ public: /// Returns true if count \p C is considered hot with regard to a given /// hot percentile cutoff value. bool isHotCountNthPercentile(int PercentileCutoff, uint64_t C); + /// Returns true if count \p C is considered cold with regard to a given + /// cold percentile cutoff value. + bool isColdCountNthPercentile(int PercentileCutoff, uint64_t C); /// Returns true if BasicBlock \p BB is considered hot. bool isHotBlock(const BasicBlock *BB, BlockFrequencyInfo *BFI); /// Returns true if BasicBlock \p BB is considered cold. @@ -135,6 +143,10 @@ public: /// hot percentile cutoff value. bool isHotBlockNthPercentile(int PercentileCutoff, const BasicBlock *BB, BlockFrequencyInfo *BFI); + /// Returns true if BasicBlock \p BB is considered cold with regard to a given + /// cold percentile cutoff value. + bool isColdBlockNthPercentile(int PercentileCutoff, + const BasicBlock *BB, BlockFrequencyInfo *BFI); /// Returns true if CallSite \p CS is considered hot. bool isHotCallSite(const CallSite &CS, BlockFrequencyInfo *BFI); /// Returns true if Callsite \p CS is considered cold. @@ -153,6 +165,17 @@ public: uint64_t getColdCountThreshold() { return ColdCountThreshold ? ColdCountThreshold.getValue() : 0; } + + private: + template + bool isFunctionHotOrColdInCallGraphNthPercentile(int PercentileCutoff, + const Function *F, + BlockFrequencyInfo &BFI); + template + bool isHotOrColdCountNthPercentile(int PercentileCutoff, uint64_t C); + template + bool isHotOrColdBlockNthPercentile(int PercentileCutoff, const BasicBlock *BB, + BlockFrequencyInfo *BFI); }; /// An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo. diff --git a/llvm/lib/Analysis/ProfileSummaryInfo.cpp b/llvm/lib/Analysis/ProfileSummaryInfo.cpp index 911d39d..678d66f 100644 --- a/llvm/lib/Analysis/ProfileSummaryInfo.cpp +++ b/llvm/lib/Analysis/ProfileSummaryInfo.cpp @@ -195,15 +195,19 @@ bool ProfileSummaryInfo::isFunctionColdInCallGraph(const Function *F, return true; } -// Like isFunctionHotInCallGraph but for a given cutoff. -bool ProfileSummaryInfo::isFunctionHotInCallGraphNthPercentile( +template +bool ProfileSummaryInfo::isFunctionHotOrColdInCallGraphNthPercentile( int PercentileCutoff, const Function *F, BlockFrequencyInfo &BFI) { if (!F || !computeSummary()) return false; - if (auto FunctionCount = F->getEntryCount()) - if (isHotCountNthPercentile(PercentileCutoff, FunctionCount.getCount())) + if (auto FunctionCount = F->getEntryCount()) { + if (isHot && + isHotCountNthPercentile(PercentileCutoff, FunctionCount.getCount())) return true; - + if (!isHot && + !isColdCountNthPercentile(PercentileCutoff, FunctionCount.getCount())) + return false; + } if (hasSampleProfile()) { uint64_t TotalCallCount = 0; for (const auto &BB : *F) @@ -211,13 +215,31 @@ bool ProfileSummaryInfo::isFunctionHotInCallGraphNthPercentile( if (isa(I) || isa(I)) if (auto CallCount = getProfileCount(&I, nullptr)) TotalCallCount += CallCount.getValue(); - if (isHotCountNthPercentile(PercentileCutoff, TotalCallCount)) + if (isHot && isHotCountNthPercentile(PercentileCutoff, TotalCallCount)) return true; + if (!isHot && !isColdCountNthPercentile(PercentileCutoff, TotalCallCount)) + return false; } - for (const auto &BB : *F) - if (isHotBlockNthPercentile(PercentileCutoff, &BB, &BFI)) + for (const auto &BB : *F) { + if (isHot && isHotBlockNthPercentile(PercentileCutoff, &BB, &BFI)) return true; - return false; + if (!isHot && !isColdBlockNthPercentile(PercentileCutoff, &BB, &BFI)) + return false; + } + return !isHot; +} + +// Like isFunctionHotInCallGraph but for a given cutoff. +bool ProfileSummaryInfo::isFunctionHotInCallGraphNthPercentile( + int PercentileCutoff, const Function *F, BlockFrequencyInfo &BFI) { + return isFunctionHotOrColdInCallGraphNthPercentile( + PercentileCutoff, F, BFI); +} + +bool ProfileSummaryInfo::isFunctionColdInCallGraphNthPercentile( + int PercentileCutoff, const Function *F, BlockFrequencyInfo &BFI) { + return isFunctionHotOrColdInCallGraphNthPercentile( + PercentileCutoff, F, BFI); } /// Returns true if the function's entry is a cold. If it returns false, it @@ -299,9 +321,22 @@ bool ProfileSummaryInfo::isColdCount(uint64_t C) { return ColdCountThreshold && C <= ColdCountThreshold.getValue(); } -bool ProfileSummaryInfo::isHotCountNthPercentile(int PercentileCutoff, uint64_t C) { +template +bool ProfileSummaryInfo::isHotOrColdCountNthPercentile(int PercentileCutoff, + uint64_t C) { auto CountThreshold = computeThreshold(PercentileCutoff); - return CountThreshold && C >= CountThreshold.getValue(); + if (isHot) + return CountThreshold && C >= CountThreshold.getValue(); + else + return CountThreshold && C <= CountThreshold.getValue(); +} + +bool ProfileSummaryInfo::isHotCountNthPercentile(int PercentileCutoff, uint64_t C) { + return isHotOrColdCountNthPercentile(PercentileCutoff, C); +} + +bool ProfileSummaryInfo::isColdCountNthPercentile(int PercentileCutoff, uint64_t C) { + return isHotOrColdCountNthPercentile(PercentileCutoff, C); } uint64_t ProfileSummaryInfo::getOrCompHotCountThreshold() { @@ -327,11 +362,27 @@ bool ProfileSummaryInfo::isColdBlock(const BasicBlock *BB, return Count && isColdCount(*Count); } +template +bool ProfileSummaryInfo::isHotOrColdBlockNthPercentile(int PercentileCutoff, + const BasicBlock *BB, + BlockFrequencyInfo *BFI) { + auto Count = BFI->getBlockProfileCount(BB); + if (isHot) + return Count && isHotCountNthPercentile(PercentileCutoff, *Count); + else + return Count && isColdCountNthPercentile(PercentileCutoff, *Count); +} + bool ProfileSummaryInfo::isHotBlockNthPercentile(int PercentileCutoff, const BasicBlock *BB, BlockFrequencyInfo *BFI) { - auto Count = BFI->getBlockProfileCount(BB); - return Count && isHotCountNthPercentile(PercentileCutoff, *Count); + return isHotOrColdBlockNthPercentile(PercentileCutoff, BB, BFI); +} + +bool ProfileSummaryInfo::isColdBlockNthPercentile(int PercentileCutoff, + const BasicBlock *BB, + BlockFrequencyInfo *BFI) { + return isHotOrColdBlockNthPercentile(PercentileCutoff, BB, BFI); } bool ProfileSummaryInfo::isHotCallSite(const CallSite &CS, diff --git a/llvm/unittests/Analysis/ProfileSummaryInfoTest.cpp b/llvm/unittests/Analysis/ProfileSummaryInfoTest.cpp index 8072e05..6c4e42a 100644 --- a/llvm/unittests/Analysis/ProfileSummaryInfoTest.cpp +++ b/llvm/unittests/Analysis/ProfileSummaryInfoTest.cpp @@ -65,6 +65,20 @@ protected: " %y2 = phi i32 [0, %bb1], [1, %bb2] \n" " ret i32 %y2\n" "}\n" + "define i32 @l(i32 %x) {{\n" + "bb0:\n" + " %y1 = icmp eq i32 %x, 0 \n" + " br i1 %y1, label %bb1, label %bb2, !prof !23 \n" + "bb1:\n" + " %z1 = call i32 @g(i32 %x)\n" + " br label %bb3\n" + "bb2:\n" + " %z2 = call i32 @h(i32 %x)\n" + " br label %bb3\n" + "bb3:\n" + " %y2 = phi i32 [0, %bb1], [1, %bb2] \n" + " ret i32 %y2\n" + "}\n" "!20 = !{{!\"function_entry_count\", i64 400}\n" "!21 = !{{!\"function_entry_count\", i64 1}\n" "!22 = !{{!\"function_entry_count\", i64 100}\n" @@ -141,14 +155,26 @@ TEST_F(ProfileSummaryInfoTest, TestCommon) { EXPECT_FALSE(PSI.isHotCountNthPercentile(990000, 100)); EXPECT_FALSE(PSI.isHotCountNthPercentile(990000, 2)); + EXPECT_FALSE(PSI.isColdCountNthPercentile(990000, 400)); + EXPECT_TRUE(PSI.isColdCountNthPercentile(990000, 100)); + EXPECT_TRUE(PSI.isColdCountNthPercentile(990000, 2)); + EXPECT_TRUE(PSI.isHotCountNthPercentile(999999, 400)); EXPECT_TRUE(PSI.isHotCountNthPercentile(999999, 100)); EXPECT_FALSE(PSI.isHotCountNthPercentile(999999, 2)); + EXPECT_FALSE(PSI.isColdCountNthPercentile(999999, 400)); + EXPECT_FALSE(PSI.isColdCountNthPercentile(999999, 100)); + EXPECT_TRUE(PSI.isColdCountNthPercentile(999999, 2)); + EXPECT_FALSE(PSI.isHotCountNthPercentile(10000, 400)); EXPECT_FALSE(PSI.isHotCountNthPercentile(10000, 100)); EXPECT_FALSE(PSI.isHotCountNthPercentile(10000, 2)); + EXPECT_TRUE(PSI.isColdCountNthPercentile(10000, 400)); + EXPECT_TRUE(PSI.isColdCountNthPercentile(10000, 100)); + EXPECT_TRUE(PSI.isColdCountNthPercentile(10000, 2)); + EXPECT_TRUE(PSI.isFunctionEntryHot(F)); EXPECT_FALSE(PSI.isFunctionEntryHot(G)); EXPECT_FALSE(PSI.isFunctionEntryHot(H)); @@ -177,16 +203,31 @@ TEST_F(ProfileSummaryInfoTest, InstrProf) { EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB2, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, BB3, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB3, &BFI)); + EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, &BB0, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB1, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB2, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB3, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, &BB0, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, BB1, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, BB2, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, BB3, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, &BB0, &BFI)); EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB1, &BFI)); EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB2, &BFI)); EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB3, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, &BB0, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, BB1, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, BB2, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, BB3, &BFI)); + CallSite CS1(BB1->getFirstNonPHI()); auto *CI2 = BB2->getFirstNonPHI(); CallSite CS2(CI2); @@ -201,6 +242,31 @@ TEST_F(ProfileSummaryInfoTest, InstrProf) { EXPECT_FALSE(PSI.isHotCallSite(CS2, &BFI)); } +TEST_F(ProfileSummaryInfoTest, InstrProfNoFuncEntryCount) { + auto M = makeLLVMModule("InstrProf"); + Function *F = M->getFunction("l"); + ProfileSummaryInfo PSI = buildPSI(M.get()); + EXPECT_TRUE(PSI.hasProfileSummary()); + EXPECT_TRUE(PSI.hasInstrumentationProfile()); + + BasicBlock &BB0 = F->getEntryBlock(); + BasicBlock *BB1 = BB0.getTerminator()->getSuccessor(0); + BasicBlock *BB2 = BB0.getTerminator()->getSuccessor(1); + BasicBlock *BB3 = BB1->getSingleSuccessor(); + + BlockFrequencyInfo BFI = buildBFI(*F); + + // Without the entry count, all should return false. + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB3, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB3, &BFI)); +} + TEST_F(ProfileSummaryInfoTest, SampleProf) { auto M = makeLLVMModule("SampleProfile"); Function *F = M->getFunction("f"); @@ -224,16 +290,31 @@ TEST_F(ProfileSummaryInfoTest, SampleProf) { EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB2, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, BB3, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB3, &BFI)); + EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, &BB0, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB1, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB2, &BFI)); EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB3, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, &BB0, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, BB1, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, BB2, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(999900, BB3, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, &BB0, &BFI)); EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB1, &BFI)); EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB2, &BFI)); EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB3, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, &BB0, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, BB1, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, BB2, &BFI)); + EXPECT_TRUE(PSI.isColdBlockNthPercentile(10000, BB3, &BFI)); + CallSite CS1(BB1->getFirstNonPHI()); auto *CI2 = BB2->getFirstNonPHI(); // Manually attach branch weights metadata to the call instruction. @@ -250,6 +331,51 @@ TEST_F(ProfileSummaryInfoTest, SampleProf) { // weights that exceed the hot count threshold. CI2->setMetadata(llvm::LLVMContext::MD_prof, MDB.createBranchWeights({400})); EXPECT_TRUE(PSI.isHotCallSite(CS2, &BFI)); + + { + Function *F = M->getFunction("l"); + BlockFrequencyInfo BFI = buildBFI(*F); + BasicBlock &BB0 = F->getEntryBlock(); + BasicBlock *BB1 = BB0.getTerminator()->getSuccessor(0); + BasicBlock *BB2 = BB0.getTerminator()->getSuccessor(1); + BasicBlock *BB3 = BB1->getSingleSuccessor(); + + // Without the entry count, all should return false. + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB3, &BFI)); + + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB3, &BFI)); + } +} + +TEST_F(ProfileSummaryInfoTest, SampleProfNoFuncEntryCount) { + auto M = makeLLVMModule("SampleProfile"); + Function *F = M->getFunction("l"); + ProfileSummaryInfo PSI = buildPSI(M.get()); + EXPECT_TRUE(PSI.hasProfileSummary()); + EXPECT_TRUE(PSI.hasSampleProfile()); + + BasicBlock &BB0 = F->getEntryBlock(); + BasicBlock *BB1 = BB0.getTerminator()->getSuccessor(0); + BasicBlock *BB2 = BB0.getTerminator()->getSuccessor(1); + BasicBlock *BB3 = BB1->getSingleSuccessor(); + + BlockFrequencyInfo BFI = buildBFI(*F); + + // Without the entry count, all should return false. + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB3, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, &BB0, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB1, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB2, &BFI)); + EXPECT_FALSE(PSI.isColdBlockNthPercentile(990000, BB3, &BFI)); } } // end anonymous namespace -- 2.7.4