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>
44using namespace llvm;
45
46#define DEBUG_TYPE "insert-gcov-profiling"
47
48static cl::opt<std::string>
49DefaultGCOVVersion("default-gcov-version", cl::init("402*"), cl::Hidden,
50                   cl::ValueRequired);
51static cl::opt<bool> DefaultExitBlockBeforeBody("gcov-exit-block-before-body",
52                                                cl::init(false), cl::Hidden);
53
54GCOVOptions 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
71namespace {
72class GCOVFunction;
73
74class GCOVProfiler {
75public:
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
88private:
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
135class GCOVProfilerLegacyPass : public ModulePass {
136public:
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
148private:
149  GCOVProfiler Profiler;
150};
151}
152
153char GCOVProfilerLegacyPass::ID = 0;
154INITIALIZE_PASS(GCOVProfilerLegacyPass, "insert-gcov-profiling",
155                "Insert instrumentation for GCOV profiling", false, false)
156
157ModulePass *llvm::createGCOVProfilerPass(const GCOVOptions &Options) {
158  return new GCOVProfilerLegacyPass(Options);
159}
160
161static StringRef getFunctionName(const DISubprogram *SP) {
162  if (!SP->getLinkageName().empty())
163    return SP->getLinkageName();
164  return SP->getName();
165}
166
167namespace {
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
428std::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
454bool 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
463PreservedAnalyses 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
474static 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
496void 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
585bool 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.
719GlobalVariable *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
765Constant *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
775Constant *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
786Constant *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
798Constant *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
807Constant *GCOVProfiler::getSummaryInfoFunc() {
808  FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
809  return M->getOrInsertFunction("llvm_gcda_summary_info", FTy);
810}
811
812Constant *GCOVProfiler::getEndFileFunc() {
813  FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
814  return M->getOrInsertFunction("llvm_gcda_end_file", FTy);
815}
816
817GlobalVariable *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
830Function *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
894void 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
945Function *GCOVProfiler::
946insertFlush(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}
986