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/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
  29 using namespace llvm;
  30
  31 enum : 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
  45 namespace {
  46 struct 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
  57 struct LineInfo {
  58   SmallVector<const GCOVBlock *, 1> blocks;
  59   uint64_t count = 0;
  60   bool exists = false;
  61 };
  62
  63 struct 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
  72 class Context {
  73 public:
  74   Context(const GCOV::Options &Options) : options(Options) {}
  75   void print(StringRef filename, StringRef gcno, StringRef gcda,
  76              GCOVFile &file);
  77
  78 private:
  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.
 102 bool 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().
 210 bool 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
 307 void 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.
 314 LLVM_DUMP_METHOD void GCOVFile::dump() const { print(dbgs()); }
 315 #endif
 316
 317 unsigned 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
 330 bool GCOVArc::onTree() const { return flags & GCOV_ARC_ON_TREE; }
 331
 332 //===----------------------------------------------------------------------===//
 333 // GCOVFunction implementation.
 334
 335 StringRef 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 }
 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. 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.
 372 void 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
 424 void 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.
 433 LLVM_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
 442 void 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.
 469 LLVM_DUMP_METHOD void GCOVBlock::dump() const { print(dbgs()); }
 470 #endif
 471
 472 uint64_t
 473 GCOVBlock::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.
 524 uint64_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%.
 557 static 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
 567 static 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
 581 namespace {
 582 struct 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
 600 static raw_ostream &operator<<(raw_ostream &OS, const formatBranchInfo &FBI) {
 601   FBI.print(OS);
 602   return OS;
 603 }
 604
 605 class LineConsumer {
 606   std::unique_ptr<MemoryBuffer> Buffer;
 607   StringRef Remaining;
 608
 609 public:
 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.
 639 static 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
 672 std::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 != 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
 696 void 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 = *llvm::max_element(b.lines);
 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
 722 void 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
 771 void 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
 779 void 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
 836 void 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
 866 void 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
 945 void 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.
 964 void 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
 974 void 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
 992 void 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 }