contrib/llvm/lib/Transforms/Instrumentation/GCOVProfiling.cpp

   1 //===- GCOVProfiling.cpp - Insert edge counters for gcov profiling --------===//
   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 pass implements GCOV-style profiling. When this pass is run it emits
  11 // "gcno" files next to the existing source, and instruments the code that runs
  12 // to records the edges between blocks that run and emit a complementary "gcda"
  13 // file on exit.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/Hashing.h"
  19 #include "llvm/ADT/STLExtras.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/ADT/StringExtras.h"
  22 #include "llvm/ADT/StringMap.h"
  23 #include "llvm/ADT/UniqueVector.h"
  24 #include "llvm/IR/DebugInfo.h"
  25 #include "llvm/IR/DebugLoc.h"
  26 #include "llvm/IR/IRBuilder.h"
  27 #include "llvm/IR/InstIterator.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/IntrinsicInst.h"
  30 #include "llvm/IR/Module.h"
  31 #include "llvm/Pass.h"
  32 #include "llvm/Support/CommandLine.h"
  33 #include "llvm/Support/Debug.h"
  34 #include "llvm/Support/FileSystem.h"
  35 #include "llvm/Support/Path.h"
  36 #include "llvm/Support/raw_ostream.h"
  37 #include "llvm/Transforms/GCOVProfiler.h"
  38 #include "llvm/Transforms/Instrumentation.h"
  39 #include "llvm/Transforms/Utils/ModuleUtils.h"
  40 #include <algorithm>
  41 #include <memory>
  42 #include <string>
  43 #include <utility>
  44 using namespace llvm;
  45
  46 #define DEBUG_TYPE "insert-gcov-profiling"
  47
  48 static cl::opt<std::string>
  49 DefaultGCOVVersion("default-gcov-version", cl::init("402*"), cl::Hidden,
  50                    cl::ValueRequired);
  51 static cl::opt<bool> DefaultExitBlockBeforeBody("gcov-exit-block-before-body",
  52                                                 cl::init(false), cl::Hidden);
  53
  54 GCOVOptions GCOVOptions::getDefault() {
  55   GCOVOptions Options;
  56   Options.EmitNotes = true;
  57   Options.EmitData = true;
  58   Options.UseCfgChecksum = false;
  59   Options.NoRedZone = false;
  60   Options.FunctionNamesInData = true;
  61   Options.ExitBlockBeforeBody = DefaultExitBlockBeforeBody;
  62
  63   if (DefaultGCOVVersion.size() != 4) {
  64     llvm::report_fatal_error(std::string("Invalid -default-gcov-version: ") +
  65                              DefaultGCOVVersion);
  66   }
  67   memcpy(Options.Version, DefaultGCOVVersion.c_str(), 4);
  68   return Options;
  69 }
  70
  71 namespace {
  72 class GCOVFunction;
  73
  74 class GCOVProfiler {
  75 public:
  76   GCOVProfiler() : GCOVProfiler(GCOVOptions::getDefault()) {}
  77   GCOVProfiler(const GCOVOptions &Opts) : Options(Opts) {
  78     assert((Options.EmitNotes || Options.EmitData) &&
  79            "GCOVProfiler asked to do nothing?");
  80     ReversedVersion[0] = Options.Version[3];
  81     ReversedVersion[1] = Options.Version[2];
  82     ReversedVersion[2] = Options.Version[1];
  83     ReversedVersion[3] = Options.Version[0];
  84     ReversedVersion[4] = '\0';
  85   }
  86   bool runOnModule(Module &M);
  87
  88 private:
  89   // Create the .gcno files for the Module based on DebugInfo.
  90   void emitProfileNotes();
  91
  92   // Modify the program to track transitions along edges and call into the
  93   // profiling runtime to emit .gcda files when run.
  94   bool emitProfileArcs();
  95
  96   // Get pointers to the functions in the runtime library.
  97   Constant *getStartFileFunc();
  98   Constant *getIncrementIndirectCounterFunc();
  99   Constant *getEmitFunctionFunc();
 100   Constant *getEmitArcsFunc();
 101   Constant *getSummaryInfoFunc();
 102   Constant *getEndFileFunc();
 103
 104   // Create or retrieve an i32 state value that is used to represent the
 105   // pred block number for certain non-trivial edges.
 106   GlobalVariable *getEdgeStateValue();
 107
 108   // Produce a table of pointers to counters, by predecessor and successor
 109   // block number.
 110   GlobalVariable *buildEdgeLookupTable(Function *F, GlobalVariable *Counter,
 111                                        const UniqueVector<BasicBlock *> &Preds,
 112                                        const UniqueVector<BasicBlock *> &Succs);
 113
 114   // Add the function to write out all our counters to the global destructor
 115   // list.
 116   Function *
 117   insertCounterWriteout(ArrayRef<std::pair<GlobalVariable *, MDNode *>>);
 118   Function *insertFlush(ArrayRef<std::pair<GlobalVariable *, MDNode *>>);
 119   void insertIndirectCounterIncrement();
 120
 121   std::string mangleName(const DICompileUnit *CU, const char *NewStem);
 122
 123   GCOVOptions Options;
 124
 125   // Reversed, NUL-terminated copy of Options.Version.
 126   char ReversedVersion[5];
 127   // Checksum, produced by hash of EdgeDestinations
 128   SmallVector<uint32_t, 4> FileChecksums;
 129
 130   Module *M;
 131   LLVMContext *Ctx;
 132   SmallVector<std::unique_ptr<GCOVFunction>, 16> Funcs;
 133 };
 134
 135 class GCOVProfilerLegacyPass : public ModulePass {
 136 public:
 137   static char ID;
 138   GCOVProfilerLegacyPass()
 139       : GCOVProfilerLegacyPass(GCOVOptions::getDefault()) {}
 140   GCOVProfilerLegacyPass(const GCOVOptions &Opts)
 141       : ModulePass(ID), Profiler(Opts) {
 142     initializeGCOVProfilerLegacyPassPass(*PassRegistry::getPassRegistry());
 143   }
 144   const char *getPassName() const override { return "GCOV Profiler"; }
 145
 146   bool runOnModule(Module &M) override { return Profiler.runOnModule(M); }
 147
 148 private:
 149   GCOVProfiler Profiler;
 150 };
 151 }
 152
 153 char GCOVProfilerLegacyPass::ID = 0;
 154 INITIALIZE_PASS(GCOVProfilerLegacyPass, "insert-gcov-profiling",
 155                 "Insert instrumentation for GCOV profiling", false, false)
 156
 157 ModulePass *llvm::createGCOVProfilerPass(const GCOVOptions &Options) {
 158   return new GCOVProfilerLegacyPass(Options);
 159 }
 160
 161 static StringRef getFunctionName(const DISubprogram *SP) {
 162   if (!SP->getLinkageName().empty())
 163     return SP->getLinkageName();
 164   return SP->getName();
 165 }
 166
 167 namespace {
 168   class GCOVRecord {
 169    protected:
 170     static const char *const LinesTag;
 171     static const char *const FunctionTag;
 172     static const char *const BlockTag;
 173     static const char *const EdgeTag;
 174
 175     GCOVRecord() = default;
 176
 177     void writeBytes(const char *Bytes, int Size) {
 178       os->write(Bytes, Size);
 179     }
 180
 181     void write(uint32_t i) {
 182       writeBytes(reinterpret_cast<char*>(&i), 4);
 183     }
 184
 185     // Returns the length measured in 4-byte blocks that will be used to
 186     // represent this string in a GCOV file
 187     static unsigned lengthOfGCOVString(StringRef s) {
 188       // A GCOV string is a length, followed by a NUL, then between 0 and 3 NULs
 189       // padding out to the next 4-byte word. The length is measured in 4-byte
 190       // words including padding, not bytes of actual string.
 191       return (s.size() / 4) + 1;
 192     }
 193
 194     void writeGCOVString(StringRef s) {
 195       uint32_t Len = lengthOfGCOVString(s);
 196       write(Len);
 197       writeBytes(s.data(), s.size());
 198
 199       // Write 1 to 4 bytes of NUL padding.
 200       assert((unsigned)(4 - (s.size() % 4)) > 0);
 201       assert((unsigned)(4 - (s.size() % 4)) <= 4);
 202       writeBytes("\0\0\0\0", 4 - (s.size() % 4));
 203     }
 204
 205     raw_ostream *os;
 206   };
 207   const char *const GCOVRecord::LinesTag = "\0\0\x45\x01";
 208   const char *const GCOVRecord::FunctionTag = "\0\0\0\1";
 209   const char *const GCOVRecord::BlockTag = "\0\0\x41\x01";
 210   const char *const GCOVRecord::EdgeTag = "\0\0\x43\x01";
 211
 212   class GCOVFunction;
 213   class GCOVBlock;
 214
 215   // Constructed only by requesting it from a GCOVBlock, this object stores a
 216   // list of line numbers and a single filename, representing lines that belong
 217   // to the block.
 218   class GCOVLines : public GCOVRecord {
 219    public:
 220     void addLine(uint32_t Line) {
 221       assert(Line != 0 && "Line zero is not a valid real line number.");
 222       Lines.push_back(Line);
 223     }
 224
 225     uint32_t length() const {
 226       // Here 2 = 1 for string length + 1 for '0' id#.
 227       return lengthOfGCOVString(Filename) + 2 + Lines.size();
 228     }
 229
 230     void writeOut() {
 231       write(0);
 232       writeGCOVString(Filename);
 233       for (int i = 0, e = Lines.size(); i != e; ++i)
 234         write(Lines[i]);
 235     }
 236
 237     GCOVLines(StringRef F, raw_ostream *os)
 238       : Filename(F) {
 239       this->os = os;
 240     }
 241
 242    private:
 243     StringRef Filename;
 244     SmallVector<uint32_t, 32> Lines;
 245   };
 246
 247
 248   // Represent a basic block in GCOV. Each block has a unique number in the
 249   // function, number of lines belonging to each block, and a set of edges to
 250   // other blocks.
 251   class GCOVBlock : public GCOVRecord {
 252    public:
 253     GCOVLines &getFile(StringRef Filename) {
 254       GCOVLines *&Lines = LinesByFile[Filename];
 255       if (!Lines) {
 256         Lines = new GCOVLines(Filename, os);
 257       }
 258       return *Lines;
 259     }
 260
 261     void addEdge(GCOVBlock &Successor) {
 262       OutEdges.push_back(&Successor);
 263     }
 264
 265     void writeOut() {
 266       uint32_t Len = 3;
 267       SmallVector<StringMapEntry<GCOVLines *> *, 32> SortedLinesByFile;
 268       for (auto &I : LinesByFile) {
 269         Len += I.second->length();
 270         SortedLinesByFile.push_back(&I);
 271       }
 272
 273       writeBytes(LinesTag, 4);
 274       write(Len);
 275       write(Number);
 276
 277       std::sort(SortedLinesByFile.begin(), SortedLinesByFile.end(),
 278                 [](StringMapEntry<GCOVLines *> *LHS,
 279                    StringMapEntry<GCOVLines *> *RHS) {
 280         return LHS->getKey() < RHS->getKey();
 281       });
 282       for (auto &I : SortedLinesByFile)
 283         I->getValue()->writeOut();
 284       write(0);
 285       write(0);
 286     }
 287
 288     ~GCOVBlock() {
 289       DeleteContainerSeconds(LinesByFile);
 290     }
 291
 292     GCOVBlock(const GCOVBlock &RHS) : GCOVRecord(RHS), Number(RHS.Number) {
 293       // Only allow copy before edges and lines have been added. After that,
 294       // there are inter-block pointers (eg: edges) that won't take kindly to
 295       // blocks being copied or moved around.
 296       assert(LinesByFile.empty());
 297       assert(OutEdges.empty());
 298     }
 299
 300    private:
 301     friend class GCOVFunction;
 302
 303     GCOVBlock(uint32_t Number, raw_ostream *os)
 304         : Number(Number) {
 305       this->os = os;
 306     }
 307
 308     uint32_t Number;
 309     StringMap<GCOVLines *> LinesByFile;
 310     SmallVector<GCOVBlock *, 4> OutEdges;
 311   };
 312
 313   // A function has a unique identifier, a checksum (we leave as zero) and a
 314   // set of blocks and a map of edges between blocks. This is the only GCOV
 315   // object users can construct, the blocks and lines will be rooted here.
 316   class GCOVFunction : public GCOVRecord {
 317    public:
 318      GCOVFunction(const DISubprogram *SP, Function *F, raw_ostream *os,
 319                   uint32_t Ident, bool UseCfgChecksum, bool ExitBlockBeforeBody)
 320          : SP(SP), Ident(Ident), UseCfgChecksum(UseCfgChecksum), CfgChecksum(0),
 321            ReturnBlock(1, os) {
 322       this->os = os;
 323
 324       DEBUG(dbgs() << "Function: " << getFunctionName(SP) << "\n");
 325
 326       uint32_t i = 0;
 327       for (auto &BB : *F) {
 328         // Skip index 1 if it's assigned to the ReturnBlock.
 329         if (i == 1 && ExitBlockBeforeBody)
 330           ++i;
 331         Blocks.insert(std::make_pair(&BB, GCOVBlock(i++, os)));
 332       }
 333       if (!ExitBlockBeforeBody)
 334         ReturnBlock.Number = i;
 335
 336       std::string FunctionNameAndLine;
 337       raw_string_ostream FNLOS(FunctionNameAndLine);
 338       FNLOS << getFunctionName(SP) << SP->getLine();
 339       FNLOS.flush();
 340       FuncChecksum = hash_value(FunctionNameAndLine);
 341     }
 342
 343     GCOVBlock &getBlock(BasicBlock *BB) {
 344       return Blocks.find(BB)->second;
 345     }
 346
 347     GCOVBlock &getReturnBlock() {
 348       return ReturnBlock;
 349     }
 350
 351     std::string getEdgeDestinations() {
 352       std::string EdgeDestinations;
 353       raw_string_ostream EDOS(EdgeDestinations);
 354       Function *F = Blocks.begin()->first->getParent();
 355       for (BasicBlock &I : *F) {
 356         GCOVBlock &Block = getBlock(&I);
 357         for (int i = 0, e = Block.OutEdges.size(); i != e; ++i)
 358           EDOS << Block.OutEdges[i]->Number;
 359       }
 360       return EdgeDestinations;
 361     }
 362
 363     uint32_t getFuncChecksum() {
 364       return FuncChecksum;
 365     }
 366
 367     void setCfgChecksum(uint32_t Checksum) {
 368       CfgChecksum = Checksum;
 369     }
 370
 371     void writeOut() {
 372       writeBytes(FunctionTag, 4);
 373       uint32_t BlockLen = 1 + 1 + 1 + lengthOfGCOVString(getFunctionName(SP)) +
 374                           1 + lengthOfGCOVString(SP->getFilename()) + 1;
 375       if (UseCfgChecksum)
 376         ++BlockLen;
 377       write(BlockLen);
 378       write(Ident);
 379       write(FuncChecksum);
 380       if (UseCfgChecksum)
 381         write(CfgChecksum);
 382       writeGCOVString(getFunctionName(SP));
 383       writeGCOVString(SP->getFilename());
 384       write(SP->getLine());
 385
 386       // Emit count of blocks.
 387       writeBytes(BlockTag, 4);
 388       write(Blocks.size() + 1);
 389       for (int i = 0, e = Blocks.size() + 1; i != e; ++i) {
 390         write(0);  // No flags on our blocks.
 391       }
 392       DEBUG(dbgs() << Blocks.size() << " blocks.\n");
 393
 394       // Emit edges between blocks.
 395       if (Blocks.empty()) return;
 396       Function *F = Blocks.begin()->first->getParent();
 397       for (BasicBlock &I : *F) {
 398         GCOVBlock &Block = getBlock(&I);
 399         if (Block.OutEdges.empty()) continue;
 400
 401         writeBytes(EdgeTag, 4);
 402         write(Block.OutEdges.size() * 2 + 1);
 403         write(Block.Number);
 404         for (int i = 0, e = Block.OutEdges.size(); i != e; ++i) {
 405           DEBUG(dbgs() << Block.Number << " -> " << Block.OutEdges[i]->Number
 406                        << "\n");
 407           write(Block.OutEdges[i]->Number);
 408           write(0);  // no flags
 409         }
 410       }
 411
 412       // Emit lines for each block.
 413       for (BasicBlock &I : *F)
 414         getBlock(&I).writeOut();
 415     }
 416
 417    private:
 418      const DISubprogram *SP;
 419     uint32_t Ident;
 420     uint32_t FuncChecksum;
 421     bool UseCfgChecksum;
 422     uint32_t CfgChecksum;
 423     DenseMap<BasicBlock *, GCOVBlock> Blocks;
 424     GCOVBlock ReturnBlock;
 425   };
 426 }
 427
 428 std::string GCOVProfiler::mangleName(const DICompileUnit *CU,
 429                                      const char *NewStem) {
 430   if (NamedMDNode *GCov = M->getNamedMetadata("llvm.gcov")) {
 431     for (int i = 0, e = GCov->getNumOperands(); i != e; ++i) {
 432       MDNode *N = GCov->getOperand(i);
 433       if (N->getNumOperands() != 2) continue;
 434       MDString *GCovFile = dyn_cast<MDString>(N->getOperand(0));
 435       MDNode *CompileUnit = dyn_cast<MDNode>(N->getOperand(1));
 436       if (!GCovFile || !CompileUnit) continue;
 437       if (CompileUnit == CU) {
 438         SmallString<128> Filename = GCovFile->getString();
 439         sys::path::replace_extension(Filename, NewStem);
 440         return Filename.str();
 441       }
 442     }
 443   }
 444
 445   SmallString<128> Filename = CU->getFilename();
 446   sys::path::replace_extension(Filename, NewStem);
 447   StringRef FName = sys::path::filename(Filename);
 448   SmallString<128> CurPath;
 449   if (sys::fs::current_path(CurPath)) return FName;
 450   sys::path::append(CurPath, FName);
 451   return CurPath.str();
 452 }
 453
 454 bool GCOVProfiler::runOnModule(Module &M) {
 455   this->M = &M;
 456   Ctx = &M.getContext();
 457
 458   if (Options.EmitNotes) emitProfileNotes();
 459   if (Options.EmitData) return emitProfileArcs();
 460   return false;
 461 }
 462
 463 PreservedAnalyses GCOVProfilerPass::run(Module &M,
 464                                         AnalysisManager<Module> &AM) {
 465
 466   GCOVProfiler Profiler(GCOVOpts);
 467
 468   if (!Profiler.runOnModule(M))
 469     return PreservedAnalyses::all();
 470
 471   return PreservedAnalyses::none();
 472 }
 473
 474 static bool functionHasLines(Function &F) {
 475   // Check whether this function actually has any source lines. Not only
 476   // do these waste space, they also can crash gcov.
 477   for (auto &BB : F) {
 478     for (auto &I : BB) {
 479       // Debug intrinsic locations correspond to the location of the
 480       // declaration, not necessarily any statements or expressions.
 481       if (isa<DbgInfoIntrinsic>(&I)) continue;
 482
 483       const DebugLoc &Loc = I.getDebugLoc();
 484       if (!Loc)
 485         continue;
 486
 487       // Artificial lines such as calls to the global constructors.
 488       if (Loc.getLine() == 0) continue;
 489
 490       return true;
 491     }
 492   }
 493   return false;
 494 }
 495
 496 void GCOVProfiler::emitProfileNotes() {
 497   NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu");
 498   if (!CU_Nodes) return;
 499
 500   for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) {
 501     // Each compile unit gets its own .gcno file. This means that whether we run
 502     // this pass over the original .o's as they're produced, or run it after
 503     // LTO, we'll generate the same .gcno files.
 504
 505     auto *CU = cast<DICompileUnit>(CU_Nodes->getOperand(i));
 506
 507     // Skip module skeleton (and module) CUs.
 508     if (CU->getDWOId())
 509       continue;
 510
 511     std::error_code EC;
 512     raw_fd_ostream out(mangleName(CU, "gcno"), EC, sys::fs::F_None);
 513     std::string EdgeDestinations;
 514
 515     unsigned FunctionIdent = 0;
 516     for (auto &F : M->functions()) {
 517       DISubprogram *SP = F.getSubprogram();
 518       if (!SP) continue;
 519       if (!functionHasLines(F)) continue;
 520
 521       // gcov expects every function to start with an entry block that has a
 522       // single successor, so split the entry block to make sure of that.
 523       BasicBlock &EntryBlock = F.getEntryBlock();
 524       BasicBlock::iterator It = EntryBlock.begin();
 525       while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It))
 526         ++It;
 527       EntryBlock.splitBasicBlock(It);
 528
 529       Funcs.push_back(make_unique<GCOVFunction>(SP, &F, &out, FunctionIdent++,
 530                                                 Options.UseCfgChecksum,
 531                                                 Options.ExitBlockBeforeBody));
 532       GCOVFunction &Func = *Funcs.back();
 533
 534       for (auto &BB : F) {
 535         GCOVBlock &Block = Func.getBlock(&BB);
 536         TerminatorInst *TI = BB.getTerminator();
 537         if (int successors = TI->getNumSuccessors()) {
 538           for (int i = 0; i != successors; ++i) {
 539             Block.addEdge(Func.getBlock(TI->getSuccessor(i)));
 540           }
 541         } else if (isa<ReturnInst>(TI)) {
 542           Block.addEdge(Func.getReturnBlock());
 543         }
 544
 545         uint32_t Line = 0;
 546         for (auto &I : BB) {
 547           // Debug intrinsic locations correspond to the location of the
 548           // declaration, not necessarily any statements or expressions.
 549           if (isa<DbgInfoIntrinsic>(&I)) continue;
 550
 551           const DebugLoc &Loc = I.getDebugLoc();
 552           if (!Loc)
 553             continue;
 554
 555           // Artificial lines such as calls to the global constructors.
 556           if (Loc.getLine() == 0) continue;
 557
 558           if (Line == Loc.getLine()) continue;
 559           Line = Loc.getLine();
 560           if (SP != getDISubprogram(Loc.getScope()))
 561             continue;
 562
 563           GCOVLines &Lines = Block.getFile(SP->getFilename());
 564           Lines.addLine(Loc.getLine());
 565         }
 566       }
 567       EdgeDestinations += Func.getEdgeDestinations();
 568     }
 569
 570     FileChecksums.push_back(hash_value(EdgeDestinations));
 571     out.write("oncg", 4);
 572     out.write(ReversedVersion, 4);
 573     out.write(reinterpret_cast<char*>(&FileChecksums.back()), 4);
 574
 575     for (auto &Func : Funcs) {
 576       Func->setCfgChecksum(FileChecksums.back());
 577       Func->writeOut();
 578     }
 579
 580     out.write("\0\0\0\0\0\0\0\0", 8);  // EOF
 581     out.close();
 582   }
 583 }
 584
 585 bool GCOVProfiler::emitProfileArcs() {
 586   NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu");
 587   if (!CU_Nodes) return false;
 588
 589   bool Result = false;
 590   bool InsertIndCounterIncrCode = false;
 591   for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) {
 592     SmallVector<std::pair<GlobalVariable *, MDNode *>, 8> CountersBySP;
 593     for (auto &F : M->functions()) {
 594       DISubprogram *SP = F.getSubprogram();
 595       if (!SP) continue;
 596       if (!functionHasLines(F)) continue;
 597       if (!Result) Result = true;
 598       unsigned Edges = 0;
 599       for (auto &BB : F) {
 600         TerminatorInst *TI = BB.getTerminator();
 601         if (isa<ReturnInst>(TI))
 602           ++Edges;
 603         else
 604           Edges += TI->getNumSuccessors();
 605       }
 606
 607       ArrayType *CounterTy =
 608         ArrayType::get(Type::getInt64Ty(*Ctx), Edges);
 609       GlobalVariable *Counters =
 610         new GlobalVariable(*M, CounterTy, false,
 611                            GlobalValue::InternalLinkage,
 612                            Constant::getNullValue(CounterTy),
 613                            "__llvm_gcov_ctr");
 614       CountersBySP.push_back(std::make_pair(Counters, SP));
 615
 616       UniqueVector<BasicBlock *> ComplexEdgePreds;
 617       UniqueVector<BasicBlock *> ComplexEdgeSuccs;
 618
 619       unsigned Edge = 0;
 620       for (auto &BB : F) {
 621         TerminatorInst *TI = BB.getTerminator();
 622         int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors();
 623         if (Successors) {
 624           if (Successors == 1) {
 625             IRBuilder<> Builder(&*BB.getFirstInsertionPt());
 626             Value *Counter = Builder.CreateConstInBoundsGEP2_64(Counters, 0,
 627                                                                 Edge);
 628             Value *Count = Builder.CreateLoad(Counter);
 629             Count = Builder.CreateAdd(Count, Builder.getInt64(1));
 630             Builder.CreateStore(Count, Counter);
 631           } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 632             IRBuilder<> Builder(BI);
 633             Value *Sel = Builder.CreateSelect(BI->getCondition(),
 634                                               Builder.getInt64(Edge),
 635                                               Builder.getInt64(Edge + 1));
 636             Value *Counter = Builder.CreateInBoundsGEP(
 637                 Counters->getValueType(), Counters, {Builder.getInt64(0), Sel});
 638             Value *Count = Builder.CreateLoad(Counter);
 639             Count = Builder.CreateAdd(Count, Builder.getInt64(1));
 640             Builder.CreateStore(Count, Counter);
 641           } else {
 642             ComplexEdgePreds.insert(&BB);
 643             for (int i = 0; i != Successors; ++i)
 644               ComplexEdgeSuccs.insert(TI->getSuccessor(i));
 645           }
 646
 647           Edge += Successors;
 648         }
 649       }
 650
 651       if (!ComplexEdgePreds.empty()) {
 652         GlobalVariable *EdgeTable =
 653           buildEdgeLookupTable(&F, Counters,
 654                                ComplexEdgePreds, ComplexEdgeSuccs);
 655         GlobalVariable *EdgeState = getEdgeStateValue();
 656
 657         for (int i = 0, e = ComplexEdgePreds.size(); i != e; ++i) {
 658           IRBuilder<> Builder(&*ComplexEdgePreds[i + 1]->getFirstInsertionPt());
 659           Builder.CreateStore(Builder.getInt32(i), EdgeState);
 660         }
 661
 662         for (int i = 0, e = ComplexEdgeSuccs.size(); i != e; ++i) {
 663           // Call runtime to perform increment.
 664           IRBuilder<> Builder(&*ComplexEdgeSuccs[i + 1]->getFirstInsertionPt());
 665           Value *CounterPtrArray =
 666             Builder.CreateConstInBoundsGEP2_64(EdgeTable, 0,
 667                                                i * ComplexEdgePreds.size());
 668
 669           // Build code to increment the counter.
 670           InsertIndCounterIncrCode = true;
 671           Builder.CreateCall(getIncrementIndirectCounterFunc(),
 672                              {EdgeState, CounterPtrArray});
 673         }
 674       }
 675     }
 676
 677     Function *WriteoutF = insertCounterWriteout(CountersBySP);
 678     Function *FlushF = insertFlush(CountersBySP);
 679
 680     // Create a small bit of code that registers the "__llvm_gcov_writeout" to
 681     // be executed at exit and the "__llvm_gcov_flush" function to be executed
 682     // when "__gcov_flush" is called.
 683     FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
 684     Function *F = Function::Create(FTy, GlobalValue::InternalLinkage,
 685                                    "__llvm_gcov_init", M);
 686     F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 687     F->setLinkage(GlobalValue::InternalLinkage);
 688     F->addFnAttr(Attribute::NoInline);
 689     if (Options.NoRedZone)
 690       F->addFnAttr(Attribute::NoRedZone);
 691
 692     BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", F);
 693     IRBuilder<> Builder(BB);
 694
 695     FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
 696     Type *Params[] = {
 697       PointerType::get(FTy, 0),
 698       PointerType::get(FTy, 0)
 699     };
 700     FTy = FunctionType::get(Builder.getVoidTy(), Params, false);
 701
 702     // Initialize the environment and register the local writeout and flush
 703     // functions.
 704     Constant *GCOVInit = M->getOrInsertFunction("llvm_gcov_init", FTy);
 705     Builder.CreateCall(GCOVInit, {WriteoutF, FlushF});
 706     Builder.CreateRetVoid();
 707
 708     appendToGlobalCtors(*M, F, 0);
 709   }
 710
 711   if (InsertIndCounterIncrCode)
 712     insertIndirectCounterIncrement();
 713
 714   return Result;
 715 }
 716
 717 // All edges with successors that aren't branches are "complex", because it
 718 // requires complex logic to pick which counter to update.
 719 GlobalVariable *GCOVProfiler::buildEdgeLookupTable(
 720     Function *F,
 721     GlobalVariable *Counters,
 722     const UniqueVector<BasicBlock *> &Preds,
 723     const UniqueVector<BasicBlock *> &Succs) {
 724   // TODO: support invoke, threads. We rely on the fact that nothing can modify
 725   // the whole-Module pred edge# between the time we set it and the time we next
 726   // read it. Threads and invoke make this untrue.
 727
 728   // emit [(succs * preds) x i64*], logically [succ x [pred x i64*]].
 729   size_t TableSize = Succs.size() * Preds.size();
 730   Type *Int64PtrTy = Type::getInt64PtrTy(*Ctx);
 731   ArrayType *EdgeTableTy = ArrayType::get(Int64PtrTy, TableSize);
 732
 733   std::unique_ptr<Constant * []> EdgeTable(new Constant *[TableSize]);
 734   Constant *NullValue = Constant::getNullValue(Int64PtrTy);
 735   for (size_t i = 0; i != TableSize; ++i)
 736     EdgeTable[i] = NullValue;
 737
 738   unsigned Edge = 0;
 739   for (BasicBlock &BB : *F) {
 740     TerminatorInst *TI = BB.getTerminator();
 741     int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors();
 742     if (Successors > 1 && !isa<BranchInst>(TI) && !isa<ReturnInst>(TI)) {
 743       for (int i = 0; i != Successors; ++i) {
 744         BasicBlock *Succ = TI->getSuccessor(i);
 745         IRBuilder<> Builder(Succ);
 746         Value *Counter = Builder.CreateConstInBoundsGEP2_64(Counters, 0,
 747                                                             Edge + i);
 748         EdgeTable[((Succs.idFor(Succ) - 1) * Preds.size()) +
 749                   (Preds.idFor(&BB) - 1)] = cast<Constant>(Counter);
 750       }
 751     }
 752     Edge += Successors;
 753   }
 754
 755   GlobalVariable *EdgeTableGV =
 756       new GlobalVariable(
 757           *M, EdgeTableTy, true, GlobalValue::InternalLinkage,
 758           ConstantArray::get(EdgeTableTy,
 759                              makeArrayRef(&EdgeTable[0],TableSize)),
 760           "__llvm_gcda_edge_table");
 761   EdgeTableGV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 762   return EdgeTableGV;
 763 }
 764
 765 Constant *GCOVProfiler::getStartFileFunc() {
 766   Type *Args[] = {
 767     Type::getInt8PtrTy(*Ctx),  // const char *orig_filename
 768     Type::getInt8PtrTy(*Ctx),  // const char version[4]
 769     Type::getInt32Ty(*Ctx),    // uint32_t checksum
 770   };
 771   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), Args, false);
 772   return M->getOrInsertFunction("llvm_gcda_start_file", FTy);
 773 }
 774
 775 Constant *GCOVProfiler::getIncrementIndirectCounterFunc() {
 776   Type *Int32Ty = Type::getInt32Ty(*Ctx);
 777   Type *Int64Ty = Type::getInt64Ty(*Ctx);
 778   Type *Args[] = {
 779     Int32Ty->getPointerTo(),                // uint32_t *predecessor
 780     Int64Ty->getPointerTo()->getPointerTo() // uint64_t **counters
 781   };
 782   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), Args, false);
 783   return M->getOrInsertFunction("__llvm_gcov_indirect_counter_increment", FTy);
 784 }
 785
 786 Constant *GCOVProfiler::getEmitFunctionFunc() {
 787   Type *Args[] = {
 788     Type::getInt32Ty(*Ctx),    // uint32_t ident
 789     Type::getInt8PtrTy(*Ctx),  // const char *function_name
 790     Type::getInt32Ty(*Ctx),    // uint32_t func_checksum
 791     Type::getInt8Ty(*Ctx),     // uint8_t use_extra_checksum
 792     Type::getInt32Ty(*Ctx),    // uint32_t cfg_checksum
 793   };
 794   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), Args, false);
 795   return M->getOrInsertFunction("llvm_gcda_emit_function", FTy);
 796 }
 797
 798 Constant *GCOVProfiler::getEmitArcsFunc() {
 799   Type *Args[] = {
 800     Type::getInt32Ty(*Ctx),     // uint32_t num_counters
 801     Type::getInt64PtrTy(*Ctx),  // uint64_t *counters
 802   };
 803   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), Args, false);
 804   return M->getOrInsertFunction("llvm_gcda_emit_arcs", FTy);
 805 }
 806
 807 Constant *GCOVProfiler::getSummaryInfoFunc() {
 808   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
 809   return M->getOrInsertFunction("llvm_gcda_summary_info", FTy);
 810 }
 811
 812 Constant *GCOVProfiler::getEndFileFunc() {
 813   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
 814   return M->getOrInsertFunction("llvm_gcda_end_file", FTy);
 815 }
 816
 817 GlobalVariable *GCOVProfiler::getEdgeStateValue() {
 818   GlobalVariable *GV = M->getGlobalVariable("__llvm_gcov_global_state_pred");
 819   if (!GV) {
 820     GV = new GlobalVariable(*M, Type::getInt32Ty(*Ctx), false,
 821                             GlobalValue::InternalLinkage,
 822                             ConstantInt::get(Type::getInt32Ty(*Ctx),
 823                                              0xffffffff),
 824                             "__llvm_gcov_global_state_pred");
 825     GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 826   }
 827   return GV;
 828 }
 829
 830 Function *GCOVProfiler::insertCounterWriteout(
 831     ArrayRef<std::pair<GlobalVariable *, MDNode *> > CountersBySP) {
 832   FunctionType *WriteoutFTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
 833   Function *WriteoutF = M->getFunction("__llvm_gcov_writeout");
 834   if (!WriteoutF)
 835     WriteoutF = Function::Create(WriteoutFTy, GlobalValue::InternalLinkage,
 836                                  "__llvm_gcov_writeout", M);
 837   WriteoutF->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 838   WriteoutF->addFnAttr(Attribute::NoInline);
 839   if (Options.NoRedZone)
 840     WriteoutF->addFnAttr(Attribute::NoRedZone);
 841
 842   BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", WriteoutF);
 843   IRBuilder<> Builder(BB);
 844
 845   Constant *StartFile = getStartFileFunc();
 846   Constant *EmitFunction = getEmitFunctionFunc();
 847   Constant *EmitArcs = getEmitArcsFunc();
 848   Constant *SummaryInfo = getSummaryInfoFunc();
 849   Constant *EndFile = getEndFileFunc();
 850
 851   NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu");
 852   if (CU_Nodes) {
 853     for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) {
 854       auto *CU = cast<DICompileUnit>(CU_Nodes->getOperand(i));
 855
 856       // Skip module skeleton (and module) CUs.
 857       if (CU->getDWOId())
 858         continue;
 859
 860       std::string FilenameGcda = mangleName(CU, "gcda");
 861       uint32_t CfgChecksum = FileChecksums.empty() ? 0 : FileChecksums[i];
 862       Builder.CreateCall(StartFile,
 863                          {Builder.CreateGlobalStringPtr(FilenameGcda),
 864                           Builder.CreateGlobalStringPtr(ReversedVersion),
 865                           Builder.getInt32(CfgChecksum)});
 866       for (unsigned j = 0, e = CountersBySP.size(); j != e; ++j) {
 867         auto *SP = cast_or_null<DISubprogram>(CountersBySP[j].second);
 868         uint32_t FuncChecksum = Funcs.empty() ? 0 : Funcs[j]->getFuncChecksum();
 869         Builder.CreateCall(
 870             EmitFunction,
 871             {Builder.getInt32(j),
 872              Options.FunctionNamesInData
 873                  ? Builder.CreateGlobalStringPtr(getFunctionName(SP))
 874                  : Constant::getNullValue(Builder.getInt8PtrTy()),
 875              Builder.getInt32(FuncChecksum),
 876              Builder.getInt8(Options.UseCfgChecksum),
 877              Builder.getInt32(CfgChecksum)});
 878
 879         GlobalVariable *GV = CountersBySP[j].first;
 880         unsigned Arcs =
 881           cast<ArrayType>(GV->getValueType())->getNumElements();
 882         Builder.CreateCall(EmitArcs, {Builder.getInt32(Arcs),
 883                                       Builder.CreateConstGEP2_64(GV, 0, 0)});
 884       }
 885       Builder.CreateCall(SummaryInfo, {});
 886       Builder.CreateCall(EndFile, {});
 887     }
 888   }
 889
 890   Builder.CreateRetVoid();
 891   return WriteoutF;
 892 }
 893
 894 void GCOVProfiler::insertIndirectCounterIncrement() {
 895   Function *Fn =
 896     cast<Function>(GCOVProfiler::getIncrementIndirectCounterFunc());
 897   Fn->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 898   Fn->setLinkage(GlobalValue::InternalLinkage);
 899   Fn->addFnAttr(Attribute::NoInline);
 900   if (Options.NoRedZone)
 901     Fn->addFnAttr(Attribute::NoRedZone);
 902
 903   // Create basic blocks for function.
 904   BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", Fn);
 905   IRBuilder<> Builder(BB);
 906
 907   BasicBlock *PredNotNegOne = BasicBlock::Create(*Ctx, "", Fn);
 908   BasicBlock *CounterEnd = BasicBlock::Create(*Ctx, "", Fn);
 909   BasicBlock *Exit = BasicBlock::Create(*Ctx, "exit", Fn);
 910
 911   // uint32_t pred = *predecessor;
 912   // if (pred == 0xffffffff) return;
 913   Argument *Arg = &*Fn->arg_begin();
 914   Arg->setName("predecessor");
 915   Value *Pred = Builder.CreateLoad(Arg, "pred");
 916   Value *Cond = Builder.CreateICmpEQ(Pred, Builder.getInt32(0xffffffff));
 917   BranchInst::Create(Exit, PredNotNegOne, Cond, BB);
 918
 919   Builder.SetInsertPoint(PredNotNegOne);
 920
 921   // uint64_t *counter = counters[pred];
 922   // if (!counter) return;
 923   Value *ZExtPred = Builder.CreateZExt(Pred, Builder.getInt64Ty());
 924   Arg = &*std::next(Fn->arg_begin());
 925   Arg->setName("counters");
 926   Value *GEP = Builder.CreateGEP(Type::getInt64PtrTy(*Ctx), Arg, ZExtPred);
 927   Value *Counter = Builder.CreateLoad(GEP, "counter");
 928   Cond = Builder.CreateICmpEQ(Counter,
 929                               Constant::getNullValue(
 930                                   Builder.getInt64Ty()->getPointerTo()));
 931   Builder.CreateCondBr(Cond, Exit, CounterEnd);
 932
 933   // ++*counter;
 934   Builder.SetInsertPoint(CounterEnd);
 935   Value *Add = Builder.CreateAdd(Builder.CreateLoad(Counter),
 936                                  Builder.getInt64(1));
 937   Builder.CreateStore(Add, Counter);
 938   Builder.CreateBr(Exit);
 939
 940   // Fill in the exit block.
 941   Builder.SetInsertPoint(Exit);
 942   Builder.CreateRetVoid();
 943 }
 944
 945 Function *GCOVProfiler::
 946 insertFlush(ArrayRef<std::pair<GlobalVariable*, MDNode*> > CountersBySP) {
 947   FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
 948   Function *FlushF = M->getFunction("__llvm_gcov_flush");
 949   if (!FlushF)
 950     FlushF = Function::Create(FTy, GlobalValue::InternalLinkage,
 951                               "__llvm_gcov_flush", M);
 952   else
 953     FlushF->setLinkage(GlobalValue::InternalLinkage);
 954   FlushF->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 955   FlushF->addFnAttr(Attribute::NoInline);
 956   if (Options.NoRedZone)
 957     FlushF->addFnAttr(Attribute::NoRedZone);
 958
 959   BasicBlock *Entry = BasicBlock::Create(*Ctx, "entry", FlushF);
 960
 961   // Write out the current counters.
 962   Constant *WriteoutF = M->getFunction("__llvm_gcov_writeout");
 963   assert(WriteoutF && "Need to create the writeout function first!");
 964
 965   IRBuilder<> Builder(Entry);
 966   Builder.CreateCall(WriteoutF, {});
 967
 968   // Zero out the counters.
 969   for (const auto &I : CountersBySP) {
 970     GlobalVariable *GV = I.first;
 971     Constant *Null = Constant::getNullValue(GV->getValueType());
 972     Builder.CreateStore(Null, GV);
 973   }
 974
 975   Type *RetTy = FlushF->getReturnType();
 976   if (RetTy == Type::getVoidTy(*Ctx))
 977     Builder.CreateRetVoid();
 978   else if (RetTy->isIntegerTy())
 979     // Used if __llvm_gcov_flush was implicitly declared.
 980     Builder.CreateRet(ConstantInt::get(RetTy, 0));
 981   else
 982     report_fatal_error("invalid return type for __llvm_gcov_flush");
 983
 984   return FlushF;
 985 }