GCOVProfiling.cpp revision 7a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efe
1b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//===- GCOVProfiling.cpp - Insert edge counters for gcov profiling --------===//
2b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//
3b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//                      The LLVM Compiler Infrastructure
4b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//
5b1928704201034c785a26296a49f69355eb56a05Nick Lewycky// This file is distributed under the University of Illinois Open Source
6b1928704201034c785a26296a49f69355eb56a05Nick Lewycky// License. See LICENSE.TXT for details.
7b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//
8b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//===----------------------------------------------------------------------===//
9b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//
10b1928704201034c785a26296a49f69355eb56a05Nick Lewycky// This pass implements GCOV-style profiling. When this pass is run it emits
11b1928704201034c785a26296a49f69355eb56a05Nick Lewycky// "gcno" files next to the existing source, and instruments the code that runs
12b1928704201034c785a26296a49f69355eb56a05Nick Lewycky// to records the edges between blocks that run and emit a complementary "gcda"
13b1928704201034c785a26296a49f69355eb56a05Nick Lewycky// file on exit.
14b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//
15b1928704201034c785a26296a49f69355eb56a05Nick Lewycky//===----------------------------------------------------------------------===//
16b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
17b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#define DEBUG_TYPE "insert-gcov-profiling"
18b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
19b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "ProfilingUtils.h"
20b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Transforms/Instrumentation.h"
21b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Analysis/DebugInfo.h"
22b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Module.h"
23b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Pass.h"
24b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Instructions.h"
25b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Support/raw_ostream.h"
26b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Support/Debug.h"
27b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Support/DebugLoc.h"
28b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Support/InstIterator.h"
29b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Support/IRBuilder.h"
30b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/Support/PathV2.h"
31b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/ADT/DenseMap.h"
32b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/ADT/Statistic.h"
33b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/ADT/STLExtras.h"
34b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/ADT/StringExtras.h"
35b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/ADT/StringMap.h"
36b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include "llvm/ADT/UniqueVector.h"
37b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include <string>
38b1928704201034c785a26296a49f69355eb56a05Nick Lewycky#include <utility>
39b1928704201034c785a26296a49f69355eb56a05Nick Lewyckyusing namespace llvm;
40b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
41b1928704201034c785a26296a49f69355eb56a05Nick Lewyckynamespace {
42b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  class GCOVProfiler : public ModulePass {
43b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    bool runOnModule(Module &M);
44b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  public:
45b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    static char ID;
46a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky    GCOVProfiler()
47a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky        : ModulePass(ID), EmitNotes(true), EmitData(true) {
48a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky      initializeGCOVProfilerPass(*PassRegistry::getPassRegistry());
49a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky    }
50a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky    GCOVProfiler(bool EmitNotes, bool EmitData)
51a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky        : ModulePass(ID), EmitNotes(EmitNotes), EmitData(EmitData) {
52a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky      assert((EmitNotes || EmitData) && "GCOVProfiler asked to do nothing?");
53b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      initializeGCOVProfilerPass(*PassRegistry::getPassRegistry());
54b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
55b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    virtual const char *getPassName() const {
56b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      return "GCOV Profiler";
57b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
58b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
59b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  private:
60b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // Create the GCNO files for the Module based on DebugInfo.
611790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void emitGCNO(DebugInfoFinder &DIF);
62b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
630c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky    // Modify the program to track transitions along edges and call into the
640c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky    // profiling runtime to emit .gcda files when run.
651790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    bool emitProfileArcs(DebugInfoFinder &DIF);
660c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky
67b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // Get pointers to the functions in the runtime library.
68b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Constant *getStartFileFunc();
691790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Constant *getIncrementIndirectCounterFunc();
70b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Constant *getEmitFunctionFunc();
71b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Constant *getEmitArcsFunc();
72b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Constant *getEndFileFunc();
73b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
741790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    // Create or retrieve an i32 state value that is used to represent the
751790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    // pred block number for certain non-trivial edges.
761790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GlobalVariable *getEdgeStateValue();
771790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
781790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    // Produce a table of pointers to counters, by predecessor and successor
791790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    // block number.
801790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GlobalVariable *buildEdgeLookupTable(Function *F,
811790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                         GlobalVariable *Counter,
821790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                         const UniqueVector<BasicBlock *> &Preds,
831790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                         const UniqueVector<BasicBlock *> &Succs);
841790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
85b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // Add the function to write out all our counters to the global destructor
86b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // list.
871790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void insertCounterWriteout(DebugInfoFinder &,
88b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                               SmallVector<std::pair<GlobalVariable *,
89b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                                     uint32_t>, 8> &);
90b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
91a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky    bool EmitNotes;
92a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky    bool EmitData;
93a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky
941790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Module *M;
95b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    LLVMContext *Ctx;
96b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  };
97b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
98b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
99b1928704201034c785a26296a49f69355eb56a05Nick Lewyckychar GCOVProfiler::ID = 0;
100b1928704201034c785a26296a49f69355eb56a05Nick LewyckyINITIALIZE_PASS(GCOVProfiler, "insert-gcov-profiling",
101b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                "Insert instrumentation for GCOV profiling", false, false)
102b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
103a61e52c9b7cf874b46cef687c1c4627a35952542Nick LewyckyModulePass *llvm::createGCOVProfilerPass(bool EmitNotes, bool EmitData) {
104a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky  return new GCOVProfiler(EmitNotes, EmitData);
105a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky}
106b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
1071790c9cbb6714e81eab1412909a2320acaecc43bNick Lewyckystatic DISubprogram findSubprogram(DIScope Scope) {
1081790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  while (!Scope.isSubprogram()) {
1091790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    assert(Scope.isLexicalBlock() &&
110b1928704201034c785a26296a49f69355eb56a05Nick Lewycky           "Debug location not lexical block or subprogram");
1111790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Scope = DILexicalBlock(Scope).getContext();
112b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  }
1131790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return DISubprogram(Scope);
114b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
115b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
116b1928704201034c785a26296a49f69355eb56a05Nick Lewyckynamespace {
117b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  class GCOVRecord {
118b1928704201034c785a26296a49f69355eb56a05Nick Lewycky   protected:
1191790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    static const char *LinesTag;
1201790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    static const char *FunctionTag;
1211790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    static const char *BlockTag;
1221790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    static const char *EdgeTag;
123b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
124b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    GCOVRecord() {}
125b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
1261790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void writeBytes(const char *Bytes, int Size) {
1271790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      os->write(Bytes, Size);
128b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
129b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
1301790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void write(uint32_t i) {
1311790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      writeBytes(reinterpret_cast<char*>(&i), 4);
132b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
133b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
134b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // Returns the length measured in 4-byte blocks that will be used to
135b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // represent this string in a GCOV file
1361790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    unsigned lengthOfGCOVString(StringRef s) {
137b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      // A GCOV string is a length, followed by a NUL, then between 0 and 3 NULs
13817df2c3240837b4382898ead8c3ead407a338520Nick Lewycky      // padding out to the next 4-byte word. The length is measured in 4-byte
13917df2c3240837b4382898ead8c3ead407a338520Nick Lewycky      // words including padding, not bytes of actual string.
140b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      return (s.size() + 5) / 4;
141b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
142b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
1431790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void writeGCOVString(StringRef s) {
1441790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      uint32_t Len = lengthOfGCOVString(s);
1451790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(Len);
1461790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      writeBytes(s.data(), s.size());
147b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
148b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      // Write 1 to 4 bytes of NUL padding.
1497a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky      assert((unsigned)(4 - (s.size() % 4)) > 0);
1507a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky      assert((unsigned)(4 - (s.size() % 4)) <= 4);
1517a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky      writeBytes("\0\0\0\0", 4 - (s.size() % 4));
152b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
153b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
154b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    raw_ostream *os;
155b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  };
1561790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const char *GCOVRecord::LinesTag = "\0\0\x45\x01";
1571790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const char *GCOVRecord::FunctionTag = "\0\0\0\1";
1581790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const char *GCOVRecord::BlockTag = "\0\0\x41\x01";
1591790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const char *GCOVRecord::EdgeTag = "\0\0\x43\x01";
160b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
161b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  class GCOVFunction;
162b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  class GCOVBlock;
163b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
164b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // Constructed only by requesting it from a GCOVBlock, this object stores a
165b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // list of line numbers and a single filename, representing lines that belong
166b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // to the block.
167b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  class GCOVLines : public GCOVRecord {
168b1928704201034c785a26296a49f69355eb56a05Nick Lewycky   public:
1691790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void addLine(uint32_t Line) {
1701790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      Lines.push_back(Line);
171b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
172b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
1731790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    uint32_t length() {
1741790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      return lengthOfGCOVString(Filename) + 2 + Lines.size();
175b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
176b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
177b1928704201034c785a26296a49f69355eb56a05Nick Lewycky   private:
178b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    friend class GCOVBlock;
179b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
1801790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GCOVLines(std::string Filename, raw_ostream *os)
1811790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        : Filename(Filename) {
182b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      this->os = os;
183b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
184b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
1851790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    std::string Filename;
1861790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    SmallVector<uint32_t, 32> Lines;
187b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  };
188b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
189b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // Represent a basic block in GCOV. Each block has a unique number in the
190b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // function, number of lines belonging to each block, and a set of edges to
191b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // other blocks.
192b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  class GCOVBlock : public GCOVRecord {
193b1928704201034c785a26296a49f69355eb56a05Nick Lewycky   public:
1941790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GCOVLines &getFile(std::string Filename) {
1951790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      GCOVLines *&Lines = LinesByFile[Filename];
1961790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      if (!Lines) {
1971790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Lines = new GCOVLines(Filename, os);
198b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
1991790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      return *Lines;
200b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
201b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
2021790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void addEdge(GCOVBlock &Successor) {
2031790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      OutEdges.push_back(&Successor);
204b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
205b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
2061790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void writeOut() {
2071790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      uint32_t Len = 3;
2081790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (StringMap<GCOVLines *>::iterator I = LinesByFile.begin(),
2091790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky               E = LinesByFile.end(); I != E; ++I) {
2101790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Len += I->second->length();
211b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
212b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
2131790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      writeBytes(LinesTag, 4);
2141790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(Len);
2151790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(Number);
2161790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (StringMap<GCOVLines *>::iterator I = LinesByFile.begin(),
2171790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky               E = LinesByFile.end(); I != E; ++I) {
2181790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        write(0);
2191790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        writeGCOVString(I->second->Filename);
2201790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        for (int i = 0, e = I->second->Lines.size(); i != e; ++i) {
2211790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          write(I->second->Lines[i]);
222b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        }
223b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
2241790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(0);
2251790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(0);
226b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
227b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
228b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    ~GCOVBlock() {
2291790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      DeleteContainerSeconds(LinesByFile);
230b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
231b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
232b1928704201034c785a26296a49f69355eb56a05Nick Lewycky   private:
233b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    friend class GCOVFunction;
234b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
2351790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GCOVBlock(uint32_t Number, raw_ostream *os)
2361790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        : Number(Number) {
237b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      this->os = os;
238b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
239b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
2401790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    uint32_t Number;
2411790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    StringMap<GCOVLines *> LinesByFile;
2421790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    SmallVector<GCOVBlock *, 4> OutEdges;
243b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  };
244b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
245b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // A function has a unique identifier, a checksum (we leave as zero) and a
246b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // set of blocks and a map of edges between blocks. This is the only GCOV
247b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  // object users can construct, the blocks and lines will be rooted here.
248b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  class GCOVFunction : public GCOVRecord {
249b1928704201034c785a26296a49f69355eb56a05Nick Lewycky   public:
250b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    GCOVFunction(DISubprogram SP, raw_ostream *os) {
251b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      this->os = os;
252b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
253b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      Function *F = SP.getFunction();
254b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      uint32_t i = 0;
255b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
2561790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Blocks[BB] = new GCOVBlock(i++, os);
257b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
2581790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      ReturnBlock = new GCOVBlock(i++, os);
2591790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
2601790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      writeBytes(FunctionTag, 4);
2611790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      uint32_t BlockLen = 1 + 1 + 1 + lengthOfGCOVString(SP.getName()) +
2621790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          1 + lengthOfGCOVString(SP.getFilename()) + 1;
2631790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(BlockLen);
2641790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      uint32_t Ident = reinterpret_cast<intptr_t>((MDNode*)SP);
2651790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(Ident);
2667a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky      write(0);  // checksum
2671790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      writeGCOVString(SP.getName());
2681790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      writeGCOVString(SP.getFilename());
2691790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(SP.getLineNumber());
270b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
271b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
272b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    ~GCOVFunction() {
2731790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      DeleteContainerSeconds(Blocks);
2741790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      delete ReturnBlock;
275b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
276b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
2771790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GCOVBlock &getBlock(BasicBlock *BB) {
2781790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      return *Blocks[BB];
279b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
280b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
2811790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GCOVBlock &getReturnBlock() {
2821790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      return *ReturnBlock;
283a4c4c0e1298f4dd9791eff2bae857e7be6d0ab56Nick Lewycky    }
284a4c4c0e1298f4dd9791eff2bae857e7be6d0ab56Nick Lewycky
2851790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    void writeOut() {
286b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      // Emit count of blocks.
2871790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      writeBytes(BlockTag, 4);
2881790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      write(Blocks.size() + 1);
2891790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (int i = 0, e = Blocks.size() + 1; i != e; ++i) {
2901790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        write(0);  // No flags on our blocks.
291b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
292b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
293b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      // Emit edges between blocks.
2941790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (DenseMap<BasicBlock *, GCOVBlock *>::iterator I = Blocks.begin(),
2951790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky               E = Blocks.end(); I != E; ++I) {
2961790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        GCOVBlock &Block = *I->second;
2971790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        if (Block.OutEdges.empty()) continue;
2981790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
2991790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        writeBytes(EdgeTag, 4);
3001790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        write(Block.OutEdges.size() * 2 + 1);
3011790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        write(Block.Number);
3021790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        for (int i = 0, e = Block.OutEdges.size(); i != e; ++i) {
3031790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          write(Block.OutEdges[i]->Number);
3041790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          write(0);  // no flags
305b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        }
306b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
307b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
308b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      // Emit lines for each block.
3091790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (DenseMap<BasicBlock *, GCOVBlock *>::iterator I = Blocks.begin(),
3101790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky               E = Blocks.end(); I != E; ++I) {
3111790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        I->second->writeOut();
312b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
313b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
314b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
315b1928704201034c785a26296a49f69355eb56a05Nick Lewycky   private:
3161790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    DenseMap<BasicBlock *, GCOVBlock *> Blocks;
3171790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GCOVBlock *ReturnBlock;
318b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  };
319b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
320b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
3210c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky// Replace the stem of a file, or add one if missing.
3221790c9cbb6714e81eab1412909a2320acaecc43bNick Lewyckystatic std::string replaceStem(std::string OrigFilename, std::string NewStem) {
3231790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return (sys::path::stem(OrigFilename) + "." + NewStem).str();
3240c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky}
3250c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky
3260c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewyckybool GCOVProfiler::runOnModule(Module &M) {
3271790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  this->M = &M;
3280c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky  Ctx = &M.getContext();
3290c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky
3300c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky  DebugInfoFinder DIF;
3311790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  DIF.processModule(M);
3320c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky
3331790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  if (EmitNotes) emitGCNO(DIF);
3341790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  if (EmitData) return emitProfileArcs(DIF);
335a61e52c9b7cf874b46cef687c1c4627a35952542Nick Lewycky  return false;
3360c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky}
3370c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky
3381790c9cbb6714e81eab1412909a2320acaecc43bNick Lewyckyvoid GCOVProfiler::emitGCNO(DebugInfoFinder &DIF) {
3391790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  DenseMap<const MDNode *, raw_fd_ostream *> GcnoFiles;
340b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  for (DebugInfoFinder::iterator I = DIF.compile_unit_begin(),
341b1928704201034c785a26296a49f69355eb56a05Nick Lewycky           E = DIF.compile_unit_end(); I != E; ++I) {
342b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // Each compile unit gets its own .gcno file. This means that whether we run
343b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // this pass over the original .o's as they're produced, or run it after
344b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    // LTO, we'll generate the same .gcno files.
345b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
346b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    DICompileUnit CU(*I);
3471790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    raw_fd_ostream *&out = GcnoFiles[CU];
348b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    std::string ErrorInfo;
3491790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    out = new raw_fd_ostream(replaceStem(CU.getFilename(), "gcno").c_str(),
3500c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky                             ErrorInfo, raw_fd_ostream::F_Binary);
3511790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    out->write("oncg*404MVLL", 12);
352b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  }
353b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
354b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  for (DebugInfoFinder::iterator SPI = DIF.subprogram_begin(),
355b1928704201034c785a26296a49f69355eb56a05Nick Lewycky           SPE = DIF.subprogram_end(); SPI != SPE; ++SPI) {
356b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    DISubprogram SP(*SPI);
3571790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    raw_fd_ostream *&os = GcnoFiles[SP.getCompileUnit()];
358b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
359b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Function *F = SP.getFunction();
3607a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky    if (!F) continue;
3617a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky    GCOVFunction Func(SP, os);
3627a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky
363b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
3641790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      GCOVBlock &Block = Func.getBlock(BB);
365b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      TerminatorInst *TI = BB->getTerminator();
366b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      if (int successors = TI->getNumSuccessors()) {
367b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        for (int i = 0; i != successors; ++i) {
3681790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Block.addEdge(Func.getBlock(TI->getSuccessor(i)));
369b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        }
370a4c4c0e1298f4dd9791eff2bae857e7be6d0ab56Nick Lewycky      } else if (isa<ReturnInst>(TI)) {
3711790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Block.addEdge(Func.getReturnBlock());
372b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
373b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
3741790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      uint32_t Line = 0;
375b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      for (BasicBlock::iterator I = BB->begin(), IE = BB->end(); I != IE; ++I) {
3761790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        const DebugLoc &Loc = I->getDebugLoc();
3771790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        if (Loc.isUnknown()) continue;
3781790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        if (Line == Loc.getLine()) continue;
3791790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Line = Loc.getLine();
3801790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        if (SP != findSubprogram(DIScope(Loc.getScope(*Ctx)))) continue;
3811790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
3821790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        GCOVLines &Lines = Block.getFile(SP.getFilename());
3831790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Lines.addLine(Loc.getLine());
384b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
385b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
3861790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Func.writeOut();
387b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  }
388b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
389b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  for (DenseMap<const MDNode *, raw_fd_ostream *>::iterator
3901790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky           I = GcnoFiles.begin(), E = GcnoFiles.end(); I != E; ++I) {
3911790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    raw_fd_ostream *&out = I->second;
3921790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    out->write("\0\0\0\0\0\0\0\0", 8);  // EOF
3931790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    out->close();
3941790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    delete out;
395b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  }
396b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
397b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
3981790c9cbb6714e81eab1412909a2320acaecc43bNick Lewyckybool GCOVProfiler::emitProfileArcs(DebugInfoFinder &DIF) {
3990c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky  if (DIF.subprogram_begin() == DIF.subprogram_end())
4000c4de8a4eb5fd6437b571611794ef84427fc4755Nick Lewycky    return false;
401b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4021790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  SmallVector<std::pair<GlobalVariable *, uint32_t>, 8> CountersByIdent;
403b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  for (DebugInfoFinder::iterator SPI = DIF.subprogram_begin(),
404b1928704201034c785a26296a49f69355eb56a05Nick Lewycky           SPE = DIF.subprogram_end(); SPI != SPE; ++SPI) {
405b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    DISubprogram SP(*SPI);
406b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Function *F = SP.getFunction();
4077a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky    if (!F) continue;
408b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4091790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    unsigned Edges = 0;
410b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
411b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      TerminatorInst *TI = BB->getTerminator();
412a4c4c0e1298f4dd9791eff2bae857e7be6d0ab56Nick Lewycky      if (isa<ReturnInst>(TI))
4131790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        ++Edges;
414a4c4c0e1298f4dd9791eff2bae857e7be6d0ab56Nick Lewycky      else
4151790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Edges += TI->getNumSuccessors();
416b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
417b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4181790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    const ArrayType *CounterTy =
4191790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        ArrayType::get(Type::getInt64Ty(*Ctx), Edges);
4201790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GlobalVariable *Counters =
4211790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        new GlobalVariable(*M, CounterTy, false,
422b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                           GlobalValue::InternalLinkage,
4231790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                           Constant::getNullValue(CounterTy),
424b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                           "__llvm_gcov_ctr", 0, false, 0);
4251790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    CountersByIdent.push_back(
4261790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        std::make_pair(Counters, reinterpret_cast<intptr_t>((MDNode*)SP)));
427b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4281790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    UniqueVector<BasicBlock *> ComplexEdgePreds;
4291790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    UniqueVector<BasicBlock *> ComplexEdgeSuccs;
430b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4311790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    unsigned Edge = 0;
432b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
433b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      TerminatorInst *TI = BB->getTerminator();
4341790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors();
4351790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      if (Successors) {
4361790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        IRBuilder<> Builder(TI);
4371790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
4381790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        if (Successors == 1) {
4391790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Value *Counter = Builder.CreateConstInBoundsGEP2_64(Counters, 0,
4401790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                                              Edge);
4411790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Value *Count = Builder.CreateLoad(Counter);
4421790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Count = Builder.CreateAdd(Count,
443b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                    ConstantInt::get(Type::getInt64Ty(*Ctx),1));
4441790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Builder.CreateStore(Count, Counter);
445b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
4461790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Value *Sel = Builder.CreateSelect(
447b1928704201034c785a26296a49f69355eb56a05Nick Lewycky              BI->getCondition(),
4481790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky              ConstantInt::get(Type::getInt64Ty(*Ctx), Edge),
4491790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky              ConstantInt::get(Type::getInt64Ty(*Ctx), Edge + 1));
4501790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          SmallVector<Value *, 2> Idx;
4511790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Idx.push_back(Constant::getNullValue(Type::getInt64Ty(*Ctx)));
4521790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Idx.push_back(Sel);
4531790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Value *Counter = Builder.CreateInBoundsGEP(Counters,
4541790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                                     Idx.begin(), Idx.end());
4551790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Value *Count = Builder.CreateLoad(Counter);
4561790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Count = Builder.CreateAdd(Count,
457b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                    ConstantInt::get(Type::getInt64Ty(*Ctx),1));
4581790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          Builder.CreateStore(Count, Counter);
459b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        } else {
4601790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          ComplexEdgePreds.insert(BB);
4611790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          for (int i = 0; i != Successors; ++i)
4621790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky            ComplexEdgeSuccs.insert(TI->getSuccessor(i));
463b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        }
4641790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Edge += Successors;
465b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
466b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
467b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4681790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    if (!ComplexEdgePreds.empty()) {
4691790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      GlobalVariable *EdgeTable =
4701790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          buildEdgeLookupTable(F, Counters,
4711790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                               ComplexEdgePreds, ComplexEdgeSuccs);
4721790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      GlobalVariable *EdgeState = getEdgeStateValue();
4731790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
4741790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      const Type *Int32Ty = Type::getInt32Ty(*Ctx);
4751790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (int i = 0, e = ComplexEdgePreds.size(); i != e; ++i) {
4761790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        IRBuilder<> Builder(ComplexEdgePreds[i+1]->getTerminator());
4777a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky        Builder.CreateStore(ConstantInt::get(Int32Ty, i), EdgeState);
478b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
4791790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (int i = 0, e = ComplexEdgeSuccs.size(); i != e; ++i) {
480b1928704201034c785a26296a49f69355eb56a05Nick Lewycky        // call runtime to perform increment
4811790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        IRBuilder<> Builder(ComplexEdgeSuccs[i+1]->getFirstNonPHI());
4821790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Value *CounterPtrArray =
4831790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky            Builder.CreateConstInBoundsGEP2_64(EdgeTable, 0,
4841790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                               i * ComplexEdgePreds.size());
4851790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Builder.CreateCall2(getIncrementIndirectCounterFunc(),
4861790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                            EdgeState, CounterPtrArray);
4871790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        // clear the predecessor number
4881790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Builder.CreateStore(ConstantInt::get(Int32Ty, 0xffffffff), EdgeState);
489b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      }
490b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
491b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  }
492b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4931790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  insertCounterWriteout(DIF, CountersByIdent);
494b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
495b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  return true;
496b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
497b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
4981790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky// All edges with successors that aren't branches are "complex", because it
4991790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky// requires complex logic to pick which counter to update.
5001790c9cbb6714e81eab1412909a2320acaecc43bNick LewyckyGlobalVariable *GCOVProfiler::buildEdgeLookupTable(
5011790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Function *F,
5021790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GlobalVariable *Counters,
5031790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    const UniqueVector<BasicBlock *> &Preds,
5041790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    const UniqueVector<BasicBlock *> &Succs) {
5051790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  // TODO: support invoke, threads. We rely on the fact that nothing can modify
5061790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  // the whole-Module pred edge# between the time we set it and the time we next
5071790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  // read it. Threads and invoke make this untrue.
5081790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
5091790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  // emit [(succs * preds) x i64*], logically [succ x [pred x i64*]].
5101790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const Type *Int64PtrTy = Type::getInt64PtrTy(*Ctx);
5111790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const ArrayType *EdgeTableTy = ArrayType::get(
5121790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      Int64PtrTy, Succs.size() * Preds.size());
5131790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
5141790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  Constant **EdgeTable = new Constant*[Succs.size() * Preds.size()];
5151790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  Constant *NullValue = Constant::getNullValue(Int64PtrTy);
5161790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  for (int i = 0, ie = Succs.size() * Preds.size(); i != ie; ++i)
5171790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    EdgeTable[i] = NullValue;
5181790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
5191790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  unsigned Edge = 0;
5201790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
5211790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    TerminatorInst *TI = BB->getTerminator();
5221790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors();
5237a2ba2fbe4b0ccaacc2cedbc1bfd2a3764170efeNick Lewycky    if (Successors > 1 && !isa<BranchInst>(TI) && !isa<ReturnInst>(TI)) {
5241790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      for (int i = 0; i != Successors; ++i) {
5251790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        BasicBlock *Succ = TI->getSuccessor(i);
5261790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        IRBuilder<> builder(Succ);
5271790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        Value *Counter = builder.CreateConstInBoundsGEP2_64(Counters, 0,
5281790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                                            Edge + i);
5291790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky        EdgeTable[((Succs.idFor(Succ)-1) * Preds.size()) +
5301790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                  (Preds.idFor(BB)-1)] = cast<Constant>(Counter);
5311790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      }
5321790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    }
5331790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Edge += Successors;
5341790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  }
5351790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
5361790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  GlobalVariable *EdgeTableGV =
5371790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      new GlobalVariable(
5381790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          *M, EdgeTableTy, true, GlobalValue::InternalLinkage,
5391790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          ConstantArray::get(EdgeTableTy,
5401790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                             &EdgeTable[0], Succs.size() * Preds.size()),
5411790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky          "__llvm_gcda_edge_table");
5421790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  EdgeTableGV->setUnnamedAddr(true);
5431790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return EdgeTableGV;
5441790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky}
5451790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
546b1928704201034c785a26296a49f69355eb56a05Nick LewyckyConstant *GCOVProfiler::getStartFileFunc() {
5471790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const Type *Args[] = { Type::getInt8PtrTy(*Ctx) };
548b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  const FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx),
549b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                              Args, false);
5501790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return M->getOrInsertFunction("llvm_gcda_start_file", FTy);
5511790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky}
5521790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky
5531790c9cbb6714e81eab1412909a2320acaecc43bNick LewyckyConstant *GCOVProfiler::getIncrementIndirectCounterFunc() {
5541790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const Type *Args[] = {
5551790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Type::getInt32PtrTy(*Ctx),                  // uint32_t *predecessor
5561790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Type::getInt64PtrTy(*Ctx)->getPointerTo(),  // uint64_t **state_table_row
5571790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  };
5581790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx),
5591790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                              Args, false);
5601790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return M->getOrInsertFunction("llvm_gcda_increment_indirect_counter", FTy);
561b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
562b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
563b1928704201034c785a26296a49f69355eb56a05Nick LewyckyConstant *GCOVProfiler::getEmitFunctionFunc() {
5641790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  const Type *Args[] = { Type::getInt32Ty(*Ctx) };
565b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  const FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx),
566b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                              Args, false);
5671790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return M->getOrInsertFunction("llvm_gcda_emit_function", FTy);
568b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
569b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
570b1928704201034c785a26296a49f69355eb56a05Nick LewyckyConstant *GCOVProfiler::getEmitArcsFunc() {
571b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  const Type *Args[] = {
572b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Type::getInt32Ty(*Ctx),     // uint32_t num_counters
573b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    Type::getInt64PtrTy(*Ctx),  // uint64_t *counters
574b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  };
575b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  const FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx),
576b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                              Args, false);
5771790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return M->getOrInsertFunction("llvm_gcda_emit_arcs", FTy);
578b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
579b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
580b1928704201034c785a26296a49f69355eb56a05Nick LewyckyConstant *GCOVProfiler::getEndFileFunc() {
581b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  const FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false);
5821790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return M->getOrInsertFunction("llvm_gcda_end_file", FTy);
583b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
584b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
5851790c9cbb6714e81eab1412909a2320acaecc43bNick LewyckyGlobalVariable *GCOVProfiler::getEdgeStateValue() {
5861790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  GlobalVariable *GV = M->getGlobalVariable("__llvm_gcov_global_state_pred");
5871790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  if (!GV) {
5881790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GV = new GlobalVariable(*M, Type::getInt32Ty(*Ctx), false,
5891790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                            GlobalValue::InternalLinkage,
5901790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                            ConstantInt::get(Type::getInt32Ty(*Ctx),
5911790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                             0xffffffff),
5921790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                            "__llvm_gcov_global_state_pred");
5931790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    GV->setUnnamedAddr(true);
5941790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  }
5951790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  return GV;
5961790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky}
597b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
5981790c9cbb6714e81eab1412909a2320acaecc43bNick Lewyckyvoid GCOVProfiler::insertCounterWriteout(
5991790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    DebugInfoFinder &DIF,
6001790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    SmallVector<std::pair<GlobalVariable *, uint32_t>, 8> &CountersByIdent) {
601b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  const FunctionType *WriteoutFTy =
602b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      FunctionType::get(Type::getVoidTy(*Ctx), false);
603b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  Function *WriteoutF = Function::Create(WriteoutFTy,
604b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                         GlobalValue::InternalLinkage,
6051790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                                         "__llvm_gcov_writeout", M);
606b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  WriteoutF->setUnnamedAddr(true);
607b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  BasicBlock *BB = BasicBlock::Create(*Ctx, "", WriteoutF);
6081790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  IRBuilder<> Builder(BB);
609b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
610b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  Constant *StartFile = getStartFileFunc();
611b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  Constant *EmitFunction = getEmitFunctionFunc();
612b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  Constant *EmitArcs = getEmitArcsFunc();
613b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  Constant *EndFile = getEndFileFunc();
614b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
615b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  for (DebugInfoFinder::iterator CUI = DIF.compile_unit_begin(),
616b1928704201034c785a26296a49f69355eb56a05Nick Lewycky           CUE = DIF.compile_unit_end(); CUI != CUE; ++CUI) {
617b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    DICompileUnit compile_unit(*CUI);
6181790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    std::string FilenameGcda = replaceStem(compile_unit.getFilename(), "gcda");
6191790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Builder.CreateCall(StartFile,
6201790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                       Builder.CreateGlobalStringPtr(FilenameGcda));
621b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    for (SmallVector<std::pair<GlobalVariable *, uint32_t>, 8>::iterator
6221790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky             I = CountersByIdent.begin(), E = CountersByIdent.end();
623b1928704201034c785a26296a49f69355eb56a05Nick Lewycky         I != E; ++I) {
6241790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      Builder.CreateCall(EmitFunction, ConstantInt::get(Type::getInt32Ty(*Ctx),
625b1928704201034c785a26296a49f69355eb56a05Nick Lewycky                                                        I->second));
626b1928704201034c785a26296a49f69355eb56a05Nick Lewycky      GlobalVariable *GV = I->first;
6271790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      unsigned Arcs =
628b1928704201034c785a26296a49f69355eb56a05Nick Lewycky          cast<ArrayType>(GV->getType()->getElementType())->getNumElements();
6291790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky      Builder.CreateCall2(EmitArcs,
6301790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                          ConstantInt::get(Type::getInt32Ty(*Ctx), Arcs),
6311790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky                          Builder.CreateConstGEP2_64(GV, 0, 0));
632b1928704201034c785a26296a49f69355eb56a05Nick Lewycky    }
6331790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky    Builder.CreateCall(EndFile);
634b1928704201034c785a26296a49f69355eb56a05Nick Lewycky  }
6351790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  Builder.CreateRetVoid();
636b1928704201034c785a26296a49f69355eb56a05Nick Lewycky
6371790c9cbb6714e81eab1412909a2320acaecc43bNick Lewycky  InsertProfilingShutdownCall(WriteoutF, M);
638b1928704201034c785a26296a49f69355eb56a05Nick Lewycky}
639