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 48 using namespace llvm; 49 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); 55 56 namespace { 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. 80 class SampleProfile { 81 public: 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 91 protected: 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. 154 class ExternalProfileTextLoader { 155 public: 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 188 private: 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. 207 class SampleProfileLoader : public FunctionPass { 208 public: 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 229 protected: 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. 242 void 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. 258 void SampleProfile::dumpFunctionProfile(StringRef FName) { 259 printFunctionProfile(dbgs(), FName); 260 } 261 262 /// \brief Dump all the function profiles found. 263 void 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. 300 void 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. 370 uint32_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. 388 uint32_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. 423 bool 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 459 char SampleProfileLoader::ID = 0; 460 INITIALIZE_PASS(SampleProfileLoader, "sample-profile", "Sample Profile loader", 461 false, false) 462 463 bool SampleProfileLoader::runOnFunction(Function &F) { 464 return Profiler->emitAnnotations(F); 465 } 466 467 bool SampleProfileLoader::doInitialization(Module &M) { 468 Profiler.reset(new SampleProfile(Filename)); 469 Profiler->loadText(); 470 return true; 471 } 472 473 FunctionPass *llvm::createSampleProfileLoaderPass() { 474 return new SampleProfileLoader(SampleProfileFile); 475 } 476 477 FunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) { 478 return new SampleProfileLoader(Name); 479 } 480