SampleProfile.cpp revision 4223b9601058369536caa1d15c9c19bc7c5a3706
1//===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 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. 14// 15// This pass generates branch weight annotations on the IR: 16// 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. 22// 23//===----------------------------------------------------------------------===// 24 25#define DEBUG_TYPE "sample-profile" 26 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/Metadata.h" 37#include "llvm/IR/MDBuilder.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" 47 48using namespace llvm; 49 50// Command line option to specify the file to read samples from. This is 51// mainly used for debugging. 52static 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); 55 56namespace { 57/// \brief Sample-based profile reader. 58/// 59/// Each profile contains sample counts for all the functions 60/// executed. Inside each function, statements are annotated with the 61/// collected samples on all the instructions associated with that 62/// statement. 63/// 64/// For this to produce meaningful data, the program needs to be 65/// compiled with some debug information (at minimum, line numbers: 66/// -gline-tables-only). Otherwise, it will be impossible to match IR 67/// instructions to the line numbers collected by the profiler. 68/// 69/// From the profile file, we are interested in collecting the 70/// following information: 71/// 72/// * A list of functions included in the profile (mangled names). 73/// 74/// * For each function F: 75/// 1. The total number of samples collected in F. 76/// 77/// 2. The samples collected at each line in F. To provide some 78/// protection against source code shuffling, line numbers should 79/// be relative to the start of the function. 80class SampleProfile { 81public: 82 SampleProfile(StringRef F) : Profiles(0), Filename(F) {} 83 84 void dump(); 85 void loadText(); 86 void loadNative() { llvm_unreachable("not implemented"); } 87 bool emitAnnotations(Function &F); 88 void printFunctionProfile(raw_ostream &OS, StringRef FName); 89 void dumpFunctionProfile(StringRef FName); 90 91protected: 92 typedef DenseMap<uint32_t, uint32_t> BodySampleMap; 93 typedef DenseMap<BasicBlock *, uint32_t> BlockWeightMap; 94 95 /// \brief Representation of the runtime profile for a function. 96 /// 97 /// This data structure contains the runtime profile for a given 98 /// function. It contains the total number of samples collected 99 /// in the function and a map of samples collected in every statement. 100 struct FunctionProfile { 101 /// \brief Total number of samples collected inside this function. 102 /// 103 /// Samples are cumulative, they include all the samples collected 104 /// inside this function and all its inlined callees. 105 unsigned TotalSamples; 106 107 // \brief Total number of samples collected at the head of the function. 108 unsigned TotalHeadSamples; 109 110 /// \brief Map line offsets to collected samples. 111 /// 112 /// Each entry in this map contains the number of samples 113 /// collected at the corresponding line offset. All line locations 114 /// are an offset from the start of the function. 115 BodySampleMap BodySamples; 116 117 /// \brief Map basic blocks to their computed weights. 118 /// 119 /// The weight of a basic block is defined to be the maximum 120 /// of all the instruction weights in that block. 121 BlockWeightMap BlockWeights; 122 }; 123 124 uint32_t getInstWeight(Instruction &I, unsigned FirstLineno, 125 BodySampleMap &BodySamples); 126 uint32_t computeBlockWeight(BasicBlock *B, unsigned FirstLineno, 127 BodySampleMap &BodySamples); 128 129 /// \brief Map every function to its associated profile. 130 /// 131 /// The profile of every function executed at runtime is collected 132 /// in the structure FunctionProfile. This maps function objects 133 /// to their corresponding profiles. 134 StringMap<FunctionProfile> Profiles; 135 136 /// \brief Path name to the file holding the profile data. 137 /// 138 /// The format of this file is defined by each profiler 139 /// independently. If possible, the profiler should have a text 140 /// version of the profile format to be used in constructing test 141 /// cases and debugging. 142 StringRef Filename; 143}; 144 145/// \brief Loader class for text-based profiles. 146/// 147/// This class defines a simple interface to read text files containing 148/// profiles. It keeps track of line number information and location of 149/// the file pointer. Users of this class are responsible for actually 150/// parsing the lines returned by the readLine function. 151/// 152/// TODO - This does not really belong here. It is a generic text file 153/// reader. It should be moved to the Support library and made more general. 154class ExternalProfileTextLoader { 155public: 156 ExternalProfileTextLoader(StringRef F) : Filename(F) { 157 error_code EC; 158 EC = MemoryBuffer::getFile(Filename, Buffer); 159 if (EC) 160 report_fatal_error("Could not open profile file " + Filename + ": " + 161 EC.message()); 162 FP = Buffer->getBufferStart(); 163 Lineno = 0; 164 } 165 166 /// \brief Read a line from the mapped file. 167 StringRef readLine() { 168 size_t Length = 0; 169 const char *start = FP; 170 while (FP != Buffer->getBufferEnd() && *FP != '\n') { 171 Length++; 172 FP++; 173 } 174 if (FP != Buffer->getBufferEnd()) 175 FP++; 176 Lineno++; 177 return StringRef(start, Length); 178 } 179 180 /// \brief Return true, if we've reached EOF. 181 bool atEOF() const { return FP == Buffer->getBufferEnd(); } 182 183 /// \brief Report a parse error message and stop compilation. 184 void reportParseError(Twine Msg) const { 185 report_fatal_error(Filename + ":" + Twine(Lineno) + ": " + Msg + "\n"); 186 } 187 188private: 189 /// \brief Memory buffer holding the text file. 190 OwningPtr<MemoryBuffer> Buffer; 191 192 /// \brief Current position into the memory buffer. 193 const char *FP; 194 195 /// \brief Current line number. 196 int64_t Lineno; 197 198 /// \brief Path name where to the profile file. 199 StringRef Filename; 200}; 201 202/// \brief Sample profile pass. 203/// 204/// This pass reads profile data from the file specified by 205/// -sample-profile-file and annotates every affected function with the 206/// profile information found in that file. 207class SampleProfileLoader : public FunctionPass { 208public: 209 // Class identification, replacement for typeinfo 210 static char ID; 211 212 SampleProfileLoader(StringRef Name = SampleProfileFile) 213 : FunctionPass(ID), Profiler(0), Filename(Name) { 214 initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry()); 215 } 216 217 virtual bool doInitialization(Module &M); 218 219 void dump() { Profiler->dump(); } 220 221 virtual const char *getPassName() const { return "Sample profile pass"; } 222 223 virtual bool runOnFunction(Function &F); 224 225 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 226 AU.setPreservesCFG(); 227 } 228 229protected: 230 /// \brief Profile reader object. 231 OwningPtr<SampleProfile> Profiler; 232 233 /// \brief Name of the profile file to load. 234 StringRef Filename; 235}; 236} 237 238/// \brief Print the function profile for \p FName on stream \p OS. 239/// 240/// \param OS Stream to emit the output to. 241/// \param FName Name of the function to print. 242void SampleProfile::printFunctionProfile(raw_ostream &OS, StringRef FName) { 243 FunctionProfile FProfile = Profiles[FName]; 244 OS << "Function: " << FName << ", " << FProfile.TotalSamples << ", " 245 << FProfile.TotalHeadSamples << ", " << FProfile.BodySamples.size() 246 << " sampled lines\n"; 247 for (BodySampleMap::const_iterator SI = FProfile.BodySamples.begin(), 248 SE = FProfile.BodySamples.end(); 249 SI != SE; ++SI) 250 OS << "\tline offset: " << SI->first 251 << ", number of samples: " << SI->second << "\n"; 252 OS << "\n"; 253} 254 255/// \brief Dump the function profile for \p FName. 256/// 257/// \param FName Name of the function to print. 258void SampleProfile::dumpFunctionProfile(StringRef FName) { 259 printFunctionProfile(dbgs(), FName); 260} 261 262/// \brief Dump all the function profiles found. 263void SampleProfile::dump() { 264 for (StringMap<FunctionProfile>::const_iterator I = Profiles.begin(), 265 E = Profiles.end(); 266 I != E; ++I) 267 dumpFunctionProfile(I->getKey()); 268} 269 270/// \brief Load samples from a text file. 271/// 272/// The file is divided in two segments: 273/// 274/// Symbol table (represented with the string "symbol table") 275/// Number of symbols in the table 276/// symbol 1 277/// symbol 2 278/// ... 279/// symbol N 280/// 281/// Function body profiles 282/// function1:total_samples:total_head_samples:number_of_locations 283/// location_offset_1: number_of_samples 284/// location_offset_2: number_of_samples 285/// ... 286/// location_offset_N: number_of_samples 287/// 288/// Function names must be mangled in order for the profile loader to 289/// match them in the current translation unit. 290/// 291/// Since this is a flat profile, a function that shows up more than 292/// once gets all its samples aggregated across all its instances. 293/// TODO - flat profiles are too imprecise to provide good optimization 294/// opportunities. Convert them to context-sensitive profile. 295/// 296/// This textual representation is useful to generate unit tests and 297/// for debugging purposes, but it should not be used to generate 298/// profiles for large programs, as the representation is extremely 299/// inefficient. 300void SampleProfile::loadText() { 301 ExternalProfileTextLoader Loader(Filename); 302 303 // Read the symbol table. 304 StringRef Line = Loader.readLine(); 305 if (Line != "symbol table") 306 Loader.reportParseError("Expected 'symbol table', found " + Line); 307 int NumSymbols; 308 Line = Loader.readLine(); 309 if (Line.getAsInteger(10, NumSymbols)) 310 Loader.reportParseError("Expected a number, found " + Line); 311 for (int I = 0; I < NumSymbols; I++) { 312 StringRef FName = Loader.readLine(); 313 FunctionProfile &FProfile = Profiles[FName]; 314 FProfile.BodySamples.clear(); 315 FProfile.TotalSamples = 0; 316 FProfile.TotalHeadSamples = 0; 317 } 318 319 // Read the profile of each function. Since each function may be 320 // mentioned more than once, and we are collecting flat profiles, 321 // accumulate samples as we parse them. 322 Regex HeadRE("^([^:]+):([0-9]+):([0-9]+):([0-9]+)$"); 323 Regex LineSample("^([0-9]+): ([0-9]+)$"); 324 while (!Loader.atEOF()) { 325 SmallVector<StringRef, 4> Matches; 326 Line = Loader.readLine(); 327 if (!HeadRE.match(Line, &Matches)) 328 Loader.reportParseError("Expected 'mangled_name:NUM:NUM:NUM', found " + 329 Line); 330 assert(Matches.size() == 5); 331 StringRef FName = Matches[1]; 332 unsigned NumSamples, NumHeadSamples, NumSampledLines; 333 Matches[2].getAsInteger(10, NumSamples); 334 Matches[3].getAsInteger(10, NumHeadSamples); 335 Matches[4].getAsInteger(10, NumSampledLines); 336 FunctionProfile &FProfile = Profiles[FName]; 337 FProfile.TotalSamples += NumSamples; 338 FProfile.TotalHeadSamples += NumHeadSamples; 339 BodySampleMap &SampleMap = FProfile.BodySamples; 340 unsigned I; 341 for (I = 0; I < NumSampledLines && !Loader.atEOF(); I++) { 342 Line = Loader.readLine(); 343 if (!LineSample.match(Line, &Matches)) 344 Loader.reportParseError("Expected 'NUM: NUM', found " + Line); 345 assert(Matches.size() == 3); 346 unsigned LineOffset, NumSamples; 347 Matches[1].getAsInteger(10, LineOffset); 348 Matches[2].getAsInteger(10, NumSamples); 349 SampleMap[LineOffset] += NumSamples; 350 } 351 352 if (I < NumSampledLines) 353 Loader.reportParseError("Unexpected end of file"); 354 } 355} 356 357/// \brief Get the weight for an instruction. 358/// 359/// The "weight" of an instruction \p Inst is the number of samples 360/// collected on that instruction at runtime. To retrieve it, we 361/// need to compute the line number of \p Inst relative to the start of its 362/// function. We use \p FirstLineno to compute the offset. We then 363/// look up the samples collected for \p Inst using \p BodySamples. 364/// 365/// \param Inst Instruction to query. 366/// \param FirstLineno Line number of the first instruction in the function. 367/// \param BodySamples Map of relative source line locations to samples. 368/// 369/// \returns The profiled weight of I. 370uint32_t SampleProfile::getInstWeight(Instruction &Inst, unsigned FirstLineno, 371 BodySampleMap &BodySamples) { 372 unsigned LOffset = Inst.getDebugLoc().getLine() - FirstLineno + 1; 373 return BodySamples.lookup(LOffset); 374} 375 376/// \brief Compute the weight of a basic block. 377/// 378/// The weight of basic block \p B is the maximum weight of all the 379/// instructions in B. 380/// 381/// \param B The basic block to query. 382/// \param FirstLineno The line number for the first line in the 383/// function holding B. 384/// \param BodySamples The map containing all the samples collected in that 385/// function. 386/// 387/// \returns The computed weight of B. 388uint32_t SampleProfile::computeBlockWeight(BasicBlock *B, unsigned FirstLineno, 389 BodySampleMap &BodySamples) { 390 // If we've computed B's weight before, return it. 391 Function *F = B->getParent(); 392 FunctionProfile &FProfile = Profiles[F->getName()]; 393 std::pair<BlockWeightMap::iterator, bool> Entry = 394 FProfile.BlockWeights.insert(std::make_pair(B, 0)); 395 if (!Entry.second) 396 return Entry.first->second; 397 398 // Otherwise, compute and cache B's weight. 399 uint32_t Weight = 0; 400 for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) { 401 uint32_t InstWeight = getInstWeight(*I, FirstLineno, BodySamples); 402 if (InstWeight > Weight) 403 Weight = InstWeight; 404 } 405 Entry.first->second = Weight; 406 return Weight; 407} 408 409/// \brief Generate branch weight metadata for all branches in \p F. 410/// 411/// For every branch instruction B in \p F, we compute the weight of the 412/// target block for each of the edges out of B. This is the weight 413/// that we associate with that branch. 414/// 415/// TODO - This weight assignment will most likely be wrong if the 416/// target branch has more than two predecessors. This needs to be done 417/// using some form of flow propagation. 418/// 419/// Once all the branch weights are computed, we emit the MD_prof 420/// metadata on B using the computed values. 421/// 422/// \param F The function to query. 423bool SampleProfile::emitAnnotations(Function &F) { 424 bool Changed = false; 425 FunctionProfile &FProfile = Profiles[F.getName()]; 426 unsigned FirstLineno = inst_begin(F)->getDebugLoc().getLine(); 427 MDBuilder MDB(F.getContext()); 428 429 // Clear the block weights cache. 430 FProfile.BlockWeights.clear(); 431 432 // When we find a branch instruction: For each edge E out of the branch, 433 // the weight of E is the weight of the target block. 434 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { 435 BasicBlock *B = I; 436 TerminatorInst *TI = B->getTerminator(); 437 if (TI->getNumSuccessors() == 1) 438 continue; 439 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI)) 440 continue; 441 442 SmallVector<uint32_t, 4> Weights; 443 unsigned NSuccs = TI->getNumSuccessors(); 444 for (unsigned I = 0; I < NSuccs; ++I) { 445 BasicBlock *Succ = TI->getSuccessor(I); 446 uint32_t Weight = 447 computeBlockWeight(Succ, FirstLineno, FProfile.BodySamples); 448 Weights.push_back(Weight); 449 } 450 451 TI->setMetadata(llvm::LLVMContext::MD_prof, 452 MDB.createBranchWeights(Weights)); 453 Changed = true; 454 } 455 456 return Changed; 457} 458 459char SampleProfileLoader::ID = 0; 460INITIALIZE_PASS(SampleProfileLoader, "sample-profile", "Sample Profile loader", 461 false, false) 462 463bool SampleProfileLoader::runOnFunction(Function &F) { 464 return Profiler->emitAnnotations(F); 465} 466 467bool SampleProfileLoader::doInitialization(Module &M) { 468 Profiler.reset(new SampleProfile(Filename)); 469 Profiler->loadText(); 470 return true; 471} 472 473FunctionPass *llvm::createSampleProfileLoaderPass() { 474 return new SampleProfileLoader(SampleProfileFile); 475} 476 477FunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) { 478 return new SampleProfileLoader(Name); 479} 480