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