#include "llvm/ProfileData/SampleProfReader.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Utils/Cloning.h"
#include <cctype>
using namespace llvm;
"sample-profile-max-propagate-iterations", cl::init(100),
cl::desc("Maximum number of iterations to go through when propagating "
"sample block/edge weights through the CFG."));
+static cl::opt<unsigned> SampleProfileRecordCoverage(
+ "sample-profile-check-record-coverage", cl::init(0), cl::value_desc("N"),
+ cl::desc("Emit a warning if less than N% of records in the input profile "
+ "are matched to the IR."));
+static cl::opt<unsigned> SampleProfileSampleCoverage(
+ "sample-profile-check-sample-coverage", cl::init(0), cl::value_desc("N"),
+ cl::desc("Emit a warning if less than N% of samples in the input profile "
+ "are matched to the IR."));
+static cl::opt<double> SampleProfileHotThreshold(
+ "sample-profile-inline-hot-threshold", cl::init(0.1), cl::value_desc("N"),
+ cl::desc("Inlined functions that account for more than N% of all samples "
+ "collected in the parent function, will be inlined again."));
+static cl::opt<double> SampleProfileGlobalHotThreshold(
+ "sample-profile-global-hot-threshold", cl::init(30), cl::value_desc("N"),
+ cl::desc("Top-level functions that account for more than N% of all samples "
+ "collected in the profile, will be marked as hot for the inliner "
+ "to consider."));
+static cl::opt<double> SampleProfileGlobalColdThreshold(
+ "sample-profile-global-cold-threshold", cl::init(0.5), cl::value_desc("N"),
+ cl::desc("Top-level functions that account for less than N% of all samples "
+ "collected in the profile, will be marked as cold for the inliner "
+ "to consider."));
namespace {
-typedef DenseMap<BasicBlock *, unsigned> BlockWeightMap;
-typedef DenseMap<BasicBlock *, BasicBlock *> EquivalenceClassMap;
-typedef std::pair<BasicBlock *, BasicBlock *> Edge;
-typedef DenseMap<Edge, unsigned> EdgeWeightMap;
-typedef DenseMap<BasicBlock *, SmallVector<BasicBlock *, 8>> BlockEdgeMap;
+typedef DenseMap<const BasicBlock *, uint64_t> BlockWeightMap;
+typedef DenseMap<const BasicBlock *, const BasicBlock *> EquivalenceClassMap;
+typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
+typedef DenseMap<Edge, uint64_t> EdgeWeightMap;
+typedef DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>
+ BlockEdgeMap;
/// \brief Sample profile pass.
///
static char ID;
SampleProfileLoader(StringRef Name = SampleProfileFile)
- : ModulePass(ID), DT(nullptr), PDT(nullptr), LI(nullptr),
- Ctx(nullptr), Reader(), Samples(nullptr), Filename(Name),
- ProfileIsValid(false) {
+ : ModulePass(ID), DT(nullptr), PDT(nullptr), LI(nullptr), Reader(),
+ Samples(nullptr), Filename(Name), ProfileIsValid(false),
+ TotalCollectedSamples(0) {
initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
-
- AU.addRequired<LoopInfoWrapperPass>();
- AU.addPreserved<LoopInfoWrapperPass>();
-
- AU.addRequired<DominatorTreeWrapperPass>();
- AU.addPreserved<DominatorTreeWrapperPass>();
-
- AU.addRequired<PostDominatorTree>();
- AU.addPreserved<PostDominatorTree>();
}
protected:
bool runOnFunction(Function &F);
unsigned getFunctionLoc(Function &F);
bool emitAnnotations(Function &F);
- unsigned getInstWeight(Instruction &I);
- unsigned getBlockWeight(BasicBlock *BB);
+ ErrorOr<uint64_t> getInstWeight(const Instruction &I) const;
+ ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB) const;
+ const FunctionSamples *findCalleeFunctionSamples(const CallInst &I) const;
+ const FunctionSamples *findFunctionSamples(const Instruction &I) const;
+ bool inlineHotFunctions(Function &F);
+ bool emitInlineHints(Function &F);
void printEdgeWeight(raw_ostream &OS, Edge E);
- void printBlockWeight(raw_ostream &OS, BasicBlock *BB);
- void printBlockEquivalence(raw_ostream &OS, BasicBlock *BB);
+ void printBlockWeight(raw_ostream &OS, const BasicBlock *BB) const;
+ void printBlockEquivalence(raw_ostream &OS, const BasicBlock *BB);
bool computeBlockWeights(Function &F);
void findEquivalenceClasses(Function &F);
void findEquivalencesFor(BasicBlock *BB1,
SmallVector<BasicBlock *, 8> Descendants,
DominatorTreeBase<BasicBlock> *DomTree);
void propagateWeights(Function &F);
- unsigned visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
+ uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
void buildEdges(Function &F);
bool propagateThroughEdges(Function &F);
-
- /// \brief Line number for the function header. Used to compute absolute
- /// line numbers from the relative line numbers found in the profile.
- unsigned HeaderLineno;
+ void computeDominanceAndLoopInfo(Function &F);
+ unsigned getOffset(unsigned L, unsigned H) const;
+ void clearFunctionData();
/// \brief Map basic blocks to their computed weights.
///
EdgeWeightMap EdgeWeights;
/// \brief Set of visited blocks during propagation.
- SmallPtrSet<BasicBlock *, 128> VisitedBlocks;
+ SmallPtrSet<const BasicBlock *, 128> VisitedBlocks;
/// \brief Set of visited edges during propagation.
SmallSet<Edge, 128> VisitedEdges;
EquivalenceClassMap EquivalenceClass;
/// \brief Dominance, post-dominance and loop information.
- DominatorTree *DT;
- PostDominatorTree *PDT;
- LoopInfo *LI;
+ std::unique_ptr<DominatorTree> DT;
+ std::unique_ptr<DominatorTreeBase<BasicBlock>> PDT;
+ std::unique_ptr<LoopInfo> LI;
/// \brief Predecessors for each basic block in the CFG.
BlockEdgeMap Predecessors;
/// \brief Successors for each basic block in the CFG.
BlockEdgeMap Successors;
- /// \brief LLVM context holding the debug data we need.
- LLVMContext *Ctx;
-
/// \brief Profile reader object.
std::unique_ptr<SampleProfileReader> Reader;
/// \brief Flag indicating whether the profile input loaded successfully.
bool ProfileIsValid;
+
+ /// \brief Total number of samples collected in this profile.
+ ///
+ /// This is the sum of all the samples collected in all the functions executed
+ /// at runtime.
+ uint64_t TotalCollectedSamples;
+};
+
+class SampleCoverageTracker {
+public:
+ SampleCoverageTracker() : SampleCoverage(), TotalUsedSamples(0) {}
+
+ bool markSamplesUsed(const FunctionSamples *FS, uint32_t LineOffset,
+ uint32_t Discriminator, uint64_t Samples);
+ unsigned computeCoverage(unsigned Used, unsigned Total) const;
+ unsigned countUsedRecords(const FunctionSamples *FS) const;
+ unsigned countBodyRecords(const FunctionSamples *FS) const;
+ uint64_t getTotalUsedSamples() const { return TotalUsedSamples; }
+ uint64_t countBodySamples(const FunctionSamples *FS) const;
+ void clear() {
+ SampleCoverage.clear();
+ TotalUsedSamples = 0;
+ }
+
+private:
+ typedef std::map<LineLocation, unsigned> BodySampleCoverageMap;
+ typedef DenseMap<const FunctionSamples *, BodySampleCoverageMap>
+ FunctionSamplesCoverageMap;
+
+ /// Coverage map for sampling records.
+ ///
+ /// This map keeps a record of sampling records that have been matched to
+ /// an IR instruction. This is used to detect some form of staleness in
+ /// profiles (see flag -sample-profile-check-coverage).
+ ///
+ /// Each entry in the map corresponds to a FunctionSamples instance. This is
+ /// another map that counts how many times the sample record at the
+ /// given location has been used.
+ FunctionSamplesCoverageMap SampleCoverage;
+
+ /// Number of samples used from the profile.
+ ///
+ /// When a sampling record is used for the first time, the samples from
+ /// that record are added to this accumulator. Coverage is later computed
+ /// based on the total number of samples available in this function and
+ /// its callsites.
+ ///
+ /// Note that this accumulator tracks samples used from a single function
+ /// and all the inlined callsites. Strictly, we should have a map of counters
+ /// keyed by FunctionSamples pointers, but these stats are cleared after
+ /// every function, so we just need to keep a single counter.
+ uint64_t TotalUsedSamples;
};
+
+SampleCoverageTracker CoverageTracker;
+
+/// Return true if the given callsite is hot wrt to its caller.
+///
+/// Functions that were inlined in the original binary will be represented
+/// in the inline stack in the sample profile. If the profile shows that
+/// the original inline decision was "good" (i.e., the callsite is executed
+/// frequently), then we will recreate the inline decision and apply the
+/// profile from the inlined callsite.
+///
+/// To decide whether an inlined callsite is hot, we compute the fraction
+/// of samples used by the callsite with respect to the total number of samples
+/// collected in the caller.
+///
+/// If that fraction is larger than the default given by
+/// SampleProfileHotThreshold, the callsite will be inlined again.
+bool callsiteIsHot(const FunctionSamples *CallerFS,
+ const FunctionSamples *CallsiteFS) {
+ if (!CallsiteFS)
+ return false; // The callsite was not inlined in the original binary.
+
+ uint64_t ParentTotalSamples = CallerFS->getTotalSamples();
+ if (ParentTotalSamples == 0)
+ return false; // Avoid division by zero.
+
+ uint64_t CallsiteTotalSamples = CallsiteFS->getTotalSamples();
+ if (CallsiteTotalSamples == 0)
+ return false; // Callsite is trivially cold.
+
+ double PercentSamples =
+ (double)CallsiteTotalSamples / (double)ParentTotalSamples * 100.0;
+ return PercentSamples >= SampleProfileHotThreshold;
+}
+
+}
+
+/// Mark as used the sample record for the given function samples at
+/// (LineOffset, Discriminator).
+///
+/// \returns true if this is the first time we mark the given record.
+bool SampleCoverageTracker::markSamplesUsed(const FunctionSamples *FS,
+ uint32_t LineOffset,
+ uint32_t Discriminator,
+ uint64_t Samples) {
+ LineLocation Loc(LineOffset, Discriminator);
+ unsigned &Count = SampleCoverage[FS][Loc];
+ bool FirstTime = (++Count == 1);
+ if (FirstTime)
+ TotalUsedSamples += Samples;
+ return FirstTime;
+}
+
+/// Return the number of sample records that were applied from this profile.
+///
+/// This count does not include records from cold inlined callsites.
+unsigned
+SampleCoverageTracker::countUsedRecords(const FunctionSamples *FS) const {
+ auto I = SampleCoverage.find(FS);
+
+ // The size of the coverage map for FS represents the number of records
+ // that were marked used at least once.
+ unsigned Count = (I != SampleCoverage.end()) ? I->second.size() : 0;
+
+ // If there are inlined callsites in this function, count the samples found
+ // in the respective bodies. However, do not bother counting callees with 0
+ // total samples, these are callees that were never invoked at runtime.
+ for (const auto &I : FS->getCallsiteSamples()) {
+ const FunctionSamples *CalleeSamples = &I.second;
+ if (callsiteIsHot(FS, CalleeSamples))
+ Count += countUsedRecords(CalleeSamples);
+ }
+
+ return Count;
+}
+
+/// Return the number of sample records in the body of this profile.
+///
+/// This count does not include records from cold inlined callsites.
+unsigned
+SampleCoverageTracker::countBodyRecords(const FunctionSamples *FS) const {
+ unsigned Count = FS->getBodySamples().size();
+
+ // Only count records in hot callsites.
+ for (const auto &I : FS->getCallsiteSamples()) {
+ const FunctionSamples *CalleeSamples = &I.second;
+ if (callsiteIsHot(FS, CalleeSamples))
+ Count += countBodyRecords(CalleeSamples);
+ }
+
+ return Count;
+}
+
+/// Return the number of samples collected in the body of this profile.
+///
+/// This count does not include samples from cold inlined callsites.
+uint64_t
+SampleCoverageTracker::countBodySamples(const FunctionSamples *FS) const {
+ uint64_t Total = 0;
+ for (const auto &I : FS->getBodySamples())
+ Total += I.second.getSamples();
+
+ // Only count samples in hot callsites.
+ for (const auto &I : FS->getCallsiteSamples()) {
+ const FunctionSamples *CalleeSamples = &I.second;
+ if (callsiteIsHot(FS, CalleeSamples))
+ Total += countBodySamples(CalleeSamples);
+ }
+
+ return Total;
+}
+
+/// Return the fraction of sample records used in this profile.
+///
+/// The returned value is an unsigned integer in the range 0-100 indicating
+/// the percentage of sample records that were used while applying this
+/// profile to the associated function.
+unsigned SampleCoverageTracker::computeCoverage(unsigned Used,
+ unsigned Total) const {
+ assert(Used <= Total &&
+ "number of used records cannot exceed the total number of records");
+ return Total > 0 ? Used * 100 / Total : 100;
+}
+
+/// Clear all the per-function data used to load samples and propagate weights.
+void SampleProfileLoader::clearFunctionData() {
+ BlockWeights.clear();
+ EdgeWeights.clear();
+ VisitedBlocks.clear();
+ VisitedEdges.clear();
+ EquivalenceClass.clear();
+ DT = nullptr;
+ PDT = nullptr;
+ LI = nullptr;
+ Predecessors.clear();
+ Successors.clear();
+ CoverageTracker.clear();
+}
+
+/// \brief Returns the offset of lineno \p L to head_lineno \p H
+///
+/// \param L Lineno
+/// \param H Header lineno of the function
+///
+/// \returns offset to the header lineno. 16 bits are used to represent offset.
+/// We assume that a single function will not exceed 65535 LOC.
+unsigned SampleProfileLoader::getOffset(unsigned L, unsigned H) const {
+ return (L - H) & 0xffff;
}
/// \brief Print the weight of edge \p E on stream \p OS.
/// \param OS Stream to emit the output to.
/// \param BB Block to print.
void SampleProfileLoader::printBlockEquivalence(raw_ostream &OS,
- BasicBlock *BB) {
- BasicBlock *Equiv = EquivalenceClass[BB];
+ const BasicBlock *BB) {
+ const BasicBlock *Equiv = EquivalenceClass[BB];
OS << "equivalence[" << BB->getName()
<< "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n";
}
///
/// \param OS Stream to emit the output to.
/// \param BB Block to print.
-void SampleProfileLoader::printBlockWeight(raw_ostream &OS, BasicBlock *BB) {
- OS << "weight[" << BB->getName() << "]: " << BlockWeights[BB] << "\n";
+void SampleProfileLoader::printBlockWeight(raw_ostream &OS,
+ const BasicBlock *BB) const {
+ const auto &I = BlockWeights.find(BB);
+ uint64_t W = (I == BlockWeights.end() ? 0 : I->second);
+ OS << "weight[" << BB->getName() << "]: " << W << "\n";
}
/// \brief Get the weight for an instruction.
///
/// \param Inst Instruction to query.
///
-/// \returns The profiled weight of I.
-unsigned SampleProfileLoader::getInstWeight(Instruction &Inst) {
+/// \returns the weight of \p Inst.
+ErrorOr<uint64_t>
+SampleProfileLoader::getInstWeight(const Instruction &Inst) const {
DebugLoc DLoc = Inst.getDebugLoc();
if (!DLoc)
- return 0;
+ return std::error_code();
- unsigned Lineno = DLoc.getLine();
- if (Lineno < HeaderLineno)
- return 0;
+ const FunctionSamples *FS = findFunctionSamples(Inst);
+ if (!FS)
+ return std::error_code();
const DILocation *DIL = DLoc;
- int LOffset = Lineno - HeaderLineno;
- unsigned Discriminator = DIL->getDiscriminator();
- unsigned Weight = Samples->samplesAt(LOffset, Discriminator);
- DEBUG(dbgs() << " " << Lineno << "." << Discriminator << ":" << Inst
- << " (line offset: " << LOffset << "." << Discriminator
- << " - weight: " << Weight << ")\n");
- return Weight;
+ unsigned Lineno = DLoc.getLine();
+ unsigned HeaderLineno = DIL->getScope()->getSubprogram()->getLine();
+
+ uint32_t LineOffset = getOffset(Lineno, HeaderLineno);
+ uint32_t Discriminator = DIL->getDiscriminator();
+ ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator);
+ if (R) {
+ bool FirstMark =
+ CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
+ if (FirstMark) {
+ const Function *F = Inst.getParent()->getParent();
+ LLVMContext &Ctx = F->getContext();
+ emitOptimizationRemark(
+ Ctx, DEBUG_TYPE, *F, DLoc,
+ Twine("Applied ") + Twine(*R) + " samples from profile (offset: " +
+ Twine(LineOffset) +
+ ((Discriminator) ? Twine(".") + Twine(Discriminator) : "") + ")");
+ }
+ DEBUG(dbgs() << " " << Lineno << "." << DIL->getDiscriminator() << ":"
+ << Inst << " (line offset: " << Lineno - HeaderLineno << "."
+ << DIL->getDiscriminator() << " - weight: " << R.get()
+ << ")\n");
+ }
+ return R;
}
/// \brief Compute the weight of a basic block.
///
/// The weight of basic block \p BB is the maximum weight of all the
-/// instructions in BB. The weight of \p BB is computed and cached in
-/// the BlockWeights map.
+/// instructions in BB.
///
/// \param BB The basic block to query.
///
-/// \returns The computed weight of BB.
-unsigned SampleProfileLoader::getBlockWeight(BasicBlock *BB) {
- // If we've computed BB's weight before, return it.
- std::pair<BlockWeightMap::iterator, bool> Entry =
- BlockWeights.insert(std::make_pair(BB, 0));
- if (!Entry.second)
- return Entry.first->second;
-
- // Otherwise, compute and cache BB's weight.
- unsigned Weight = 0;
+/// \returns the weight for \p BB.
+ErrorOr<uint64_t>
+SampleProfileLoader::getBlockWeight(const BasicBlock *BB) const {
+ bool Found = false;
+ uint64_t Weight = 0;
for (auto &I : BB->getInstList()) {
- unsigned InstWeight = getInstWeight(I);
- if (InstWeight > Weight)
- Weight = InstWeight;
+ const ErrorOr<uint64_t> &R = getInstWeight(I);
+ if (R && R.get() >= Weight) {
+ Weight = R.get();
+ Found = true;
+ }
}
- Entry.first->second = Weight;
- return Weight;
+ if (Found)
+ return Weight;
+ else
+ return std::error_code();
}
/// \brief Compute and store the weights of every basic block.
bool SampleProfileLoader::computeBlockWeights(Function &F) {
bool Changed = false;
DEBUG(dbgs() << "Block weights\n");
- for (auto &BB : F) {
- unsigned Weight = getBlockWeight(&BB);
- Changed |= (Weight > 0);
+ for (const auto &BB : F) {
+ ErrorOr<uint64_t> Weight = getBlockWeight(&BB);
+ if (Weight) {
+ BlockWeights[&BB] = Weight.get();
+ VisitedBlocks.insert(&BB);
+ Changed = true;
+ }
DEBUG(printBlockWeight(dbgs(), &BB));
}
return Changed;
}
+/// \brief Get the FunctionSamples for a call instruction.
+///
+/// The FunctionSamples of a call instruction \p Inst is the inlined
+/// instance in which that call instruction is calling to. It contains
+/// all samples that resides in the inlined instance. We first find the
+/// inlined instance in which the call instruction is from, then we
+/// traverse its children to find the callsite with the matching
+/// location and callee function name.
+///
+/// \param Inst Call instruction to query.
+///
+/// \returns The FunctionSamples pointer to the inlined instance.
+const FunctionSamples *
+SampleProfileLoader::findCalleeFunctionSamples(const CallInst &Inst) const {
+ const DILocation *DIL = Inst.getDebugLoc();
+ if (!DIL) {
+ return nullptr;
+ }
+ DISubprogram *SP = DIL->getScope()->getSubprogram();
+ if (!SP)
+ return nullptr;
+
+ Function *CalleeFunc = Inst.getCalledFunction();
+ if (!CalleeFunc) {
+ return nullptr;
+ }
+
+ StringRef CalleeName = CalleeFunc->getName();
+ const FunctionSamples *FS = findFunctionSamples(Inst);
+ if (FS == nullptr)
+ return nullptr;
+
+ return FS->findFunctionSamplesAt(
+ CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
+ DIL->getDiscriminator(), CalleeName));
+}
+
+/// \brief Get the FunctionSamples for an instruction.
+///
+/// The FunctionSamples of an instruction \p Inst is the inlined instance
+/// in which that instruction is coming from. We traverse the inline stack
+/// of that instruction, and match it with the tree nodes in the profile.
+///
+/// \param Inst Instruction to query.
+///
+/// \returns the FunctionSamples pointer to the inlined instance.
+const FunctionSamples *
+SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {
+ SmallVector<CallsiteLocation, 10> S;
+ const DILocation *DIL = Inst.getDebugLoc();
+ if (!DIL) {
+ return Samples;
+ }
+ StringRef CalleeName;
+ for (const DILocation *DIL = Inst.getDebugLoc(); DIL;
+ DIL = DIL->getInlinedAt()) {
+ DISubprogram *SP = DIL->getScope()->getSubprogram();
+ if (!SP)
+ return nullptr;
+ if (!CalleeName.empty()) {
+ S.push_back(CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
+ DIL->getDiscriminator(), CalleeName));
+ }
+ CalleeName = SP->getLinkageName();
+ }
+ if (S.size() == 0)
+ return Samples;
+ const FunctionSamples *FS = Samples;
+ for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
+ FS = FS->findFunctionSamplesAt(S[i]);
+ }
+ return FS;
+}
+
+/// \brief Emit an inline hint if \p F is globally hot or cold.
+///
+/// If \p F consumes a significant fraction of samples (indicated by
+/// SampleProfileGlobalHotThreshold), apply the InlineHint attribute for the
+/// inliner to consider the function hot.
+///
+/// If \p F consumes a small fraction of samples (indicated by
+/// SampleProfileGlobalColdThreshold), apply the Cold attribute for the inliner
+/// to consider the function cold.
+///
+/// FIXME - This setting of inline hints is sub-optimal. Instead of marking a
+/// function globally hot or cold, we should be annotating individual callsites.
+/// This is not currently possible, but work on the inliner will eventually
+/// provide this ability. See http://reviews.llvm.org/D15003 for details and
+/// discussion.
+///
+/// \returns True if either attribute was applied to \p F.
+bool SampleProfileLoader::emitInlineHints(Function &F) {
+ if (TotalCollectedSamples == 0)
+ return false;
+
+ uint64_t FunctionSamples = Samples->getTotalSamples();
+ double SamplesPercent =
+ (double)FunctionSamples / (double)TotalCollectedSamples * 100.0;
+
+ // If the function collected more samples than the hot threshold, mark
+ // it globally hot.
+ if (SamplesPercent >= SampleProfileGlobalHotThreshold) {
+ F.addFnAttr(llvm::Attribute::InlineHint);
+ std::string Msg;
+ raw_string_ostream S(Msg);
+ S << "Applied inline hint to globally hot function '" << F.getName()
+ << "' with " << format("%.2f", SamplesPercent)
+ << "% of samples (threshold: "
+ << format("%.2f", SampleProfileGlobalHotThreshold.getValue()) << "%)";
+ S.flush();
+ emitOptimizationRemark(F.getContext(), DEBUG_TYPE, F, DebugLoc(), Msg);
+ return true;
+ }
+
+ // If the function collected fewer samples than the cold threshold, mark
+ // it globally cold.
+ if (SamplesPercent <= SampleProfileGlobalColdThreshold) {
+ F.addFnAttr(llvm::Attribute::Cold);
+ std::string Msg;
+ raw_string_ostream S(Msg);
+ S << "Applied cold hint to globally cold function '" << F.getName()
+ << "' with " << format("%.2f", SamplesPercent)
+ << "% of samples (threshold: "
+ << format("%.2f", SampleProfileGlobalColdThreshold.getValue()) << "%)";
+ S.flush();
+ emitOptimizationRemark(F.getContext(), DEBUG_TYPE, F, DebugLoc(), Msg);
+ return true;
+ }
+
+ return false;
+}
+
+/// \brief Iteratively inline hot callsites of a function.
+///
+/// Iteratively traverse all callsites of the function \p F, and find if
+/// the corresponding inlined instance exists and is hot in profile. If
+/// it is hot enough, inline the callsites and adds new callsites of the
+/// callee into the caller.
+///
+/// TODO: investigate the possibility of not invoking InlineFunction directly.
+///
+/// \param F function to perform iterative inlining.
+///
+/// \returns True if there is any inline happened.
+bool SampleProfileLoader::inlineHotFunctions(Function &F) {
+ bool Changed = false;
+ LLVMContext &Ctx = F.getContext();
+ while (true) {
+ bool LocalChanged = false;
+ SmallVector<CallInst *, 10> CIS;
+ for (auto &BB : F) {
+ for (auto &I : BB.getInstList()) {
+ CallInst *CI = dyn_cast<CallInst>(&I);
+ if (CI && callsiteIsHot(Samples, findCalleeFunctionSamples(*CI)))
+ CIS.push_back(CI);
+ }
+ }
+ for (auto CI : CIS) {
+ InlineFunctionInfo IFI;
+ Function *CalledFunction = CI->getCalledFunction();
+ DebugLoc DLoc = CI->getDebugLoc();
+ uint64_t NumSamples = findCalleeFunctionSamples(*CI)->getTotalSamples();
+ if (InlineFunction(CI, IFI)) {
+ LocalChanged = true;
+ emitOptimizationRemark(Ctx, DEBUG_TYPE, F, DLoc,
+ Twine("inlined hot callee '") +
+ CalledFunction->getName() + "' with " +
+ Twine(NumSamples) + " samples into '" +
+ F.getName() + "'");
+ }
+ }
+ if (LocalChanged) {
+ Changed = true;
+ } else {
+ break;
+ }
+ }
+ return Changed;
+}
+
/// \brief Find equivalence classes for the given block.
///
/// This finds all the blocks that are guaranteed to execute the same
void SampleProfileLoader::findEquivalencesFor(
BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants,
DominatorTreeBase<BasicBlock> *DomTree) {
- for (auto *BB2 : Descendants) {
+ const BasicBlock *EC = EquivalenceClass[BB1];
+ uint64_t Weight = BlockWeights[EC];
+ for (const auto *BB2 : Descendants) {
bool IsDomParent = DomTree->dominates(BB2, BB1);
bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
- if (BB1 != BB2 && VisitedBlocks.insert(BB2).second && IsDomParent &&
- IsInSameLoop) {
- EquivalenceClass[BB2] = BB1;
+ if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
+ EquivalenceClass[BB2] = EC;
// If BB2 is heavier than BB1, make BB2 have the same weight
// as BB1.
// during the propagation phase. Right now, we just want to
// make sure that BB1 has the largest weight of all the
// members of its equivalence set.
- unsigned &BB1Weight = BlockWeights[BB1];
- unsigned &BB2Weight = BlockWeights[BB2];
- BB1Weight = std::max(BB1Weight, BB2Weight);
+ Weight = std::max(Weight, BlockWeights[BB2]);
}
}
+ BlockWeights[EC] = Weight;
}
/// \brief Find equivalence classes.
// class by making BB2's equivalence class be BB1.
DominatedBBs.clear();
DT->getDescendants(BB1, DominatedBBs);
- findEquivalencesFor(BB1, DominatedBBs, PDT->DT);
-
- // Repeat the same logic for all the blocks post-dominated by BB1.
- // We are looking for every basic block BB2 such that:
- //
- // 1- BB1 post-dominates BB2.
- // 2- BB2 dominates BB1.
- // 3- BB1 and BB2 are in the same loop nest.
- //
- // If all those conditions hold, BB2's equivalence class is BB1.
- DominatedBBs.clear();
- PDT->getDescendants(BB1, DominatedBBs);
- findEquivalencesFor(BB1, DominatedBBs, DT);
+ findEquivalencesFor(BB1, DominatedBBs, PDT.get());
DEBUG(printBlockEquivalence(dbgs(), BB1));
}
// to all the blocks in that equivalence class.
DEBUG(dbgs() << "\nAssign the same weight to all blocks in the same class\n");
for (auto &BI : F) {
- BasicBlock *BB = &BI;
- BasicBlock *EquivBB = EquivalenceClass[BB];
+ const BasicBlock *BB = &BI;
+ const BasicBlock *EquivBB = EquivalenceClass[BB];
if (BB != EquivBB)
BlockWeights[BB] = BlockWeights[EquivBB];
DEBUG(printBlockWeight(dbgs(), BB));
/// \param UnknownEdge Set if E has not been visited before.
///
/// \returns E's weight, if known. Otherwise, return 0.
-unsigned SampleProfileLoader::visitEdge(Edge E, unsigned *NumUnknownEdges,
+uint64_t SampleProfileLoader::visitEdge(Edge E, unsigned *NumUnknownEdges,
Edge *UnknownEdge) {
if (!VisitedEdges.count(E)) {
(*NumUnknownEdges)++;
bool SampleProfileLoader::propagateThroughEdges(Function &F) {
bool Changed = false;
DEBUG(dbgs() << "\nPropagation through edges\n");
- for (auto &BI : F) {
- BasicBlock *BB = &BI;
+ for (const auto &BI : F) {
+ const BasicBlock *BB = &BI;
+ const BasicBlock *EC = EquivalenceClass[BB];
// Visit all the predecessor and successor edges to determine
// which ones have a weight assigned already. Note that it doesn't
// only case we are interested in handling is when only a single
// edge is unknown (see setEdgeOrBlockWeight).
for (unsigned i = 0; i < 2; i++) {
- unsigned TotalWeight = 0;
+ uint64_t TotalWeight = 0;
unsigned NumUnknownEdges = 0;
Edge UnknownEdge, SelfReferentialEdge;
// all edges will get a weight, or iteration will stop when
// it reaches SampleProfileMaxPropagateIterations.
if (NumUnknownEdges <= 1) {
- unsigned &BBWeight = BlockWeights[BB];
+ uint64_t &BBWeight = BlockWeights[EC];
if (NumUnknownEdges == 0) {
// If we already know the weight of all edges, the weight of the
// basic block can be computed. It should be no larger than the sum
<< " known. Set weight for block: ";
printBlockWeight(dbgs(), BB););
}
- if (VisitedBlocks.insert(BB).second)
+ if (VisitedBlocks.insert(EC).second)
Changed = true;
- } else if (NumUnknownEdges == 1 && VisitedBlocks.count(BB)) {
+ } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
// If there is a single unknown edge and the block has been
// visited, then we can compute E's weight.
if (BBWeight >= TotalWeight)
DEBUG(dbgs() << "Set weight for edge: ";
printEdgeWeight(dbgs(), UnknownEdge));
}
- } else if (SelfReferentialEdge.first && VisitedBlocks.count(BB)) {
- unsigned &BBWeight = BlockWeights[BB];
+ } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
+ uint64_t &BBWeight = BlockWeights[BB];
// We have a self-referential edge and the weight of BB is known.
if (BBWeight >= TotalWeight)
EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
/// known).
void SampleProfileLoader::propagateWeights(Function &F) {
bool Changed = true;
- unsigned i = 0;
+ unsigned I = 0;
// Add an entry count to the function using the samples gathered
// at the function entry.
buildEdges(F);
// Propagate until we converge or we go past the iteration limit.
- while (Changed && i++ < SampleProfileMaxPropagateIterations) {
+ while (Changed && I++ < SampleProfileMaxPropagateIterations) {
Changed = propagateThroughEdges(F);
}
// Generate MD_prof metadata for every branch instruction using the
// edge weights computed during propagation.
DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
- MDBuilder MDB(F.getContext());
+ LLVMContext &Ctx = F.getContext();
+ MDBuilder MDB(Ctx);
for (auto &BI : F) {
BasicBlock *BB = &BI;
TerminatorInst *TI = BB->getTerminator();
DEBUG(dbgs() << "\nGetting weights for branch at line "
<< TI->getDebugLoc().getLine() << ".\n");
- SmallVector<unsigned, 4> Weights;
- bool AllWeightsZero = true;
+ SmallVector<uint32_t, 4> Weights;
+ uint32_t MaxWeight = 0;
+ DebugLoc MaxDestLoc;
for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
BasicBlock *Succ = TI->getSuccessor(I);
Edge E = std::make_pair(BB, Succ);
- unsigned Weight = EdgeWeights[E];
+ uint64_t Weight = EdgeWeights[E];
DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
- Weights.push_back(Weight);
- if (Weight != 0)
- AllWeightsZero = false;
+ // Use uint32_t saturated arithmetic to adjust the incoming weights,
+ // if needed. Sample counts in profiles are 64-bit unsigned values,
+ // but internally branch weights are expressed as 32-bit values.
+ if (Weight > std::numeric_limits<uint32_t>::max()) {
+ DEBUG(dbgs() << " (saturated due to uint32_t overflow)");
+ Weight = std::numeric_limits<uint32_t>::max();
+ }
+ Weights.push_back(static_cast<uint32_t>(Weight));
+ if (Weight != 0) {
+ if (Weight > MaxWeight) {
+ MaxWeight = Weight;
+ MaxDestLoc = Succ->getFirstNonPHIOrDbgOrLifetime()->getDebugLoc();
+ }
+ }
}
// Only set weights if there is at least one non-zero weight.
// In any other case, let the analyzer set weights.
- if (!AllWeightsZero) {
+ if (MaxWeight > 0) {
DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
TI->setMetadata(llvm::LLVMContext::MD_prof,
MDB.createBranchWeights(Weights));
+ DebugLoc BranchLoc = TI->getDebugLoc();
+ emitOptimizationRemark(
+ Ctx, DEBUG_TYPE, F, MaxDestLoc,
+ Twine("most popular destination for conditional branches at ") +
+ ((BranchLoc) ? Twine(BranchLoc->getFilename() + ":" +
+ Twine(BranchLoc.getLine()) + ":" +
+ Twine(BranchLoc.getCol()))
+ : Twine("<UNKNOWN LOCATION>")));
} else {
DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
}
if (DISubprogram *S = getDISubprogram(&F))
return S->getLine();
- // If could not find the start of \p F, emit a diagnostic to inform the user
+ // If the start of \p F is missing, emit a diagnostic to inform the user
// about the missed opportunity.
F.getContext().diagnose(DiagnosticInfoSampleProfile(
"No debug information found in function " + F.getName() +
return 0;
}
+void SampleProfileLoader::computeDominanceAndLoopInfo(Function &F) {
+ DT.reset(new DominatorTree);
+ DT->recalculate(F);
+
+ PDT.reset(new DominatorTreeBase<BasicBlock>(true));
+ PDT->recalculate(F);
+
+ LI.reset(new LoopInfo);
+ LI->analyze(*DT);
+}
+
/// \brief Generate branch weight metadata for all branches in \p F.
///
/// Branch weights are computed out of instruction samples using a
bool SampleProfileLoader::emitAnnotations(Function &F) {
bool Changed = false;
- // Initialize invariants used during computation and propagation.
- HeaderLineno = getFunctionLoc(F);
- if (HeaderLineno == 0)
+ if (getFunctionLoc(F) == 0)
return false;
DEBUG(dbgs() << "Line number for the first instruction in " << F.getName()
- << ": " << HeaderLineno << "\n");
+ << ": " << getFunctionLoc(F) << "\n");
+
+ Changed |= emitInlineHints(F);
+
+ Changed |= inlineHotFunctions(F);
// Compute basic block weights.
Changed |= computeBlockWeights(F);
if (Changed) {
+ // Compute dominance and loop info needed for propagation.
+ computeDominanceAndLoopInfo(F);
+
// Find equivalence classes.
findEquivalenceClasses(F);
propagateWeights(F);
}
+ // If coverage checking was requested, compute it now.
+ if (SampleProfileRecordCoverage) {
+ unsigned Used = CoverageTracker.countUsedRecords(Samples);
+ unsigned Total = CoverageTracker.countBodyRecords(Samples);
+ unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
+ if (Coverage < SampleProfileRecordCoverage) {
+ F.getContext().diagnose(DiagnosticInfoSampleProfile(
+ getDISubprogram(&F)->getFilename(), getFunctionLoc(F),
+ Twine(Used) + " of " + Twine(Total) + " available profile records (" +
+ Twine(Coverage) + "%) were applied",
+ DS_Warning));
+ }
+ }
+
+ if (SampleProfileSampleCoverage) {
+ uint64_t Used = CoverageTracker.getTotalUsedSamples();
+ uint64_t Total = CoverageTracker.countBodySamples(Samples);
+ unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
+ if (Coverage < SampleProfileSampleCoverage) {
+ F.getContext().diagnose(DiagnosticInfoSampleProfile(
+ getDISubprogram(&F)->getFilename(), getFunctionLoc(F),
+ Twine(Used) + " of " + Twine(Total) + " available profile samples (" +
+ Twine(Coverage) + "%) were applied",
+ DS_Warning));
+ }
+ }
return Changed;
}
char SampleProfileLoader::ID = 0;
INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile",
"Sample Profile loader", false, false)
-INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
-INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AddDiscriminators)
INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile",
"Sample Profile loader", false, false)
bool SampleProfileLoader::doInitialization(Module &M) {
- auto& Ctx = M.getContext();
+ auto &Ctx = M.getContext();
auto ReaderOrErr = SampleProfileReader::create(Filename, Ctx);
if (std::error_code EC = ReaderOrErr.getError()) {
std::string Msg = "Could not open profile: " + EC.message();
- Ctx.diagnose(DiagnosticInfoSampleProfile(Filename.data(), Msg));
+ Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg));
return false;
}
Reader = std::move(ReaderOrErr.get());
}
bool SampleProfileLoader::runOnModule(Module &M) {
+ if (!ProfileIsValid)
+ return false;
+
+ // Compute the total number of samples collected in this profile.
+ for (const auto &I : Reader->getProfiles())
+ TotalCollectedSamples += I.second.getTotalSamples();
+
bool retval = false;
for (auto &F : M)
- if (!F.isDeclaration())
+ if (!F.isDeclaration()) {
+ clearFunctionData();
retval |= runOnFunction(F);
+ }
return retval;
}
bool SampleProfileLoader::runOnFunction(Function &F) {
- if (!ProfileIsValid)
- return false;
-
- DT = &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
- PDT = &getAnalysis<PostDominatorTree>(F);
- LI = &getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
- Ctx = &F.getParent()->getContext();
Samples = Reader->getSamplesFor(F);
if (!Samples->empty())
return emitAnnotations(F);
projects / oota-llvm.git / blobdiff