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