1//===- GCOV.cpp - LLVM coverage tool --------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// GCOV implements the interface to read and write coverage files that use
10// 'gcov' format.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/ProfileData/GCOV.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallSet.h"
17#include "llvm/Config/llvm-config.h"
18#include "llvm/Demangle/Demangle.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/FileSystem.h"
21#include "llvm/Support/Format.h"
22#include "llvm/Support/MD5.h"
23#include "llvm/Support/Path.h"
24#include "llvm/Support/raw_ostream.h"
25#include <algorithm>
26#include <optional>
27#include <system_error>
28
29using namespace llvm;
30
31enum : uint32_t {
32  GCOV_ARC_ON_TREE = 1 << 0,
33  GCOV_ARC_FALLTHROUGH = 1 << 2,
34
35  GCOV_TAG_FUNCTION = 0x01000000,
36  GCOV_TAG_BLOCKS = 0x01410000,
37  GCOV_TAG_ARCS = 0x01430000,
38  GCOV_TAG_LINES = 0x01450000,
39  GCOV_TAG_COUNTER_ARCS = 0x01a10000,
40  // GCOV_TAG_OBJECT_SUMMARY superseded GCOV_TAG_PROGRAM_SUMMARY in GCC 9.
41  GCOV_TAG_OBJECT_SUMMARY = 0xa1000000,
42  GCOV_TAG_PROGRAM_SUMMARY = 0xa3000000,
43};
44
45namespace {
46struct Summary {
47  Summary(StringRef Name) : Name(Name) {}
48
49  StringRef Name;
50  uint64_t lines = 0;
51  uint64_t linesExec = 0;
52  uint64_t branches = 0;
53  uint64_t branchesExec = 0;
54  uint64_t branchesTaken = 0;
55};
56
57struct LineInfo {
58  SmallVector<const GCOVBlock *, 1> blocks;
59  uint64_t count = 0;
60  bool exists = false;
61};
62
63struct SourceInfo {
64  StringRef filename;
65  SmallString<0> displayName;
66  std::vector<std::vector<const GCOVFunction *>> startLineToFunctions;
67  std::vector<LineInfo> lines;
68  bool ignored = false;
69  SourceInfo(StringRef filename) : filename(filename) {}
70};
71
72class Context {
73public:
74  Context(const GCOV::Options &Options) : options(Options) {}
75  void print(StringRef filename, StringRef gcno, StringRef gcda,
76             GCOVFile &file);
77
78private:
79  std::string getCoveragePath(StringRef filename, StringRef mainFilename) const;
80  void printFunctionDetails(const GCOVFunction &f, raw_ostream &os) const;
81  void printBranchInfo(const GCOVBlock &Block, uint32_t &edgeIdx,
82                       raw_ostream &OS) const;
83  void printSummary(const Summary &summary, raw_ostream &os) const;
84
85  void collectFunction(GCOVFunction &f, Summary &summary);
86  void collectSourceLine(SourceInfo &si, Summary *summary, LineInfo &line,
87                         size_t lineNum) const;
88  void collectSource(SourceInfo &si, Summary &summary) const;
89  void annotateSource(SourceInfo &si, const GCOVFile &file, StringRef gcno,
90                      StringRef gcda, raw_ostream &os) const;
91  void printSourceToIntermediate(const SourceInfo &si, raw_ostream &os) const;
92
93  const GCOV::Options &options;
94  std::vector<SourceInfo> sources;
95};
96} // namespace
97
98//===----------------------------------------------------------------------===//
99// GCOVFile implementation.
100
101/// readGCNO - Read GCNO buffer.
102bool GCOVFile::readGCNO(GCOVBuffer &buf) {
103  if (!buf.readGCNOFormat())
104    return false;
105  if (!buf.readGCOVVersion(version))
106    return false;
107
108  checksum = buf.getWord();
109  if (version >= GCOV::V900 && !buf.readString(cwd))
110    return false;
111  if (version >= GCOV::V800)
112    buf.getWord(); // hasUnexecutedBlocks
113
114  uint32_t tag, length;
115  GCOVFunction *fn = nullptr;
116  while ((tag = buf.getWord())) {
117    if (!buf.readInt(length))
118      return false;
119    uint32_t pos = buf.cursor.tell();
120    if (tag == GCOV_TAG_FUNCTION) {
121      functions.push_back(std::make_unique<GCOVFunction>(*this));
122      fn = functions.back().get();
123      fn->ident = buf.getWord();
124      fn->linenoChecksum = buf.getWord();
125      if (version >= GCOV::V407)
126        fn->cfgChecksum = buf.getWord();
127      buf.readString(fn->Name);
128      StringRef filename;
129      if (version < GCOV::V800) {
130        if (!buf.readString(filename))
131          return false;
132        fn->startLine = buf.getWord();
133      } else {
134        fn->artificial = buf.getWord();
135        if (!buf.readString(filename))
136          return false;
137        fn->startLine = buf.getWord();
138        fn->startColumn = buf.getWord();
139        fn->endLine = buf.getWord();
140        if (version >= GCOV::V900)
141          fn->endColumn = buf.getWord();
142      }
143      fn->srcIdx = addNormalizedPathToMap(filename);
144      identToFunction[fn->ident] = fn;
145    } else if (tag == GCOV_TAG_BLOCKS && fn) {
146      if (version < GCOV::V800) {
147        for (uint32_t i = 0; i != length; ++i) {
148          buf.getWord(); // Ignored block flags
149          fn->blocks.push_back(std::make_unique<GCOVBlock>(i));
150        }
151      } else {
152        uint32_t num = buf.getWord();
153        for (uint32_t i = 0; i != num; ++i)
154          fn->blocks.push_back(std::make_unique<GCOVBlock>(i));
155      }
156    } else if (tag == GCOV_TAG_ARCS && fn) {
157      uint32_t srcNo = buf.getWord();
158      if (srcNo >= fn->blocks.size()) {
159        errs() << "unexpected block number: " << srcNo << " (in "
160               << fn->blocks.size() << ")\n";
161        return false;
162      }
163      GCOVBlock *src = fn->blocks[srcNo].get();
164      const uint32_t e =
165          version >= GCOV::V1200 ? (length / 4 - 1) / 2 : (length - 1) / 2;
166      for (uint32_t i = 0; i != e; ++i) {
167        uint32_t dstNo = buf.getWord(), flags = buf.getWord();
168        GCOVBlock *dst = fn->blocks[dstNo].get();
169        auto arc = std::make_unique<GCOVArc>(*src, *dst, flags);
170        src->addDstEdge(arc.get());
171        dst->addSrcEdge(arc.get());
172        if (arc->onTree())
173          fn->treeArcs.push_back(std::move(arc));
174        else
175          fn->arcs.push_back(std::move(arc));
176      }
177    } else if (tag == GCOV_TAG_LINES && fn) {
178      uint32_t srcNo = buf.getWord();
179      if (srcNo >= fn->blocks.size()) {
180        errs() << "unexpected block number: " << srcNo << " (in "
181               << fn->blocks.size() << ")\n";
182        return false;
183      }
184      GCOVBlock &Block = *fn->blocks[srcNo];
185      for (;;) {
186        uint32_t line = buf.getWord();
187        if (line)
188          Block.addLine(line);
189        else {
190          StringRef filename;
191          buf.readString(filename);
192          if (filename.empty())
193            break;
194          // TODO Unhandled
195        }
196      }
197    }
198    pos += version >= GCOV::V1200 ? length : 4 * length;
199    if (pos < buf.cursor.tell())
200      return false;
201    buf.de.skip(buf.cursor, pos - buf.cursor.tell());
202  }
203
204  GCNOInitialized = true;
205  return true;
206}
207
208/// readGCDA - Read GCDA buffer. It is required that readGCDA() can only be
209/// called after readGCNO().
210bool GCOVFile::readGCDA(GCOVBuffer &buf) {
211  assert(GCNOInitialized && "readGCDA() can only be called after readGCNO()");
212  if (!buf.readGCDAFormat())
213    return false;
214  GCOV::GCOVVersion GCDAVersion;
215  if (!buf.readGCOVVersion(GCDAVersion))
216    return false;
217  if (version != GCDAVersion) {
218    errs() << "GCOV versions do not match.\n";
219    return false;
220  }
221
222  uint32_t GCDAChecksum;
223  if (!buf.readInt(GCDAChecksum))
224    return false;
225  if (checksum != GCDAChecksum) {
226    errs() << "file checksums do not match: " << checksum
227           << " != " << GCDAChecksum << "\n";
228    return false;
229  }
230  uint32_t dummy, tag, length;
231  uint32_t ident;
232  GCOVFunction *fn = nullptr;
233  while ((tag = buf.getWord())) {
234    if (!buf.readInt(length))
235      return false;
236    uint32_t pos = buf.cursor.tell();
237    if (tag == GCOV_TAG_OBJECT_SUMMARY) {
238      buf.readInt(runCount);
239      buf.readInt(dummy);
240    } else if (tag == GCOV_TAG_PROGRAM_SUMMARY) {
241      buf.readInt(dummy);
242      buf.readInt(dummy);
243      buf.readInt(runCount);
244      ++programCount;
245    } else if (tag == GCOV_TAG_FUNCTION) {
246      if (length == 0) // Placeholder
247        continue;
248      if (length < 2 || !buf.readInt(ident))
249        return false;
250      auto It = identToFunction.find(ident);
251      uint32_t linenoChecksum, cfgChecksum = 0;
252      buf.readInt(linenoChecksum);
253      if (version >= GCOV::V407)
254        buf.readInt(cfgChecksum);
255      if (It != identToFunction.end()) {
256        fn = It->second;
257        if (linenoChecksum != fn->linenoChecksum ||
258            cfgChecksum != fn->cfgChecksum) {
259          errs() << fn->Name
260                 << format(": checksum mismatch, (%u, %u) != (%u, %u)\n",
261                           linenoChecksum, cfgChecksum, fn->linenoChecksum,
262                           fn->cfgChecksum);
263          return false;
264        }
265      }
266    } else if (tag == GCOV_TAG_COUNTER_ARCS && fn) {
267      uint32_t expected = 2 * fn->arcs.size();
268      if (version >= GCOV::V1200)
269        expected *= 4;
270      if (length != expected) {
271        errs() << fn->Name
272               << format(
273                      ": GCOV_TAG_COUNTER_ARCS mismatch, got %u, expected %u\n",
274                      length, expected);
275        return false;
276      }
277      for (std::unique_ptr<GCOVArc> &arc : fn->arcs) {
278        if (!buf.readInt64(arc->count))
279          return false;
280        arc->src.count += arc->count;
281      }
282
283      if (fn->blocks.size() >= 2) {
284        GCOVBlock &src = *fn->blocks[0];
285        GCOVBlock &sink =
286            version < GCOV::V408 ? *fn->blocks.back() : *fn->blocks[1];
287        auto arc = std::make_unique<GCOVArc>(sink, src, GCOV_ARC_ON_TREE);
288        sink.addDstEdge(arc.get());
289        src.addSrcEdge(arc.get());
290        fn->treeArcs.push_back(std::move(arc));
291
292        for (GCOVBlock &block : fn->blocksRange())
293          fn->propagateCounts(block, nullptr);
294        for (size_t i = fn->treeArcs.size() - 1; i; --i)
295          fn->treeArcs[i - 1]->src.count += fn->treeArcs[i - 1]->count;
296      }
297    }
298    pos += version >= GCOV::V1200 ? length : 4 * length;
299    if (pos < buf.cursor.tell())
300      return false;
301    buf.de.skip(buf.cursor, pos - buf.cursor.tell());
302  }
303
304  return true;
305}
306
307void GCOVFile::print(raw_ostream &OS) const {
308  for (const GCOVFunction &f : *this)
309    f.print(OS);
310}
311
312#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
313/// dump - Dump GCOVFile content to dbgs() for debugging purposes.
314LLVM_DUMP_METHOD void GCOVFile::dump() const { print(dbgs()); }
315#endif
316
317unsigned GCOVFile::addNormalizedPathToMap(StringRef filename) {
318  // unify filename, as the same path can have different form
319  SmallString<256> P(filename);
320  sys::path::remove_dots(P, true);
321  filename = P.str();
322
323  auto r = filenameToIdx.try_emplace(filename, filenameToIdx.size());
324  if (r.second)
325    filenames.emplace_back(filename);
326
327  return r.first->second;
328}
329
330bool GCOVArc::onTree() const { return flags & GCOV_ARC_ON_TREE; }
331
332//===----------------------------------------------------------------------===//
333// GCOVFunction implementation.
334
335StringRef GCOVFunction::getName(bool demangle) const {
336  if (!demangle)
337    return Name;
338  if (demangled.empty()) {
339    do {
340      if (Name.starts_with("_Z")) {
341        // Name is guaranteed to be NUL-terminated.
342        if (char *res = itaniumDemangle(Name.data())) {
343          demangled = res;
344          free(res);
345          break;
346        }
347      }
348      demangled = Name;
349    } while (false);
350  }
351  return demangled;
352}
353StringRef GCOVFunction::getFilename() const { return file.filenames[srcIdx]; }
354
355/// getEntryCount - Get the number of times the function was called by
356/// retrieving the entry block's count.
357uint64_t GCOVFunction::getEntryCount() const {
358  return blocks.front()->getCount();
359}
360
361GCOVBlock &GCOVFunction::getExitBlock() const {
362  return file.getVersion() < GCOV::V408 ? *blocks.back() : *blocks[1];
363}
364
365// For each basic block, the sum of incoming edge counts equals the sum of
366// outgoing edge counts by Kirchoff's circuit law. If the unmeasured arcs form a
367// spanning tree, the count for each unmeasured arc (GCOV_ARC_ON_TREE) can be
368// uniquely identified. Use an iterative algorithm to decrease stack usage for
369// library users in threads. See the edge propagation algorithm in Optimally
370// Profiling and Tracing Programs, ACM Transactions on Programming Languages and
371// Systems, 1994.
372void GCOVFunction::propagateCounts(const GCOVBlock &v, GCOVArc *pred) {
373  struct Elem {
374    const GCOVBlock &v;
375    GCOVArc *pred;
376    bool inDst;
377    size_t i = 0;
378    uint64_t excess = 0;
379  };
380
381  SmallVector<Elem, 0> stack;
382  stack.push_back({v, pred, false});
383  for (;;) {
384    Elem &u = stack.back();
385    // If GCOV_ARC_ON_TREE edges do form a tree, visited is not needed;
386    // otherwise, this prevents infinite recursion for bad input.
387    if (u.i == 0 && !visited.insert(&u.v).second) {
388      stack.pop_back();
389      if (stack.empty())
390        break;
391      continue;
392    }
393    if (u.i < u.v.pred.size()) {
394      GCOVArc *e = u.v.pred[u.i++];
395      if (e != u.pred) {
396        if (e->onTree())
397          stack.push_back({e->src, e, /*inDst=*/false});
398        else
399          u.excess += e->count;
400      }
401    } else if (u.i < u.v.pred.size() + u.v.succ.size()) {
402      GCOVArc *e = u.v.succ[u.i++ - u.v.pred.size()];
403      if (e != u.pred) {
404        if (e->onTree())
405          stack.push_back({e->dst, e, /*inDst=*/true});
406        else
407          u.excess -= e->count;
408      }
409    } else {
410      uint64_t excess = u.excess;
411      if (static_cast<int64_t>(excess) < 0)
412        excess = -excess;
413      if (u.pred)
414        u.pred->count = excess;
415      bool inDst = u.inDst;
416      stack.pop_back();
417      if (stack.empty())
418        break;
419      stack.back().excess += inDst ? -excess : excess;
420    }
421  }
422}
423
424void GCOVFunction::print(raw_ostream &OS) const {
425  OS << "===== " << Name << " (" << ident << ") @ " << getFilename() << ":"
426     << startLine << "\n";
427  for (const auto &Block : blocks)
428    Block->print(OS);
429}
430
431#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
432/// dump - Dump GCOVFunction content to dbgs() for debugging purposes.
433LLVM_DUMP_METHOD void GCOVFunction::dump() const { print(dbgs()); }
434#endif
435
436/// collectLineCounts - Collect line counts. This must be used after
437/// reading .gcno and .gcda files.
438
439//===----------------------------------------------------------------------===//
440// GCOVBlock implementation.
441
442void GCOVBlock::print(raw_ostream &OS) const {
443  OS << "Block : " << number << " Counter : " << count << "\n";
444  if (!pred.empty()) {
445    OS << "\tSource Edges : ";
446    for (const GCOVArc *Edge : pred)
447      OS << Edge->src.number << " (" << Edge->count << "), ";
448    OS << "\n";
449  }
450  if (!succ.empty()) {
451    OS << "\tDestination Edges : ";
452    for (const GCOVArc *Edge : succ) {
453      if (Edge->flags & GCOV_ARC_ON_TREE)
454        OS << '*';
455      OS << Edge->dst.number << " (" << Edge->count << "), ";
456    }
457    OS << "\n";
458  }
459  if (!lines.empty()) {
460    OS << "\tLines : ";
461    for (uint32_t N : lines)
462      OS << (N) << ",";
463    OS << "\n";
464  }
465}
466
467#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
468/// dump - Dump GCOVBlock content to dbgs() for debugging purposes.
469LLVM_DUMP_METHOD void GCOVBlock::dump() const { print(dbgs()); }
470#endif
471
472uint64_t
473GCOVBlock::augmentOneCycle(GCOVBlock *src,
474                           std::vector<std::pair<GCOVBlock *, size_t>> &stack) {
475  GCOVBlock *u;
476  size_t i;
477  stack.clear();
478  stack.emplace_back(src, 0);
479  src->incoming = (GCOVArc *)1; // Mark u available for cycle detection
480  for (;;) {
481    std::tie(u, i) = stack.back();
482    if (i == u->succ.size()) {
483      u->traversable = false;
484      stack.pop_back();
485      if (stack.empty())
486        break;
487      continue;
488    }
489    ++stack.back().second;
490    GCOVArc *succ = u->succ[i];
491    // Ignore saturated arcs (cycleCount has been reduced to 0) and visited
492    // blocks. Ignore self arcs to guard against bad input (.gcno has no
493    // self arcs).
494    if (succ->cycleCount == 0 || !succ->dst.traversable || &succ->dst == u)
495      continue;
496    if (succ->dst.incoming == nullptr) {
497      succ->dst.incoming = succ;
498      stack.emplace_back(&succ->dst, 0);
499      continue;
500    }
501    uint64_t minCount = succ->cycleCount;
502    for (GCOVBlock *v = u;;) {
503      minCount = std::min(minCount, v->incoming->cycleCount);
504      v = &v->incoming->src;
505      if (v == &succ->dst)
506        break;
507    }
508    succ->cycleCount -= minCount;
509    for (GCOVBlock *v = u;;) {
510      v->incoming->cycleCount -= minCount;
511      v = &v->incoming->src;
512      if (v == &succ->dst)
513        break;
514    }
515    return minCount;
516  }
517  return 0;
518}
519
520// Get the total execution count of loops among blocks on the same line.
521// Assuming a reducible flow graph, the count is the sum of back edge counts.
522// Identifying loops is complex, so we simply find cycles and perform cycle
523// cancelling iteratively.
524uint64_t GCOVBlock::getCyclesCount(const BlockVector &blocks) {
525  std::vector<std::pair<GCOVBlock *, size_t>> stack;
526  uint64_t count = 0, d;
527  for (;;) {
528    // Make blocks on the line traversable and try finding a cycle.
529    for (const auto *b : blocks) {
530      const_cast<GCOVBlock *>(b)->traversable = true;
531      const_cast<GCOVBlock *>(b)->incoming = nullptr;
532    }
533    d = 0;
534    for (const auto *block : blocks) {
535      auto *b = const_cast<GCOVBlock *>(block);
536      if (b->traversable && (d = augmentOneCycle(b, stack)) > 0)
537        break;
538    }
539    if (d == 0)
540      break;
541    count += d;
542  }
543  // If there is no more loop, all traversable bits should have been cleared.
544  // This property is needed by subsequent calls.
545  for (const auto *b : blocks) {
546    assert(!b->traversable);
547    (void)b;
548  }
549  return count;
550}
551
552//===----------------------------------------------------------------------===//
553// FileInfo implementation.
554
555// Format dividend/divisor as a percentage. Return 1 if the result is greater
556// than 0% and less than 1%.
557static uint32_t formatPercentage(uint64_t dividend, uint64_t divisor) {
558  if (!dividend || !divisor)
559    return 0;
560  dividend *= 100;
561  return dividend < divisor ? 1 : dividend / divisor;
562}
563
564// This custom division function mimics gcov's branch ouputs:
565//   - Round to closest whole number
566//   - Only output 0% or 100% if it's exactly that value
567static uint32_t branchDiv(uint64_t Numerator, uint64_t Divisor) {
568  if (!Numerator)
569    return 0;
570  if (Numerator == Divisor)
571    return 100;
572
573  uint8_t Res = (Numerator * 100 + Divisor / 2) / Divisor;
574  if (Res == 0)
575    return 1;
576  if (Res == 100)
577    return 99;
578  return Res;
579}
580
581namespace {
582struct formatBranchInfo {
583  formatBranchInfo(const GCOV::Options &Options, uint64_t Count, uint64_t Total)
584      : Options(Options), Count(Count), Total(Total) {}
585
586  void print(raw_ostream &OS) const {
587    if (!Total)
588      OS << "never executed";
589    else if (Options.BranchCount)
590      OS << "taken " << Count;
591    else
592      OS << "taken " << branchDiv(Count, Total) << "%";
593  }
594
595  const GCOV::Options &Options;
596  uint64_t Count;
597  uint64_t Total;
598};
599
600static raw_ostream &operator<<(raw_ostream &OS, const formatBranchInfo &FBI) {
601  FBI.print(OS);
602  return OS;
603}
604
605class LineConsumer {
606  std::unique_ptr<MemoryBuffer> Buffer;
607  StringRef Remaining;
608
609public:
610  LineConsumer() = default;
611  LineConsumer(StringRef Filename) {
612    // Open source files without requiring a NUL terminator. The concurrent
613    // modification may nullify the NUL terminator condition.
614    ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr =
615        MemoryBuffer::getFileOrSTDIN(Filename, /*IsText=*/false,
616                                     /*RequiresNullTerminator=*/false);
617    if (std::error_code EC = BufferOrErr.getError()) {
618      errs() << Filename << ": " << EC.message() << "\n";
619      Remaining = "";
620    } else {
621      Buffer = std::move(BufferOrErr.get());
622      Remaining = Buffer->getBuffer();
623    }
624  }
625  bool empty() { return Remaining.empty(); }
626  void printNext(raw_ostream &OS, uint32_t LineNum) {
627    StringRef Line;
628    if (empty())
629      Line = "/*EOF*/";
630    else
631      std::tie(Line, Remaining) = Remaining.split("\n");
632    OS << format("%5u:", LineNum) << Line << "\n";
633  }
634};
635} // end anonymous namespace
636
637/// Convert a path to a gcov filename. If PreservePaths is true, this
638/// translates "/" to "#", ".." to "^", and drops ".", to match gcov.
639static std::string mangleCoveragePath(StringRef Filename, bool PreservePaths) {
640  if (!PreservePaths)
641    return sys::path::filename(Filename).str();
642
643  // This behaviour is defined by gcov in terms of text replacements, so it's
644  // not likely to do anything useful on filesystems with different textual
645  // conventions.
646  llvm::SmallString<256> Result("");
647  StringRef::iterator I, S, E;
648  for (I = S = Filename.begin(), E = Filename.end(); I != E; ++I) {
649    if (*I != '/')
650      continue;
651
652    if (I - S == 1 && *S == '.') {
653      // ".", the current directory, is skipped.
654    } else if (I - S == 2 && *S == '.' && *(S + 1) == '.') {
655      // "..", the parent directory, is replaced with "^".
656      Result.append("^#");
657    } else {
658      if (S < I)
659        // Leave other components intact,
660        Result.append(S, I);
661      // And separate with "#".
662      Result.push_back('#');
663    }
664    S = I + 1;
665  }
666
667  if (S < I)
668    Result.append(S, I);
669  return std::string(Result);
670}
671
672std::string Context::getCoveragePath(StringRef filename,
673                                     StringRef mainFilename) const {
674  if (options.NoOutput)
675    // This is probably a bug in gcov, but when -n is specified, paths aren't
676    // mangled at all, and the -l and -p options are ignored. Here, we do the
677    // same.
678    return std::string(filename);
679
680  std::string CoveragePath;
681  if (options.LongFileNames && !filename.equals(mainFilename))
682    CoveragePath =
683        mangleCoveragePath(mainFilename, options.PreservePaths) + "##";
684  CoveragePath += mangleCoveragePath(filename, options.PreservePaths);
685  if (options.HashFilenames) {
686    MD5 Hasher;
687    MD5::MD5Result Result;
688    Hasher.update(filename.str());
689    Hasher.final(Result);
690    CoveragePath += "##" + std::string(Result.digest());
691  }
692  CoveragePath += ".gcov";
693  return CoveragePath;
694}
695
696void Context::collectFunction(GCOVFunction &f, Summary &summary) {
697  SourceInfo &si = sources[f.srcIdx];
698  if (f.startLine >= si.startLineToFunctions.size())
699    si.startLineToFunctions.resize(f.startLine + 1);
700  si.startLineToFunctions[f.startLine].push_back(&f);
701  SmallSet<uint32_t, 16> lines;
702  SmallSet<uint32_t, 16> linesExec;
703  for (const GCOVBlock &b : f.blocksRange()) {
704    if (b.lines.empty())
705      continue;
706    uint32_t maxLineNum = *std::max_element(b.lines.begin(), b.lines.end());
707    if (maxLineNum >= si.lines.size())
708      si.lines.resize(maxLineNum + 1);
709    for (uint32_t lineNum : b.lines) {
710      LineInfo &line = si.lines[lineNum];
711      if (lines.insert(lineNum).second)
712        ++summary.lines;
713      if (b.count && linesExec.insert(lineNum).second)
714        ++summary.linesExec;
715      line.exists = true;
716      line.count += b.count;
717      line.blocks.push_back(&b);
718    }
719  }
720}
721
722void Context::collectSourceLine(SourceInfo &si, Summary *summary,
723                                LineInfo &line, size_t lineNum) const {
724  uint64_t count = 0;
725  for (const GCOVBlock *b : line.blocks) {
726    if (b->number == 0) {
727      // For nonstandard control flows, arcs into the exit block may be
728      // duplicately counted (fork) or not be counted (abnormal exit), and thus
729      // the (exit,entry) counter may be inaccurate. Count the entry block with
730      // the outgoing arcs.
731      for (const GCOVArc *arc : b->succ)
732        count += arc->count;
733    } else {
734      // Add counts from predecessors that are not on the same line.
735      for (const GCOVArc *arc : b->pred)
736        if (!llvm::is_contained(line.blocks, &arc->src))
737          count += arc->count;
738    }
739    for (GCOVArc *arc : b->succ)
740      arc->cycleCount = arc->count;
741  }
742
743  count += GCOVBlock::getCyclesCount(line.blocks);
744  line.count = count;
745  if (line.exists) {
746    ++summary->lines;
747    if (line.count != 0)
748      ++summary->linesExec;
749  }
750
751  if (options.BranchInfo)
752    for (const GCOVBlock *b : line.blocks) {
753      if (b->getLastLine() != lineNum)
754        continue;
755      int branches = 0, execBranches = 0, takenBranches = 0;
756      for (const GCOVArc *arc : b->succ) {
757        ++branches;
758        if (count != 0)
759          ++execBranches;
760        if (arc->count != 0)
761          ++takenBranches;
762      }
763      if (branches > 1) {
764        summary->branches += branches;
765        summary->branchesExec += execBranches;
766        summary->branchesTaken += takenBranches;
767      }
768    }
769}
770
771void Context::collectSource(SourceInfo &si, Summary &summary) const {
772  size_t lineNum = 0;
773  for (LineInfo &line : si.lines) {
774    collectSourceLine(si, &summary, line, lineNum);
775    ++lineNum;
776  }
777}
778
779void Context::annotateSource(SourceInfo &si, const GCOVFile &file,
780                             StringRef gcno, StringRef gcda,
781                             raw_ostream &os) const {
782  auto source =
783      options.Intermediate ? LineConsumer() : LineConsumer(si.filename);
784
785  os << "        -:    0:Source:" << si.displayName << '\n';
786  os << "        -:    0:Graph:" << gcno << '\n';
787  os << "        -:    0:Data:" << gcda << '\n';
788  os << "        -:    0:Runs:" << file.runCount << '\n';
789  if (file.version < GCOV::V900)
790    os << "        -:    0:Programs:" << file.programCount << '\n';
791
792  for (size_t lineNum = 1; !source.empty(); ++lineNum) {
793    if (lineNum >= si.lines.size()) {
794      os << "        -:";
795      source.printNext(os, lineNum);
796      continue;
797    }
798
799    const LineInfo &line = si.lines[lineNum];
800    if (options.BranchInfo && lineNum < si.startLineToFunctions.size())
801      for (const auto *f : si.startLineToFunctions[lineNum])
802        printFunctionDetails(*f, os);
803    if (!line.exists)
804      os << "        -:";
805    else if (line.count == 0)
806      os << "    #####:";
807    else
808      os << format("%9" PRIu64 ":", line.count);
809    source.printNext(os, lineNum);
810
811    uint32_t blockIdx = 0, edgeIdx = 0;
812    for (const GCOVBlock *b : line.blocks) {
813      if (b->getLastLine() != lineNum)
814        continue;
815      if (options.AllBlocks) {
816        if (b->getCount() == 0)
817          os << "    $$$$$:";
818        else
819          os << format("%9" PRIu64 ":", b->count);
820        os << format("%5u-block %2u\n", lineNum, blockIdx++);
821      }
822      if (options.BranchInfo) {
823        size_t NumEdges = b->succ.size();
824        if (NumEdges > 1)
825          printBranchInfo(*b, edgeIdx, os);
826        else if (options.UncondBranch && NumEdges == 1) {
827          uint64_t count = b->succ[0]->count;
828          os << format("unconditional %2u ", edgeIdx++)
829             << formatBranchInfo(options, count, count) << '\n';
830        }
831      }
832    }
833  }
834}
835
836void Context::printSourceToIntermediate(const SourceInfo &si,
837                                        raw_ostream &os) const {
838  os << "file:" << si.filename << '\n';
839  for (const auto &fs : si.startLineToFunctions)
840    for (const GCOVFunction *f : fs)
841      os << "function:" << f->startLine << ',' << f->getEntryCount() << ','
842         << f->getName(options.Demangle) << '\n';
843  for (size_t lineNum = 1, size = si.lines.size(); lineNum < size; ++lineNum) {
844    const LineInfo &line = si.lines[lineNum];
845    if (line.blocks.empty())
846      continue;
847    // GCC 8 (r254259) added third third field for Ada:
848    // lcount:<line>,<count>,<has_unexecuted_blocks>
849    // We don't need the third field.
850    os << "lcount:" << lineNum << ',' << line.count << '\n';
851
852    if (!options.BranchInfo)
853      continue;
854    for (const GCOVBlock *b : line.blocks) {
855      if (b->succ.size() < 2 || b->getLastLine() != lineNum)
856        continue;
857      for (const GCOVArc *arc : b->succ) {
858        const char *type =
859            b->getCount() ? arc->count ? "taken" : "nottaken" : "notexec";
860        os << "branch:" << lineNum << ',' << type << '\n';
861      }
862    }
863  }
864}
865
866void Context::print(StringRef filename, StringRef gcno, StringRef gcda,
867                    GCOVFile &file) {
868  for (StringRef filename : file.filenames) {
869    sources.emplace_back(filename);
870    SourceInfo &si = sources.back();
871    si.displayName = si.filename;
872    if (!options.SourcePrefix.empty() &&
873        sys::path::replace_path_prefix(si.displayName, options.SourcePrefix,
874                                       "") &&
875        !si.displayName.empty()) {
876      // TODO replace_path_prefix may strip the prefix even if the remaining
877      // part does not start with a separator.
878      if (sys::path::is_separator(si.displayName[0]))
879        si.displayName.erase(si.displayName.begin());
880      else
881        si.displayName = si.filename;
882    }
883    if (options.RelativeOnly && sys::path::is_absolute(si.displayName))
884      si.ignored = true;
885  }
886
887  raw_ostream &os = llvm::outs();
888  for (GCOVFunction &f : make_pointee_range(file.functions)) {
889    Summary summary(f.getName(options.Demangle));
890    collectFunction(f, summary);
891    if (options.FuncCoverage && !options.UseStdout) {
892      os << "Function '" << summary.Name << "'\n";
893      printSummary(summary, os);
894      os << '\n';
895    }
896  }
897
898  for (SourceInfo &si : sources) {
899    if (si.ignored)
900      continue;
901    Summary summary(si.displayName);
902    collectSource(si, summary);
903
904    // Print file summary unless -t is specified.
905    std::string gcovName = getCoveragePath(si.filename, filename);
906    if (!options.UseStdout) {
907      os << "File '" << summary.Name << "'\n";
908      printSummary(summary, os);
909      if (!options.NoOutput && !options.Intermediate)
910        os << "Creating '" << gcovName << "'\n";
911      os << '\n';
912    }
913
914    if (options.NoOutput || options.Intermediate)
915      continue;
916    std::optional<raw_fd_ostream> os;
917    if (!options.UseStdout) {
918      std::error_code ec;
919      os.emplace(gcovName, ec, sys::fs::OF_TextWithCRLF);
920      if (ec) {
921        errs() << ec.message() << '\n';
922        continue;
923      }
924    }
925    annotateSource(si, file, gcno, gcda,
926                   options.UseStdout ? llvm::outs() : *os);
927  }
928
929  if (options.Intermediate && !options.NoOutput) {
930    // gcov 7.* unexpectedly create multiple .gcov files, which was fixed in 8.0
931    // (PR GCC/82702). We create just one file.
932    std::string outputPath(sys::path::filename(filename));
933    std::error_code ec;
934    raw_fd_ostream os(outputPath + ".gcov", ec, sys::fs::OF_TextWithCRLF);
935    if (ec) {
936      errs() << ec.message() << '\n';
937      return;
938    }
939
940    for (const SourceInfo &si : sources)
941      printSourceToIntermediate(si, os);
942  }
943}
944
945void Context::printFunctionDetails(const GCOVFunction &f,
946                                   raw_ostream &os) const {
947  const uint64_t entryCount = f.getEntryCount();
948  uint32_t blocksExec = 0;
949  const GCOVBlock &exitBlock = f.getExitBlock();
950  uint64_t exitCount = 0;
951  for (const GCOVArc *arc : exitBlock.pred)
952    exitCount += arc->count;
953  for (const GCOVBlock &b : f.blocksRange())
954    if (b.number != 0 && &b != &exitBlock && b.getCount())
955      ++blocksExec;
956
957  os << "function " << f.getName(options.Demangle) << " called " << entryCount
958     << " returned " << formatPercentage(exitCount, entryCount)
959     << "% blocks executed "
960     << formatPercentage(blocksExec, f.blocks.size() - 2) << "%\n";
961}
962
963/// printBranchInfo - Print conditional branch probabilities.
964void Context::printBranchInfo(const GCOVBlock &Block, uint32_t &edgeIdx,
965                              raw_ostream &os) const {
966  uint64_t total = 0;
967  for (const GCOVArc *arc : Block.dsts())
968    total += arc->count;
969  for (const GCOVArc *arc : Block.dsts())
970    os << format("branch %2u ", edgeIdx++)
971       << formatBranchInfo(options, arc->count, total) << '\n';
972}
973
974void Context::printSummary(const Summary &summary, raw_ostream &os) const {
975  os << format("Lines executed:%.2f%% of %" PRIu64 "\n",
976               double(summary.linesExec) * 100 / summary.lines, summary.lines);
977  if (options.BranchInfo) {
978    if (summary.branches == 0) {
979      os << "No branches\n";
980    } else {
981      os << format("Branches executed:%.2f%% of %" PRIu64 "\n",
982                   double(summary.branchesExec) * 100 / summary.branches,
983                   summary.branches);
984      os << format("Taken at least once:%.2f%% of %" PRIu64 "\n",
985                   double(summary.branchesTaken) * 100 / summary.branches,
986                   summary.branches);
987    }
988    os << "No calls\n";
989  }
990}
991
992void llvm::gcovOneInput(const GCOV::Options &options, StringRef filename,
993                        StringRef gcno, StringRef gcda, GCOVFile &file) {
994  Context fi(options);
995  fi.print(filename, gcno, gcda, file);
996}
997