Index: include/llvm/Analysis/IndirectCallPromotionAnalysis.h =================================================================== --- /dev/null +++ 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 Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -28,6 +28,7 @@ EHPersonalities.cpp GlobalsModRef.cpp IVUsers.cpp + IndirectCallPromotionAnalysis.cpp InlineCost.cpp InstCount.cpp InstructionSimplify.cpp Index: lib/Analysis/IndirectCallPromotionAnalysis.cpp =================================================================== --- /dev/null +++ lib/Analysis/IndirectCallPromotionAnalysis.cpp @@ -0,0 +1,132 @@ +//===-- 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")); + +// If the option is set to true, only call instructions will be considered for +// transformation -- invoke instructions will be ignored. +static cl::opt + ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden, + cl::desc("Run indirect-call promotion for call instructions " + "only")); + +// If the option is set to true, only invoke instructions will be considered for +// transformation -- call instructions will be ignored. +static cl::opt ICPInvokeOnly("icp-invoke-only", cl::init(false), + cl::Hidden, + cl::desc("Run indirect-call promotion for " + "invoke instruction only")); + +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 (ICPInvokeOnly && dyn_cast(Inst)) { + DEBUG(dbgs() << " Not promote: User options.\n"); + return I; + } + if (ICPCallOnly && dyn_cast(Inst)) { + DEBUG(dbgs() << " Not promote: User option.\n"); + return I; + } + 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); +} Index: lib/Transforms/Instrumentation/IndirectCallPromotion.cpp =================================================================== --- lib/Transforms/Instrumentation/IndirectCallPromotion.cpp +++ 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 @@ 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,19 +70,6 @@ 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 - ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden, - cl::desc("Run indirect-call promotion for call instructions " - "only")); - -// If the option is set to true, only invoke instructions will be considered for -// transformation -- call instructions will be ignored. -static cl::opt ICPInvokeOnly("icp-invoke-only", cl::init(false), - cl::Hidden, - cl::desc("Run indirect-call promotion for " - "invoke instruction only")); // Dump the function level IR if the transformation happened in this // function. For debug use only. @@ -157,14 +123,6 @@ // 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. @@ -188,7 +146,7 @@ // of promotions. 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 +190,11 @@ 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,41 +239,30 @@ 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; DEBUG(dbgs() << " Candidate " << I << " Count=" << Count << " Target_func: " << Target << "\n"); - if (ICPInvokeOnly && dyn_cast(Inst)) { - DEBUG(dbgs() << " Not promote: User options.\n"); - break; - } - if (ICPCallOnly && dyn_cast(Inst)) { - DEBUG(dbgs() << " Not promote: User option.\n"); - break; - } if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) { 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 +570,16 @@ // 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 +591,8 @@ 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, NumPromoted); } return Changed; } Index: lib/Transforms/Instrumentation/IndirectCallSiteVisitor.h =================================================================== --- /dev/null +++ lib/Transforms/Instrumentation/IndirectCallSiteVisitor.h @@ -1,43 +0,0 @@ -//===-- IndirectCallSiteVisitor.h - indirect call-sites visitor -----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements defines a visitor class and a helper function that find -// all indirect call-sites in a function. - -#include "llvm/IR/InstVisitor.h" -#include - -namespace llvm { -// Visitor class that finds all indirect call sites. -struct PGOIndirectCallSiteVisitor - : public InstVisitor { - std::vector IndirectCallInsts; - PGOIndirectCallSiteVisitor() {} - - void visitCallSite(CallSite CS) { - if (CS.getCalledFunction() || !CS.getCalledValue()) - return; - Instruction *I = CS.getInstruction(); - if (CallInst *CI = dyn_cast(I)) { - if (CI->isInlineAsm()) - return; - } - if (isa(CS.getCalledValue())) - return; - IndirectCallInsts.push_back(I); - } -}; - -// Helper function that finds all indirect call sites. -static inline std::vector findIndirectCallSites(Function &F) { - PGOIndirectCallSiteVisitor ICV; - ICV.visit(F); - return ICV.IndirectCallInsts; -} -} Index: lib/Transforms/Instrumentation/PGOInstrumentation.cpp =================================================================== --- lib/Transforms/Instrumentation/PGOInstrumentation.cpp +++ 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"