lib/Transforms/Scalar/SampleProfile.cpp

   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/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"
  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
  58 typedef DenseMap<uint32_t, uint32_t> BodySampleMap;
  59 typedef DenseMap<BasicBlock *, uint32_t> BlockWeightMap;
  60
  61 /// \brief Representation of the runtime profile for a function.
  62 ///
  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 {
  67 public:
  68   SampleFunctionProfile() : TotalSamples(0), TotalHeadSamples(0) {}
  69
  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;
  79   }
  80   void print(raw_ostream &OS);
  81
  82 protected:
  83   /// \brief Total number of samples collected inside this function.
  84   ///
  85   /// Samples are cumulative, they include all the samples collected
  86   /// inside this function and all its inlined callees.
  87   unsigned TotalSamples;
  88
  89   // \brief Total number of samples collected at the head of the function.
  90   unsigned TotalHeadSamples;
  91
  92   /// \brief Map line offsets to collected samples.
  93   ///
  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;
  98
  99   /// \brief Map basic blocks to their computed weights.
 100   ///
 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;
 104 };
 105
 106 /// \brief Sample-based profile reader.
 107 ///
 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
 111 /// statement.
 112 ///
 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.
 117 ///
 118 /// From the profile file, we are interested in collecting the
 119 /// following information:
 120 ///
 121 /// * A list of functions included in the profile (mangled names).
 122 ///
 123 /// * For each function F:
 124 ///   1. The total number of samples collected in F.
 125 ///
 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 {
 130 public:
 131   SampleModuleProfile(StringRef F) : Profiles(0), Filename(F) {}
 132
 133   void dump();
 134   void loadText();
 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()];
 140   }
 141
 142 protected:
 143   /// \brief Map every function to its associated profile.
 144   ///
 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;
 149
 150   /// \brief Path name to the file holding the profile data.
 151   ///
 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.
 156   StringRef Filename;
 157 };
 158
 159 /// \brief Loader class for text-based profiles.
 160 ///
 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.
 165 ///
 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 {
 169 public:
 170   ExternalProfileTextLoader(StringRef F) : Filename(F) {
 171     error_code EC;
 172     EC = MemoryBuffer::getFile(Filename, Buffer);
 173     if (EC)
 174       report_fatal_error("Could not open profile file " + Filename + ": " +
 175                          EC.message());
 176     FP = Buffer->getBufferStart();
 177     Lineno = 0;
 178   }
 179
 180   /// \brief Read a line from the mapped file.
 181   StringRef readLine() {
 182     size_t Length = 0;
 183     const char *start = FP;
 184     while (FP != Buffer->getBufferEnd() && *FP != '\n') {
 185       Length++;
 186       FP++;
 187     }
 188     if (FP != Buffer->getBufferEnd())
 189       FP++;
 190     Lineno++;
 191     return StringRef(start, Length);
 192   }
 193
 194   /// \brief Return true, if we've reached EOF.
 195   bool atEOF() const { return FP == Buffer->getBufferEnd(); }
 196
 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");
 200   }
 201
 202 private:
 203   /// \brief Memory buffer holding the text file.
 204   OwningPtr<MemoryBuffer> Buffer;
 205
 206   /// \brief Current position into the memory buffer.
 207   const char *FP;
 208
 209   /// \brief Current line number.
 210   int64_t Lineno;
 211
 212   /// \brief Path name where to the profile file.
 213   StringRef Filename;
 214 };
 215
 216 /// \brief Sample profile pass.
 217 ///
 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 {
 222 public:
 223   // Class identification, replacement for typeinfo
 224   static char ID;
 225
 226   SampleProfileLoader(StringRef Name = SampleProfileFile)
 227       : FunctionPass(ID), Profiler(0), Filename(Name) {
 228     initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
 229   }
 230
 231   virtual bool doInitialization(Module &M);
 232
 233   void dump() { Profiler->dump(); }
 234
 235   virtual const char *getPassName() const { return "Sample profile pass"; }
 236
 237   virtual bool runOnFunction(Function &F);
 238
 239   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 240     AU.setPreservesCFG();
 241   }
 242
 243 protected:
 244   /// \brief Profile reader object.
 245   OwningPtr<SampleModuleProfile> Profiler;
 246
 247   /// \brief Name of the profile file to load.
 248   StringRef Filename;
 249 };
 250 }
 251
 252 /// \brief Print this function profile on stream \p OS.
 253 ///
 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();
 260        SI != SE; ++SI)
 261     OS << "\tline offset: " << SI->first
 262        << ", number of samples: " << SI->second << "\n";
 263   OS << "\n";
 264 }
 265
 266 /// \brief Print the function profile for \p FName on stream \p OS.
 267 ///
 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,
 271                                                StringRef FName) {
 272   OS << "Function: " << FName << ":\n";
 273   Profiles[FName].print(OS);
 274 }
 275
 276 /// \brief Dump the function profile for \p FName.
 277 ///
 278 /// \param FName Name of the function to print.
 279 void SampleModuleProfile::dumpFunctionProfile(StringRef FName) {
 280   printFunctionProfile(dbgs(), FName);
 281 }
 282
 283 /// \brief Dump all the function profiles found.
 284 void SampleModuleProfile::dump() {
 285   for (StringMap<SampleFunctionProfile>::const_iterator I = Profiles.begin(),
 286                                                         E = Profiles.end();
 287        I != E; ++I)
 288     dumpFunctionProfile(I->getKey());
 289 }
 290
 291 /// \brief Load samples from a text file.
 292 ///
 293 /// The file is divided in two segments:
 294 ///
 295 /// Symbol table (represented with the string "symbol table")
 296 ///    Number of symbols in the table
 297 ///    symbol 1
 298 ///    symbol 2
 299 ///    ...
 300 ///    symbol N
 301 ///
 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
 306 ///    ...
 307 ///    location_offset_N: number_of_samples
 308 ///
 309 /// Function names must be mangled in order for the profile loader to
 310 /// match them in the current translation unit.
 311 ///
 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.
 316 ///
 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
 320 /// inefficient.
 321 void SampleModuleProfile::loadText() {
 322   ExternalProfileTextLoader Loader(Filename);
 323
 324   // Read the symbol table.
 325   StringRef Line = Loader.readLine();
 326   if (Line != "symbol table")
 327     Loader.reportParseError("Expected 'symbol table', found " + Line);
 328   int NumSymbols;
 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();
 334
 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 " +
 345                               Line);
 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);
 355     unsigned I;
 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);
 365     }
 366
 367     if (I < NumSampledLines)
 368       Loader.reportParseError("Unexpected end of file");
 369   }
 370 }
 371
 372 char SampleProfileLoader::ID = 0;
 373 INITIALIZE_PASS(SampleProfileLoader, "sample-profile", "Sample Profile loader",
 374                 false, false)
 375
 376 bool SampleProfileLoader::doInitialization(Module &M) {
 377   Profiler.reset(new SampleModuleProfile(Filename));
 378   Profiler->loadText();
 379   return true;
 380 }
 381
 382 FunctionPass *llvm::createSampleProfileLoaderPass() {
 383   return new SampleProfileLoader(SampleProfileFile);
 384 }
 385
 386 FunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) {
 387   return new SampleProfileLoader(Name);
 388 }
 389
 390 /// \brief Get the weight for an instruction.
 391 ///
 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.
 397 ///
 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.
 401 ///
 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);
 408 }
 409
 410 /// \brief Compute the weight of a basic block.
 411 ///
 412 /// The weight of basic block \p B is the maximum weight of all the
 413 /// instructions in B.
 414 ///
 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
 419 ///     function.
 420 ///
 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));
 428   if (!Entry.second)
 429     return Entry.first->second;
 430
 431   // Otherwise, compute and cache B's weight.
 432   uint32_t Weight = 0;
 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)
 436       Weight = InstWeight;
 437   }
 438   Entry.first->second = Weight;
 439   return Weight;
 440 }
 441
 442 /// \brief Generate branch weight metadata for all branches in \p F.
 443 ///
 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.
 447 ///
 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.
 451 ///
 452 /// Once all the branch weights are computed, we emit the MD_prof
 453 /// metadata on B using the computed values.
 454 ///
 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());
 460
 461   // Clear the block weights cache.
 462   BlockWeights.clear();
 463
 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) {
 467     BasicBlock *B = I;
 468     TerminatorInst *TI = B->getTerminator();
 469     if (TI->getNumSuccessors() == 1)
 470       continue;
 471     if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
 472       continue;
 473
 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);
 480     }
 481
 482     TI->setMetadata(llvm::LLVMContext::MD_prof,
 483                     MDB.createBranchWeights(Weights));
 484     Changed = true;
 485   }
 486
 487   return Changed;
 488 }
 489
 490 bool SampleProfileLoader::runOnFunction(Function &F) {
 491   return Profiler->getProfile(F).emitAnnotations(F);
 492 }