1 //===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the SampleProfileLoader transformation. This pass
11 // reads a profile file generated by a sampling profiler (e.g. Linux Perf -
12 // http://perf.wiki.kernel.org/) and generates IR metadata to reflect the
13 // profile information in the given profile.
15 // This pass generates branch weight annotations on the IR:
17 // - prof: Represents branch weights. This annotation is added to branches
18 // to indicate the weights of each edge coming out of the branch.
19 // The weight of each edge is the weight of the target block for
20 // that edge. The weight of a block B is computed as the maximum
21 // number of samples found in B.
23 //===----------------------------------------------------------------------===//
25 #define DEBUG_TYPE "sample-profile"
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/OwningPtr.h"
29 #include "llvm/ADT/StringMap.h"
30 #include "llvm/ADT/StringRef.h"
31 #include "llvm/DebugInfo/DIContext.h"
32 #include "llvm/IR/Constants.h"
33 #include "llvm/IR/Function.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/LLVMContext.h"
36 #include "llvm/IR/MDBuilder.h"
37 #include "llvm/IR/Metadata.h"
38 #include "llvm/IR/Module.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/CommandLine.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/InstIterator.h"
43 #include "llvm/Support/MemoryBuffer.h"
44 #include "llvm/Support/Regex.h"
45 #include "llvm/Support/raw_ostream.h"
46 #include "llvm/Transforms/Scalar.h"
50 // Command line option to specify the file to read samples from. This is
51 // mainly used for debugging.
52 static cl::opt<std::string> SampleProfileFile(
53 "sample-profile-file", cl::init(""), cl::value_desc("filename"),
54 cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
58 typedef DenseMap<uint32_t, uint32_t> BodySampleMap;
59 typedef DenseMap<BasicBlock *, uint32_t> BlockWeightMap;
61 /// \brief Representation of the runtime profile for a function.
63 /// This data structure contains the runtime profile for a given
64 /// function. It contains the total number of samples collected
65 /// in the function and a map of samples collected in every statement.
66 class SampleFunctionProfile {
68 SampleFunctionProfile() : TotalSamples(0), TotalHeadSamples(0) {}
70 bool emitAnnotations(Function &F);
71 uint32_t getInstWeight(Instruction &I, unsigned FirstLineno,
72 BodySampleMap &BodySamples);
73 uint32_t computeBlockWeight(BasicBlock *B, unsigned FirstLineno,
74 BodySampleMap &BodySamples);
75 void addTotalSamples(unsigned Num) { TotalSamples += Num; }
76 void addHeadSamples(unsigned Num) { TotalHeadSamples += Num; }
77 void addBodySamples(unsigned LineOffset, unsigned Num) {
78 BodySamples[LineOffset] += Num;
80 void print(raw_ostream &OS);
83 /// \brief Total number of samples collected inside this function.
85 /// Samples are cumulative, they include all the samples collected
86 /// inside this function and all its inlined callees.
87 unsigned TotalSamples;
89 // \brief Total number of samples collected at the head of the function.
90 unsigned TotalHeadSamples;
92 /// \brief Map line offsets to collected samples.
94 /// Each entry in this map contains the number of samples
95 /// collected at the corresponding line offset. All line locations
96 /// are an offset from the start of the function.
97 BodySampleMap BodySamples;
99 /// \brief Map basic blocks to their computed weights.
101 /// The weight of a basic block is defined to be the maximum
102 /// of all the instruction weights in that block.
103 BlockWeightMap BlockWeights;
106 /// \brief Sample-based profile reader.
108 /// Each profile contains sample counts for all the functions
109 /// executed. Inside each function, statements are annotated with the
110 /// collected samples on all the instructions associated with that
113 /// For this to produce meaningful data, the program needs to be
114 /// compiled with some debug information (at minimum, line numbers:
115 /// -gline-tables-only). Otherwise, it will be impossible to match IR
116 /// instructions to the line numbers collected by the profiler.
118 /// From the profile file, we are interested in collecting the
119 /// following information:
121 /// * A list of functions included in the profile (mangled names).
123 /// * For each function F:
124 /// 1. The total number of samples collected in F.
126 /// 2. The samples collected at each line in F. To provide some
127 /// protection against source code shuffling, line numbers should
128 /// be relative to the start of the function.
129 class SampleModuleProfile {
131 SampleModuleProfile(StringRef F) : Profiles(0), Filename(F) {}
135 void loadNative() { llvm_unreachable("not implemented"); }
136 void printFunctionProfile(raw_ostream &OS, StringRef FName);
137 void dumpFunctionProfile(StringRef FName);
138 SampleFunctionProfile &getProfile(const Function &F) {
139 return Profiles[F.getName()];
143 /// \brief Map every function to its associated profile.
145 /// The profile of every function executed at runtime is collected
146 /// in the structure SampleFunctionProfile. This maps function objects
147 /// to their corresponding profiles.
148 StringMap<SampleFunctionProfile> Profiles;
150 /// \brief Path name to the file holding the profile data.
152 /// The format of this file is defined by each profiler
153 /// independently. If possible, the profiler should have a text
154 /// version of the profile format to be used in constructing test
155 /// cases and debugging.
159 /// \brief Loader class for text-based profiles.
161 /// This class defines a simple interface to read text files containing
162 /// profiles. It keeps track of line number information and location of
163 /// the file pointer. Users of this class are responsible for actually
164 /// parsing the lines returned by the readLine function.
166 /// TODO - This does not really belong here. It is a generic text file
167 /// reader. It should be moved to the Support library and made more general.
168 class ExternalProfileTextLoader {
170 ExternalProfileTextLoader(StringRef F) : Filename(F) {
172 EC = MemoryBuffer::getFile(Filename, Buffer);
174 report_fatal_error("Could not open profile file " + Filename + ": " +
176 FP = Buffer->getBufferStart();
180 /// \brief Read a line from the mapped file.
181 StringRef readLine() {
183 const char *start = FP;
184 while (FP != Buffer->getBufferEnd() && *FP != '\n') {
188 if (FP != Buffer->getBufferEnd())
191 return StringRef(start, Length);
194 /// \brief Return true, if we've reached EOF.
195 bool atEOF() const { return FP == Buffer->getBufferEnd(); }
197 /// \brief Report a parse error message and stop compilation.
198 void reportParseError(Twine Msg) const {
199 report_fatal_error(Filename + ":" + Twine(Lineno) + ": " + Msg + "\n");
203 /// \brief Memory buffer holding the text file.
204 OwningPtr<MemoryBuffer> Buffer;
206 /// \brief Current position into the memory buffer.
209 /// \brief Current line number.
212 /// \brief Path name where to the profile file.
216 /// \brief Sample profile pass.
218 /// This pass reads profile data from the file specified by
219 /// -sample-profile-file and annotates every affected function with the
220 /// profile information found in that file.
221 class SampleProfileLoader : public FunctionPass {
223 // Class identification, replacement for typeinfo
226 SampleProfileLoader(StringRef Name = SampleProfileFile)
227 : FunctionPass(ID), Profiler(0), Filename(Name) {
228 initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
231 virtual bool doInitialization(Module &M);
233 void dump() { Profiler->dump(); }
235 virtual const char *getPassName() const { return "Sample profile pass"; }
237 virtual bool runOnFunction(Function &F);
239 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
240 AU.setPreservesCFG();
244 /// \brief Profile reader object.
245 OwningPtr<SampleModuleProfile> Profiler;
247 /// \brief Name of the profile file to load.
252 /// \brief Print this function profile on stream \p OS.
254 /// \param OS Stream to emit the output to.
255 void SampleFunctionProfile::print(raw_ostream &OS) {
256 OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
257 << " sampled lines\n";
258 for (BodySampleMap::const_iterator SI = BodySamples.begin(),
259 SE = BodySamples.end();
261 OS << "\tline offset: " << SI->first
262 << ", number of samples: " << SI->second << "\n";
266 /// \brief Print the function profile for \p FName on stream \p OS.
268 /// \param OS Stream to emit the output to.
269 /// \param FName Name of the function to print.
270 void SampleModuleProfile::printFunctionProfile(raw_ostream &OS,
272 OS << "Function: " << FName << ":\n";
273 Profiles[FName].print(OS);
276 /// \brief Dump the function profile for \p FName.
278 /// \param FName Name of the function to print.
279 void SampleModuleProfile::dumpFunctionProfile(StringRef FName) {
280 printFunctionProfile(dbgs(), FName);
283 /// \brief Dump all the function profiles found.
284 void SampleModuleProfile::dump() {
285 for (StringMap<SampleFunctionProfile>::const_iterator I = Profiles.begin(),
288 dumpFunctionProfile(I->getKey());
291 /// \brief Load samples from a text file.
293 /// The file is divided in two segments:
295 /// Symbol table (represented with the string "symbol table")
296 /// Number of symbols in the table
302 /// Function body profiles
303 /// function1:total_samples:total_head_samples:number_of_locations
304 /// location_offset_1: number_of_samples
305 /// location_offset_2: number_of_samples
307 /// location_offset_N: number_of_samples
309 /// Function names must be mangled in order for the profile loader to
310 /// match them in the current translation unit.
312 /// Since this is a flat profile, a function that shows up more than
313 /// once gets all its samples aggregated across all its instances.
314 /// TODO - flat profiles are too imprecise to provide good optimization
315 /// opportunities. Convert them to context-sensitive profile.
317 /// This textual representation is useful to generate unit tests and
318 /// for debugging purposes, but it should not be used to generate
319 /// profiles for large programs, as the representation is extremely
321 void SampleModuleProfile::loadText() {
322 ExternalProfileTextLoader Loader(Filename);
324 // Read the symbol table.
325 StringRef Line = Loader.readLine();
326 if (Line != "symbol table")
327 Loader.reportParseError("Expected 'symbol table', found " + Line);
329 Line = Loader.readLine();
330 if (Line.getAsInteger(10, NumSymbols))
331 Loader.reportParseError("Expected a number, found " + Line);
332 for (int I = 0; I < NumSymbols; I++)
333 Profiles[Loader.readLine()] = SampleFunctionProfile();
335 // Read the profile of each function. Since each function may be
336 // mentioned more than once, and we are collecting flat profiles,
337 // accumulate samples as we parse them.
338 Regex HeadRE("^([^:]+):([0-9]+):([0-9]+):([0-9]+)$");
339 Regex LineSample("^([0-9]+): ([0-9]+)$");
340 while (!Loader.atEOF()) {
341 SmallVector<StringRef, 4> Matches;
342 Line = Loader.readLine();
343 if (!HeadRE.match(Line, &Matches))
344 Loader.reportParseError("Expected 'mangled_name:NUM:NUM:NUM', found " +
346 assert(Matches.size() == 5);
347 StringRef FName = Matches[1];
348 unsigned NumSamples, NumHeadSamples, NumSampledLines;
349 Matches[2].getAsInteger(10, NumSamples);
350 Matches[3].getAsInteger(10, NumHeadSamples);
351 Matches[4].getAsInteger(10, NumSampledLines);
352 SampleFunctionProfile &FProfile = Profiles[FName];
353 FProfile.addTotalSamples(NumSamples);
354 FProfile.addHeadSamples(NumHeadSamples);
356 for (I = 0; I < NumSampledLines && !Loader.atEOF(); I++) {
357 Line = Loader.readLine();
358 if (!LineSample.match(Line, &Matches))
359 Loader.reportParseError("Expected 'NUM: NUM', found " + Line);
360 assert(Matches.size() == 3);
361 unsigned LineOffset, NumSamples;
362 Matches[1].getAsInteger(10, LineOffset);
363 Matches[2].getAsInteger(10, NumSamples);
364 FProfile.addBodySamples(LineOffset, NumSamples);
367 if (I < NumSampledLines)
368 Loader.reportParseError("Unexpected end of file");
372 char SampleProfileLoader::ID = 0;
373 INITIALIZE_PASS(SampleProfileLoader, "sample-profile", "Sample Profile loader",
376 bool SampleProfileLoader::doInitialization(Module &M) {
377 Profiler.reset(new SampleModuleProfile(Filename));
378 Profiler->loadText();
382 FunctionPass *llvm::createSampleProfileLoaderPass() {
383 return new SampleProfileLoader(SampleProfileFile);
386 FunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) {
387 return new SampleProfileLoader(Name);
390 /// \brief Get the weight for an instruction.
392 /// The "weight" of an instruction \p Inst is the number of samples
393 /// collected on that instruction at runtime. To retrieve it, we
394 /// need to compute the line number of \p Inst relative to the start of its
395 /// function. We use \p FirstLineno to compute the offset. We then
396 /// look up the samples collected for \p Inst using \p BodySamples.
398 /// \param Inst Instruction to query.
399 /// \param FirstLineno Line number of the first instruction in the function.
400 /// \param BodySamples Map of relative source line locations to samples.
402 /// \returns The profiled weight of I.
403 uint32_t SampleFunctionProfile::getInstWeight(Instruction &Inst,
404 unsigned FirstLineno,
405 BodySampleMap &BodySamples) {
406 unsigned LOffset = Inst.getDebugLoc().getLine() - FirstLineno + 1;
407 return BodySamples.lookup(LOffset);
410 /// \brief Compute the weight of a basic block.
412 /// The weight of basic block \p B is the maximum weight of all the
413 /// instructions in B.
415 /// \param B The basic block to query.
416 /// \param FirstLineno The line number for the first line in the
417 /// function holding B.
418 /// \param BodySamples The map containing all the samples collected in that
421 /// \returns The computed weight of B.
422 uint32_t SampleFunctionProfile::computeBlockWeight(BasicBlock *B,
423 unsigned FirstLineno,
424 BodySampleMap &BodySamples) {
425 // If we've computed B's weight before, return it.
426 std::pair<BlockWeightMap::iterator, bool> Entry =
427 BlockWeights.insert(std::make_pair(B, 0));
429 return Entry.first->second;
431 // Otherwise, compute and cache B's weight.
433 for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
434 uint32_t InstWeight = getInstWeight(*I, FirstLineno, BodySamples);
435 if (InstWeight > Weight)
438 Entry.first->second = Weight;
442 /// \brief Generate branch weight metadata for all branches in \p F.
444 /// For every branch instruction B in \p F, we compute the weight of the
445 /// target block for each of the edges out of B. This is the weight
446 /// that we associate with that branch.
448 /// TODO - This weight assignment will most likely be wrong if the
449 /// target branch has more than two predecessors. This needs to be done
450 /// using some form of flow propagation.
452 /// Once all the branch weights are computed, we emit the MD_prof
453 /// metadata on B using the computed values.
455 /// \param F The function to query.
456 bool SampleFunctionProfile::emitAnnotations(Function &F) {
457 bool Changed = false;
458 unsigned FirstLineno = inst_begin(F)->getDebugLoc().getLine();
459 MDBuilder MDB(F.getContext());
461 // Clear the block weights cache.
462 BlockWeights.clear();
464 // When we find a branch instruction: For each edge E out of the branch,
465 // the weight of E is the weight of the target block.
466 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
468 TerminatorInst *TI = B->getTerminator();
469 if (TI->getNumSuccessors() == 1)
471 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
474 SmallVector<uint32_t, 4> Weights;
475 unsigned NSuccs = TI->getNumSuccessors();
476 for (unsigned I = 0; I < NSuccs; ++I) {
477 BasicBlock *Succ = TI->getSuccessor(I);
478 uint32_t Weight = computeBlockWeight(Succ, FirstLineno, BodySamples);
479 Weights.push_back(Weight);
482 TI->setMetadata(llvm::LLVMContext::MD_prof,
483 MDB.createBranchWeights(Weights));
490 bool SampleProfileLoader::runOnFunction(Function &F) {
491 return Profiler->getProfile(F).emitAnnotations(F);