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/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   virtual void dump();
  85   virtual void loadText();
  86   virtual void loadNative() { llvm_unreachable("not implemented"); }
  87   virtual 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 }