llvm/lib/ProfileData/GCOV.cpp

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