aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Scalar/SampleProfile.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/SampleProfile.cpp')
-rw-r--r--lib/Transforms/Scalar/SampleProfile.cpp479
1 files changed, 479 insertions, 0 deletions
diff --git a/lib/Transforms/Scalar/SampleProfile.cpp b/lib/Transforms/Scalar/SampleProfile.cpp
new file mode 100644
index 0000000..9bcd702
--- /dev/null
+++ b/lib/Transforms/Scalar/SampleProfile.cpp
@@ -0,0 +1,479 @@
+//===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the SampleProfileLoader transformation. This pass
+// reads a profile file generated by a sampling profiler (e.g. Linux Perf -
+// http://perf.wiki.kernel.org/) and generates IR metadata to reflect the
+// profile information in the given profile.
+//
+// This pass generates branch weight annotations on the IR:
+//
+// - prof: Represents branch weights. This annotation is added to branches
+// to indicate the weights of each edge coming out of the branch.
+// The weight of each edge is the weight of the target block for
+// that edge. The weight of a block B is computed as the maximum
+// number of samples found in B.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "sample-profile"
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/DebugInfo/DIContext.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/Regex.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
+
+using namespace llvm;
+
+// Command line option to specify the file to read samples from. This is
+// mainly used for debugging.
+static cl::opt<std::string> SampleProfileFile(
+ "sample-profile-file", cl::init(""), cl::value_desc("filename"),
+ cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
+
+namespace {
+/// \brief Sample-based profile reader.
+///
+/// Each profile contains sample counts for all the functions
+/// executed. Inside each function, statements are annotated with the
+/// collected samples on all the instructions associated with that
+/// statement.
+///
+/// For this to produce meaningful data, the program needs to be
+/// compiled with some debug information (at minimum, line numbers:
+/// -gline-tables-only). Otherwise, it will be impossible to match IR
+/// instructions to the line numbers collected by the profiler.
+///
+/// From the profile file, we are interested in collecting the
+/// following information:
+///
+/// * A list of functions included in the profile (mangled names).
+///
+/// * For each function F:
+/// 1. The total number of samples collected in F.
+///
+/// 2. The samples collected at each line in F. To provide some
+/// protection against source code shuffling, line numbers should
+/// be relative to the start of the function.
+class SampleProfile {
+public:
+ SampleProfile(StringRef F) : Profiles(0), Filename(F) {}
+
+ void dump();
+ void loadText();
+ void loadNative() { llvm_unreachable("not implemented"); }
+ bool emitAnnotations(Function &F);
+ void printFunctionProfile(raw_ostream &OS, StringRef FName);
+ void dumpFunctionProfile(StringRef FName);
+
+protected:
+ typedef DenseMap<uint32_t, uint32_t> BodySampleMap;
+ typedef DenseMap<BasicBlock *, uint32_t> BlockWeightMap;
+
+ /// \brief Representation of the runtime profile for a function.
+ ///
+ /// This data structure contains the runtime profile for a given
+ /// function. It contains the total number of samples collected
+ /// in the function and a map of samples collected in every statement.
+ struct FunctionProfile {
+ /// \brief Total number of samples collected inside this function.
+ ///
+ /// Samples are cumulative, they include all the samples collected
+ /// inside this function and all its inlined callees.
+ unsigned TotalSamples;
+
+ // \brief Total number of samples collected at the head of the function.
+ unsigned TotalHeadSamples;
+
+ /// \brief Map line offsets to collected samples.
+ ///
+ /// Each entry in this map contains the number of samples
+ /// collected at the corresponding line offset. All line locations
+ /// are an offset from the start of the function.
+ BodySampleMap BodySamples;
+
+ /// \brief Map basic blocks to their computed weights.
+ ///
+ /// The weight of a basic block is defined to be the maximum
+ /// of all the instruction weights in that block.
+ BlockWeightMap BlockWeights;
+ };
+
+ uint32_t getInstWeight(Instruction &I, unsigned FirstLineno,
+ BodySampleMap &BodySamples);
+ uint32_t computeBlockWeight(BasicBlock *B, unsigned FirstLineno,
+ BodySampleMap &BodySamples);
+
+ /// \brief Map every function to its associated profile.
+ ///
+ /// The profile of every function executed at runtime is collected
+ /// in the structure FunctionProfile. This maps function objects
+ /// to their corresponding profiles.
+ StringMap<FunctionProfile> Profiles;
+
+ /// \brief Path name to the file holding the profile data.
+ ///
+ /// The format of this file is defined by each profiler
+ /// independently. If possible, the profiler should have a text
+ /// version of the profile format to be used in constructing test
+ /// cases and debugging.
+ StringRef Filename;
+};
+
+/// \brief Loader class for text-based profiles.
+///
+/// This class defines a simple interface to read text files containing
+/// profiles. It keeps track of line number information and location of
+/// the file pointer. Users of this class are responsible for actually
+/// parsing the lines returned by the readLine function.
+///
+/// TODO - This does not really belong here. It is a generic text file
+/// reader. It should be moved to the Support library and made more general.
+class ExternalProfileTextLoader {
+public:
+ ExternalProfileTextLoader(StringRef F) : Filename(F) {
+ error_code EC;
+ EC = MemoryBuffer::getFile(Filename, Buffer);
+ if (EC)
+ report_fatal_error("Could not open profile file " + Filename + ": " +
+ EC.message());
+ FP = Buffer->getBufferStart();
+ Lineno = 0;
+ }
+
+ /// \brief Read a line from the mapped file.
+ StringRef readLine() {
+ size_t Length = 0;
+ const char *start = FP;
+ while (FP != Buffer->getBufferEnd() && *FP != '\n') {
+ Length++;
+ FP++;
+ }
+ if (FP != Buffer->getBufferEnd())
+ FP++;
+ Lineno++;
+ return StringRef(start, Length);
+ }
+
+ /// \brief Return true, if we've reached EOF.
+ bool atEOF() const { return FP == Buffer->getBufferEnd(); }
+
+ /// \brief Report a parse error message and stop compilation.
+ void reportParseError(Twine Msg) const {
+ report_fatal_error(Filename + ":" + Twine(Lineno) + ": " + Msg + "\n");
+ }
+
+private:
+ /// \brief Memory buffer holding the text file.
+ OwningPtr<MemoryBuffer> Buffer;
+
+ /// \brief Current position into the memory buffer.
+ const char *FP;
+
+ /// \brief Current line number.
+ int64_t Lineno;
+
+ /// \brief Path name where to the profile file.
+ StringRef Filename;
+};
+
+/// \brief Sample profile pass.
+///
+/// This pass reads profile data from the file specified by
+/// -sample-profile-file and annotates every affected function with the
+/// profile information found in that file.
+class SampleProfileLoader : public FunctionPass {
+public:
+ // Class identification, replacement for typeinfo
+ static char ID;
+
+ SampleProfileLoader(StringRef Name = SampleProfileFile)
+ : FunctionPass(ID), Profiler(0), Filename(Name) {
+ initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
+ }
+
+ virtual bool doInitialization(Module &M);
+
+ void dump() { Profiler->dump(); }
+
+ virtual const char *getPassName() const { return "Sample profile pass"; }
+
+ virtual bool runOnFunction(Function &F);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesCFG();
+ }
+
+protected:
+ /// \brief Profile reader object.
+ OwningPtr<SampleProfile> Profiler;
+
+ /// \brief Name of the profile file to load.
+ StringRef Filename;
+};
+}
+
+/// \brief Print the function profile for \p FName on stream \p OS.
+///
+/// \param OS Stream to emit the output to.
+/// \param FName Name of the function to print.
+void SampleProfile::printFunctionProfile(raw_ostream &OS, StringRef FName) {
+ FunctionProfile FProfile = Profiles[FName];
+ OS << "Function: " << FName << ", " << FProfile.TotalSamples << ", "
+ << FProfile.TotalHeadSamples << ", " << FProfile.BodySamples.size()
+ << " sampled lines\n";
+ for (BodySampleMap::const_iterator SI = FProfile.BodySamples.begin(),
+ SE = FProfile.BodySamples.end();
+ SI != SE; ++SI)
+ OS << "\tline offset: " << SI->first
+ << ", number of samples: " << SI->second << "\n";
+ OS << "\n";
+}
+
+/// \brief Dump the function profile for \p FName.
+///
+/// \param FName Name of the function to print.
+void SampleProfile::dumpFunctionProfile(StringRef FName) {
+ printFunctionProfile(dbgs(), FName);
+}
+
+/// \brief Dump all the function profiles found.
+void SampleProfile::dump() {
+ for (StringMap<FunctionProfile>::const_iterator I = Profiles.begin(),
+ E = Profiles.end();
+ I != E; ++I)
+ dumpFunctionProfile(I->getKey());
+}
+
+/// \brief Load samples from a text file.
+///
+/// The file is divided in two segments:
+///
+/// Symbol table (represented with the string "symbol table")
+/// Number of symbols in the table
+/// symbol 1
+/// symbol 2
+/// ...
+/// symbol N
+///
+/// Function body profiles
+/// function1:total_samples:total_head_samples:number_of_locations
+/// location_offset_1: number_of_samples
+/// location_offset_2: number_of_samples
+/// ...
+/// location_offset_N: number_of_samples
+///
+/// Function names must be mangled in order for the profile loader to
+/// match them in the current translation unit.
+///
+/// Since this is a flat profile, a function that shows up more than
+/// once gets all its samples aggregated across all its instances.
+/// TODO - flat profiles are too imprecise to provide good optimization
+/// opportunities. Convert them to context-sensitive profile.
+///
+/// This textual representation is useful to generate unit tests and
+/// for debugging purposes, but it should not be used to generate
+/// profiles for large programs, as the representation is extremely
+/// inefficient.
+void SampleProfile::loadText() {
+ ExternalProfileTextLoader Loader(Filename);
+
+ // Read the symbol table.
+ StringRef Line = Loader.readLine();
+ if (Line != "symbol table")
+ Loader.reportParseError("Expected 'symbol table', found " + Line);
+ int NumSymbols;
+ Line = Loader.readLine();
+ if (Line.getAsInteger(10, NumSymbols))
+ Loader.reportParseError("Expected a number, found " + Line);
+ for (int I = 0; I < NumSymbols; I++) {
+ StringRef FName = Loader.readLine();
+ FunctionProfile &FProfile = Profiles[FName];
+ FProfile.BodySamples.clear();
+ FProfile.TotalSamples = 0;
+ FProfile.TotalHeadSamples = 0;
+ }
+
+ // Read the profile of each function. Since each function may be
+ // mentioned more than once, and we are collecting flat profiles,
+ // accumulate samples as we parse them.
+ Regex HeadRE("^([^:]+):([0-9]+):([0-9]+):([0-9]+)$");
+ Regex LineSample("^([0-9]+): ([0-9]+)$");
+ while (!Loader.atEOF()) {
+ SmallVector<StringRef, 4> Matches;
+ Line = Loader.readLine();
+ if (!HeadRE.match(Line, &Matches))
+ Loader.reportParseError("Expected 'mangled_name:NUM:NUM:NUM', found " +
+ Line);
+ assert(Matches.size() == 5);
+ StringRef FName = Matches[1];
+ unsigned NumSamples, NumHeadSamples, NumSampledLines;
+ Matches[2].getAsInteger(10, NumSamples);
+ Matches[3].getAsInteger(10, NumHeadSamples);
+ Matches[4].getAsInteger(10, NumSampledLines);
+ FunctionProfile &FProfile = Profiles[FName];
+ FProfile.TotalSamples += NumSamples;
+ FProfile.TotalHeadSamples += NumHeadSamples;
+ BodySampleMap &SampleMap = FProfile.BodySamples;
+ unsigned I;
+ for (I = 0; I < NumSampledLines && !Loader.atEOF(); I++) {
+ Line = Loader.readLine();
+ if (!LineSample.match(Line, &Matches))
+ Loader.reportParseError("Expected 'NUM: NUM', found " + Line);
+ assert(Matches.size() == 3);
+ unsigned LineOffset, NumSamples;
+ Matches[1].getAsInteger(10, LineOffset);
+ Matches[2].getAsInteger(10, NumSamples);
+ SampleMap[LineOffset] += NumSamples;
+ }
+
+ if (I < NumSampledLines)
+ Loader.reportParseError("Unexpected end of file");
+ }
+}
+
+/// \brief Get the weight for an instruction.
+///
+/// The "weight" of an instruction \p Inst is the number of samples
+/// collected on that instruction at runtime. To retrieve it, we
+/// need to compute the line number of \p Inst relative to the start of its
+/// function. We use \p FirstLineno to compute the offset. We then
+/// look up the samples collected for \p Inst using \p BodySamples.
+///
+/// \param Inst Instruction to query.
+/// \param FirstLineno Line number of the first instruction in the function.
+/// \param BodySamples Map of relative source line locations to samples.
+///
+/// \returns The profiled weight of I.
+uint32_t SampleProfile::getInstWeight(Instruction &Inst, unsigned FirstLineno,
+ BodySampleMap &BodySamples) {
+ unsigned LOffset = Inst.getDebugLoc().getLine() - FirstLineno + 1;
+ return BodySamples.lookup(LOffset);
+}
+
+/// \brief Compute the weight of a basic block.
+///
+/// The weight of basic block \p B is the maximum weight of all the
+/// instructions in B.
+///
+/// \param B The basic block to query.
+/// \param FirstLineno The line number for the first line in the
+/// function holding B.
+/// \param BodySamples The map containing all the samples collected in that
+/// function.
+///
+/// \returns The computed weight of B.
+uint32_t SampleProfile::computeBlockWeight(BasicBlock *B, unsigned FirstLineno,
+ BodySampleMap &BodySamples) {
+ // If we've computed B's weight before, return it.
+ Function *F = B->getParent();
+ FunctionProfile &FProfile = Profiles[F->getName()];
+ std::pair<BlockWeightMap::iterator, bool> Entry =
+ FProfile.BlockWeights.insert(std::make_pair(B, 0));
+ if (!Entry.second)
+ return Entry.first->second;
+
+ // Otherwise, compute and cache B's weight.
+ uint32_t Weight = 0;
+ for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
+ uint32_t InstWeight = getInstWeight(*I, FirstLineno, BodySamples);
+ if (InstWeight > Weight)
+ Weight = InstWeight;
+ }
+ Entry.first->second = Weight;
+ return Weight;
+}
+
+/// \brief Generate branch weight metadata for all branches in \p F.
+///
+/// For every branch instruction B in \p F, we compute the weight of the
+/// target block for each of the edges out of B. This is the weight
+/// that we associate with that branch.
+///
+/// TODO - This weight assignment will most likely be wrong if the
+/// target branch has more than two predecessors. This needs to be done
+/// using some form of flow propagation.
+///
+/// Once all the branch weights are computed, we emit the MD_prof
+/// metadata on B using the computed values.
+///
+/// \param F The function to query.
+bool SampleProfile::emitAnnotations(Function &F) {
+ bool Changed = false;
+ FunctionProfile &FProfile = Profiles[F.getName()];
+ unsigned FirstLineno = inst_begin(F)->getDebugLoc().getLine();
+ MDBuilder MDB(F.getContext());
+
+ // Clear the block weights cache.
+ FProfile.BlockWeights.clear();
+
+ // When we find a branch instruction: For each edge E out of the branch,
+ // the weight of E is the weight of the target block.
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
+ BasicBlock *B = I;
+ TerminatorInst *TI = B->getTerminator();
+ if (TI->getNumSuccessors() == 1)
+ continue;
+ if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
+ continue;
+
+ SmallVector<uint32_t, 4> Weights;
+ unsigned NSuccs = TI->getNumSuccessors();
+ for (unsigned I = 0; I < NSuccs; ++I) {
+ BasicBlock *Succ = TI->getSuccessor(I);
+ uint32_t Weight =
+ computeBlockWeight(Succ, FirstLineno, FProfile.BodySamples);
+ Weights.push_back(Weight);
+ }
+
+ TI->setMetadata(llvm::LLVMContext::MD_prof,
+ MDB.createBranchWeights(Weights));
+ Changed = true;
+ }
+
+ return Changed;
+}
+
+char SampleProfileLoader::ID = 0;
+INITIALIZE_PASS(SampleProfileLoader, "sample-profile", "Sample Profile loader",
+ false, false)
+
+bool SampleProfileLoader::runOnFunction(Function &F) {
+ return Profiler->emitAnnotations(F);
+}
+
+bool SampleProfileLoader::doInitialization(Module &M) {
+ Profiler.reset(new SampleProfile(Filename));
+ Profiler->loadText();
+ return true;
+}
+
+FunctionPass *llvm::createSampleProfileLoaderPass() {
+ return new SampleProfileLoader(SampleProfileFile);
+}
+
+FunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) {
+ return new SampleProfileLoader(Name);
+}
generated by cgit v1.1 at 2024-05-17 20:59:06 +0000