From e0c5ceae903f6b1bd8c40e62d65e0cc1fdf6e10a Mon Sep 17 00:00:00 2001 From: Teresa Johnson Date: Tue, 12 Jul 2016 21:13:44 +0000 Subject: [PATCH] Refactor indirect call promotion profitability analysis (NFC) Summary: Refactored the profitability analysis out of the IC promotion pass and into lib/Analysis so that it can be accessed by the summary index builder in a follow-on patch to enable IC promotion in ThinLTO (D21932). Reviewers: davidxl, xur Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D22182 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@275216 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../llvm/Analysis/IndirectCallPromotionAnalysis.h | 67 +++++++++++++ .../llvm/Analysis}/IndirectCallSiteVisitor.h | 0 lib/Analysis/CMakeLists.txt | 1 + lib/Analysis/IndirectCallPromotionAnalysis.cpp | 110 +++++++++++++++++++++ lib/Analysis/LLVMBuild.txt | 2 +- .../Instrumentation/IndirectCallPromotion.cpp | 82 ++++----------- .../Instrumentation/PGOInstrumentation.cpp | 2 +- 7 files changed, 201 insertions(+), 63 deletions(-) create mode 100644 include/llvm/Analysis/IndirectCallPromotionAnalysis.h rename {lib/Transforms/Instrumentation => include/llvm/Analysis}/IndirectCallSiteVisitor.h (100%) create mode 100644 lib/Analysis/IndirectCallPromotionAnalysis.cpp diff --git a/include/llvm/Analysis/IndirectCallPromotionAnalysis.h b/include/llvm/Analysis/IndirectCallPromotionAnalysis.h new file mode 100644 index 00000000000..007e4d8602f --- /dev/null +++ b/include/llvm/Analysis/IndirectCallPromotionAnalysis.h @@ -0,0 +1,67 @@ +//===- IndirectCallPromotionAnalysis.h - Indirect call analysis -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// Interface to identify indirect call promotion candidates. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_INDIRECTCALLPROMOTIONANALYSIS_H +#define LLVM_ANALYSIS_INDIRECTCALLPROMOTIONANALYSIS_H + +#include "llvm/ProfileData/InstrProf.h" + +namespace llvm { + +class Instruction; + +// Class for identifying profitable indirect call promotion candidates when +// the indirect-call value profile metadata is available. +class ICallPromotionAnalysis { +private: + // Allocate space to read the profile annotation. + std::unique_ptr ValueDataArray; + + // Count is the call count for the direct-call target and + // TotalCount is the call count for the indirect-call callsite. + // Return true we should promote this indirect-call target. + bool isPromotionProfitable(uint64_t Count, uint64_t TotalCount); + + // Returns the number of profitable candidates to promote for the + // current ValueDataArray and the given \p Inst. + uint32_t getProfitablePromotionCandidates(const Instruction *Inst, + uint32_t NumVals, + uint64_t TotalCount); + + // Noncopyable + ICallPromotionAnalysis(const ICallPromotionAnalysis &other) = delete; + ICallPromotionAnalysis & + operator=(const ICallPromotionAnalysis &other) = delete; + +public: + ICallPromotionAnalysis(); + + /// \brief Returns reference to array of InstrProfValueData for the given + /// instruction \p I. + /// + /// The \p NumVals, \p TotalCount and \p NumCandidates + /// are set to the number of values in the array, the total profile count + /// of the indirect call \p I, and the number of profitable candidates + /// in the given array (which is sorted in reverse order of profitability). + /// + /// The returned array space is owned by this class, and overwritten on + /// subsequent calls. + ArrayRef + getPromotionCandidatesForInstruction(const Instruction *I, uint32_t &NumVals, + uint64_t &TotalCount, + uint32_t &NumCandidates); +}; + +} // end namespace llvm + +#endif diff --git a/lib/Transforms/Instrumentation/IndirectCallSiteVisitor.h b/include/llvm/Analysis/IndirectCallSiteVisitor.h similarity index 100% rename from lib/Transforms/Instrumentation/IndirectCallSiteVisitor.h rename to include/llvm/Analysis/IndirectCallSiteVisitor.h diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index a6d8d54488a..ee9edd8b01a 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -30,6 +30,7 @@ add_llvm_library(LLVMAnalysis EHPersonalities.cpp GlobalsModRef.cpp IVUsers.cpp + IndirectCallPromotionAnalysis.cpp InlineCost.cpp InstCount.cpp InstructionSimplify.cpp diff --git a/lib/Analysis/IndirectCallPromotionAnalysis.cpp b/lib/Analysis/IndirectCallPromotionAnalysis.cpp new file mode 100644 index 00000000000..b3941a4004a --- /dev/null +++ b/lib/Analysis/IndirectCallPromotionAnalysis.cpp @@ -0,0 +1,110 @@ +//===-- IndirectCallPromotionAnalysis.cpp - Find promotion candidates ===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Helper methods for identifying profitable indirect call promotion +// candidates for an instruction when the indirect-call value profile metadata +// is available. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/IndirectCallPromotionAnalysis.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/IndirectCallSiteVisitor.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/DiagnosticInfo.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/InstVisitor.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/ProfileData/InstrProf.h" +#include "llvm/Support/Debug.h" +#include +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "pgo-icall-prom-analysis" + +// The minimum call count for the direct-call target to be considered as the +// promotion candidate. +static cl::opt + ICPCountThreshold("icp-count-threshold", cl::Hidden, cl::ZeroOrMore, + cl::init(1000), + cl::desc("The minimum count to the direct call target " + "for the promotion")); + +// The percent threshold for the direct-call target (this call site vs the +// total call count) for it to be considered as the promotion target. +static cl::opt + ICPPercentThreshold("icp-percent-threshold", cl::init(33), cl::Hidden, + cl::ZeroOrMore, + cl::desc("The percentage threshold for the promotion")); + +// Set the maximum number of targets to promote for a single indirect-call +// callsite. +static cl::opt + MaxNumPromotions("icp-max-prom", cl::init(2), cl::Hidden, cl::ZeroOrMore, + cl::desc("Max number of promotions for a single indirect " + "call callsite")); + +ICallPromotionAnalysis::ICallPromotionAnalysis() { + ValueDataArray = llvm::make_unique(MaxNumPromotions); +} + +bool ICallPromotionAnalysis::isPromotionProfitable(uint64_t Count, + uint64_t TotalCount) { + if (Count < ICPCountThreshold) + return false; + + unsigned Percentage = (Count * 100) / TotalCount; + return (Percentage >= ICPPercentThreshold); +} + +// Indirect-call promotion heuristic. The direct targets are sorted based on +// the count. Stop at the first target that is not promoted. Returns the +// number of candidates deemed profitable. +uint32_t ICallPromotionAnalysis::getProfitablePromotionCandidates( + const Instruction *Inst, uint32_t NumVals, uint64_t TotalCount) { + ArrayRef ValueDataRef(ValueDataArray.get(), NumVals); + + DEBUG(dbgs() << " \nWork on callsite " << *Inst << " Num_targets: " << NumVals + << "\n"); + + uint32_t I = 0; + for (; I < MaxNumPromotions && I < NumVals; I++) { + uint64_t Count = ValueDataRef[I].Count; + assert(Count <= TotalCount); + uint64_t Target = ValueDataRef[I].Value; + DEBUG(dbgs() << " Candidate " << I << " Count=" << Count + << " Target_func: " << Target << "\n"); + + if (!isPromotionProfitable(Count, TotalCount)) { + DEBUG(dbgs() << " Not promote: Cold target.\n"); + return I; + } + TotalCount -= Count; + } + return I; +} + +ArrayRef +ICallPromotionAnalysis::getPromotionCandidatesForInstruction( + const Instruction *I, uint32_t &NumVals, uint64_t &TotalCount, + uint32_t &NumCandidates) { + bool Res = + getValueProfDataFromInst(*I, IPVK_IndirectCallTarget, MaxNumPromotions, + ValueDataArray.get(), NumVals, TotalCount); + if (!Res) { + NumCandidates = 0; + return ArrayRef(); + } + NumCandidates = getProfitablePromotionCandidates(I, NumVals, TotalCount); + return ArrayRef(ValueDataArray.get(), NumVals); +} diff --git a/lib/Analysis/LLVMBuild.txt b/lib/Analysis/LLVMBuild.txt index bddf1a3ac20..08af5f37700 100644 --- a/lib/Analysis/LLVMBuild.txt +++ b/lib/Analysis/LLVMBuild.txt @@ -19,4 +19,4 @@ type = Library name = Analysis parent = Libraries -required_libraries = Core Support +required_libraries = Core Support ProfileData diff --git a/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp b/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp index 92847c59be1..c9bc7db38ca 100644 --- a/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp +++ b/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp @@ -13,11 +13,12 @@ // //===----------------------------------------------------------------------===// -#include "IndirectCallSiteVisitor.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Triple.h" #include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/IndirectCallPromotionAnalysis.h" +#include "llvm/Analysis/IndirectCallSiteVisitor.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/IRBuilder.h" @@ -49,28 +50,6 @@ STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites."); static cl::opt DisableICP("disable-icp", cl::init(false), cl::Hidden, cl::desc("Disable indirect call promotion")); -// The minimum call count for the direct-call target to be considered as the -// promotion candidate. -static cl::opt - ICPCountThreshold("icp-count-threshold", cl::Hidden, cl::ZeroOrMore, - cl::init(1000), - cl::desc("The minimum count to the direct call target " - "for the promotion")); - -// The percent threshold for the direct-call target (this call site vs the -// total call count) for it to be considered as the promotion target. -static cl::opt - ICPPercentThreshold("icp-percent-threshold", cl::init(33), cl::Hidden, - cl::ZeroOrMore, - cl::desc("The percentage threshold for the promotion")); - -// Set the maximum number of targets to promote for a single indirect-call -// callsite. -static cl::opt - MaxNumPromotions("icp-max-prom", cl::init(2), cl::Hidden, cl::ZeroOrMore, - cl::desc("Max number of promotions for a single indirect " - "call callsite")); - // Set the cutoff value for the promotion. If the value is other than 0, we // stop the transformation once the total number of promotions equals the cutoff // value. @@ -91,6 +70,7 @@ static cl::opt static cl::opt ICPLTOMode("icp-lto", cl::init(false), cl::Hidden, cl::desc("Run indirect-call promotion in LTO " "mode")); + // If the option is set to true, only call instructions will be considered for // transformation -- invoke instructions will be ignored. static cl::opt @@ -157,14 +137,6 @@ private: // defines. InstrProfSymtab *Symtab; - // Allocate space to read the profile annotation. - std::unique_ptr ValueDataArray; - - // Count is the call count for the direct-call target and - // TotalCount is the call count for the indirect-call callsite. - // Return true we should promote this indirect-call target. - bool isPromotionProfitable(uint64_t Count, uint64_t TotalCount); - enum TargetStatus { OK, // Should be able to promote. NotAvailableInModule, // Cannot find the target in current module. @@ -185,10 +157,13 @@ private: }; // Check if the indirect-call call site should be promoted. Return the number - // of promotions. + // of promotions. Inst is the candidate indirect call, ValueDataRef + // contains the array of value profile data for profiled targets, + // TotalCount is the total profiled count of call executions, and + // NumCandidates is the number of candidate entries in ValueDataRef. std::vector getPromotionCandidatesForCallSite( Instruction *Inst, const ArrayRef &ValueDataRef, - uint64_t TotalCount); + uint64_t TotalCount, uint32_t NumCandidates); // Main function that transforms Inst (either a indirect-call instruction, or // an invoke instruction , to a conditional call to F. This is like: @@ -232,21 +207,11 @@ private: public: ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab) : F(Func), M(Modu), Symtab(Symtab) { - ValueDataArray = llvm::make_unique(MaxNumPromotions); } bool processFunction(); }; } // end anonymous namespace -bool ICallPromotionFunc::isPromotionProfitable(uint64_t Count, - uint64_t TotalCount) { - if (Count < ICPCountThreshold) - return false; - - unsigned Percentage = (Count * 100) / TotalCount; - return (Percentage >= ICPPercentThreshold); -} - ICallPromotionFunc::TargetStatus ICallPromotionFunc::isPromotionLegal(Instruction *Inst, uint64_t Target, Function *&TargetFunction) { @@ -291,19 +256,20 @@ ICallPromotionFunc::isPromotionLegal(Instruction *Inst, uint64_t Target, std::vector ICallPromotionFunc::getPromotionCandidatesForCallSite( Instruction *Inst, const ArrayRef &ValueDataRef, - uint64_t TotalCount) { + uint64_t TotalCount, uint32_t NumCandidates) { uint32_t NumVals = ValueDataRef.size(); std::vector Ret; DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << *Inst - << " Num_targets: " << NumVals << "\n"); + << " Num_targets: " << NumVals + << " Num_candidates: " << NumCandidates << "\n"); NumOfPGOICallsites++; if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) { DEBUG(dbgs() << " Skip: User options.\n"); return Ret; } - for (uint32_t I = 0; I < MaxNumPromotions && I < NumVals; I++) { + for (uint32_t I = 0; I < NumCandidates; I++) { uint64_t Count = ValueDataRef[I].Count; assert(Count <= TotalCount); uint64_t Target = ValueDataRef[I].Value; @@ -322,10 +288,6 @@ ICallPromotionFunc::getPromotionCandidatesForCallSite( DEBUG(dbgs() << " Not promote: Cutoff reached.\n"); break; } - if (!isPromotionProfitable(Count, TotalCount)) { - DEBUG(dbgs() << " Not promote: Cold target.\n"); - break; - } Function *TargetFunction = nullptr; TargetStatus Status = isPromotionLegal(Inst, Target, TargetFunction); if (Status != OK) { @@ -633,18 +595,16 @@ uint32_t ICallPromotionFunc::tryToPromote( // annotation to perform indirect-call promotion. bool ICallPromotionFunc::processFunction() { bool Changed = false; + ICallPromotionAnalysis ICallAnalysis; for (auto &I : findIndirectCallSites(F)) { - uint32_t NumVals; + uint32_t NumVals, NumCandidates; uint64_t TotalCount; - bool Res = - getValueProfDataFromInst(*I, IPVK_IndirectCallTarget, MaxNumPromotions, - ValueDataArray.get(), NumVals, TotalCount); - if (!Res) + auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction( + I, NumVals, TotalCount, NumCandidates); + if (!NumCandidates) continue; - ArrayRef ValueDataArrayRef(ValueDataArray.get(), - NumVals); - auto PromotionCandidates = - getPromotionCandidatesForCallSite(I, ValueDataArrayRef, TotalCount); + auto PromotionCandidates = getPromotionCandidatesForCallSite( + I, ICallProfDataRef, TotalCount, NumCandidates); uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount); if (NumPromoted == 0) continue; @@ -656,8 +616,8 @@ bool ICallPromotionFunc::processFunction() { if (TotalCount == 0 || NumPromoted == NumVals) continue; // Otherwise we need update with the un-promoted records back. - annotateValueSite(*M, *I, ValueDataArrayRef.slice(NumPromoted), TotalCount, - IPVK_IndirectCallTarget, MaxNumPromotions); + annotateValueSite(*M, *I, ICallProfDataRef.slice(NumPromoted), TotalCount, + IPVK_IndirectCallTarget, NumCandidates); } return Changed; } diff --git a/lib/Transforms/Instrumentation/PGOInstrumentation.cpp b/lib/Transforms/Instrumentation/PGOInstrumentation.cpp index 27f32b3de56..f54d8ad4814 100644 --- a/lib/Transforms/Instrumentation/PGOInstrumentation.cpp +++ b/lib/Transforms/Instrumentation/PGOInstrumentation.cpp @@ -50,13 +50,13 @@ #include "llvm/Transforms/PGOInstrumentation.h" #include "CFGMST.h" -#include "IndirectCallSiteVisitor.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Triple.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/IndirectCallSiteVisitor.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/IRBuilder.h" -- 2.11.0