1686 lines · cpp
1//===- CoverageMapping.cpp - Code coverage mapping support ----------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains support for clang's and llvm's instrumentation based10// code coverage.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/ProfileData/Coverage/CoverageMapping.h"15#include "llvm/ADT/ArrayRef.h"16#include "llvm/ADT/DenseMap.h"17#include "llvm/ADT/STLExtras.h"18#include "llvm/ADT/SmallBitVector.h"19#include "llvm/ADT/SmallVector.h"20#include "llvm/ADT/StringExtras.h"21#include "llvm/ADT/StringRef.h"22#include "llvm/Object/BuildID.h"23#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"24#include "llvm/ProfileData/InstrProfReader.h"25#include "llvm/Support/Debug.h"26#include "llvm/Support/Errc.h"27#include "llvm/Support/Error.h"28#include "llvm/Support/ErrorHandling.h"29#include "llvm/Support/MemoryBuffer.h"30#include "llvm/Support/VirtualFileSystem.h"31#include "llvm/Support/raw_ostream.h"32#include <algorithm>33#include <cassert>34#include <cmath>35#include <cstdint>36#include <iterator>37#include <map>38#include <memory>39#include <optional>40#include <stack>41#include <string>42#include <system_error>43#include <utility>44#include <vector>45 46using namespace llvm;47using namespace coverage;48 49#define DEBUG_TYPE "coverage-mapping"50 51Counter CounterExpressionBuilder::get(const CounterExpression &E) {52 auto [It, Inserted] = ExpressionIndices.try_emplace(E, Expressions.size());53 if (Inserted)54 Expressions.push_back(E);55 return Counter::getExpression(It->second);56}57 58void CounterExpressionBuilder::extractTerms(Counter C, int Factor,59 SmallVectorImpl<Term> &Terms) {60 switch (C.getKind()) {61 case Counter::Zero:62 break;63 case Counter::CounterValueReference:64 Terms.emplace_back(C.getCounterID(), Factor);65 break;66 case Counter::Expression:67 const auto &E = Expressions[C.getExpressionID()];68 extractTerms(E.LHS, Factor, Terms);69 extractTerms(70 E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms);71 break;72 }73}74 75Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {76 // Gather constant terms.77 SmallVector<Term, 32> Terms;78 extractTerms(ExpressionTree, +1, Terms);79 80 // If there are no terms, this is just a zero. The algorithm below assumes at81 // least one term.82 if (Terms.size() == 0)83 return Counter::getZero();84 85 // Group the terms by counter ID.86 llvm::sort(Terms, [](const Term &LHS, const Term &RHS) {87 return LHS.CounterID < RHS.CounterID;88 });89 90 // Combine terms by counter ID to eliminate counters that sum to zero.91 auto Prev = Terms.begin();92 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {93 if (I->CounterID == Prev->CounterID) {94 Prev->Factor += I->Factor;95 continue;96 }97 ++Prev;98 *Prev = *I;99 }100 Terms.erase(++Prev, Terms.end());101 102 Counter C;103 // Create additions. We do this before subtractions to avoid constructs like104 // ((0 - X) + Y), as opposed to (Y - X).105 for (auto T : Terms) {106 if (T.Factor <= 0)107 continue;108 for (int I = 0; I < T.Factor; ++I)109 if (C.isZero())110 C = Counter::getCounter(T.CounterID);111 else112 C = get(CounterExpression(CounterExpression::Add, C,113 Counter::getCounter(T.CounterID)));114 }115 116 // Create subtractions.117 for (auto T : Terms) {118 if (T.Factor >= 0)119 continue;120 for (int I = 0; I < -T.Factor; ++I)121 C = get(CounterExpression(CounterExpression::Subtract, C,122 Counter::getCounter(T.CounterID)));123 }124 return C;125}126 127Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS, bool Simplify) {128 auto Cnt = get(CounterExpression(CounterExpression::Add, LHS, RHS));129 return Simplify ? simplify(Cnt) : Cnt;130}131 132Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS,133 bool Simplify) {134 auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS));135 return Simplify ? simplify(Cnt) : Cnt;136}137 138Counter CounterExpressionBuilder::subst(Counter C, const SubstMap &Map) {139 // Replace C with the value found in Map even if C is Expression.140 if (auto I = Map.find(C); I != Map.end())141 return I->second;142 143 if (!C.isExpression())144 return C;145 146 auto CE = Expressions[C.getExpressionID()];147 auto NewLHS = subst(CE.LHS, Map);148 auto NewRHS = subst(CE.RHS, Map);149 150 // Reconstruct Expression with induced subexpressions.151 switch (CE.Kind) {152 case CounterExpression::Add:153 C = add(NewLHS, NewRHS);154 break;155 case CounterExpression::Subtract:156 C = subtract(NewLHS, NewRHS);157 break;158 }159 160 return C;161}162 163void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {164 switch (C.getKind()) {165 case Counter::Zero:166 OS << '0';167 return;168 case Counter::CounterValueReference:169 OS << '#' << C.getCounterID();170 break;171 case Counter::Expression: {172 if (C.getExpressionID() >= Expressions.size())173 return;174 const auto &E = Expressions[C.getExpressionID()];175 OS << '(';176 dump(E.LHS, OS);177 OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");178 dump(E.RHS, OS);179 OS << ')';180 break;181 }182 }183 if (CounterValues.empty())184 return;185 Expected<int64_t> Value = evaluate(C);186 if (auto E = Value.takeError()) {187 consumeError(std::move(E));188 return;189 }190 OS << '[' << *Value << ']';191}192 193Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {194 struct StackElem {195 Counter ICounter;196 int64_t LHS = 0;197 enum {198 KNeverVisited = 0,199 KVisitedOnce = 1,200 KVisitedTwice = 2,201 } VisitCount = KNeverVisited;202 };203 204 std::stack<StackElem> CounterStack;205 CounterStack.push({C});206 207 int64_t LastPoppedValue;208 209 while (!CounterStack.empty()) {210 StackElem &Current = CounterStack.top();211 212 switch (Current.ICounter.getKind()) {213 case Counter::Zero:214 LastPoppedValue = 0;215 CounterStack.pop();216 break;217 case Counter::CounterValueReference:218 if (Current.ICounter.getCounterID() >= CounterValues.size())219 return errorCodeToError(errc::argument_out_of_domain);220 LastPoppedValue = CounterValues[Current.ICounter.getCounterID()];221 CounterStack.pop();222 break;223 case Counter::Expression: {224 if (Current.ICounter.getExpressionID() >= Expressions.size())225 return errorCodeToError(errc::argument_out_of_domain);226 const auto &E = Expressions[Current.ICounter.getExpressionID()];227 if (Current.VisitCount == StackElem::KNeverVisited) {228 CounterStack.push(StackElem{E.LHS});229 Current.VisitCount = StackElem::KVisitedOnce;230 } else if (Current.VisitCount == StackElem::KVisitedOnce) {231 Current.LHS = LastPoppedValue;232 CounterStack.push(StackElem{E.RHS});233 Current.VisitCount = StackElem::KVisitedTwice;234 } else {235 int64_t LHS = Current.LHS;236 int64_t RHS = LastPoppedValue;237 LastPoppedValue =238 E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS;239 CounterStack.pop();240 }241 break;242 }243 }244 }245 246 return LastPoppedValue;247}248 249// Find an independence pair for each condition:250// - The condition is true in one test and false in the other.251// - The decision outcome is true one test and false in the other.252// - All other conditions' values must be equal or marked as "don't care".253void MCDCRecord::findIndependencePairs() {254 if (IndependencePairs)255 return;256 257 IndependencePairs.emplace();258 259 unsigned NumTVs = TV.size();260 // Will be replaced to shorter expr.261 unsigned TVTrueIdx = std::distance(262 TV.begin(),263 llvm::find_if(TV,264 [&](auto I) { return (I.second == MCDCRecord::MCDC_True); })265 266 );267 for (unsigned I = TVTrueIdx; I < NumTVs; ++I) {268 const auto &[A, ACond] = TV[I];269 assert(ACond == MCDCRecord::MCDC_True);270 for (unsigned J = 0; J < TVTrueIdx; ++J) {271 const auto &[B, BCond] = TV[J];272 assert(BCond == MCDCRecord::MCDC_False);273 // If the two vectors differ in exactly one condition, ignoring DontCare274 // conditions, we have found an independence pair.275 auto AB = A.getDifferences(B);276 if (AB.count() == 1)277 IndependencePairs->insert(278 {AB.find_first(), std::make_pair(J + 1, I + 1)});279 }280 }281}282 283mcdc::TVIdxBuilder::TVIdxBuilder(const SmallVectorImpl<ConditionIDs> &NextIDs,284 int Offset)285 : Indices(NextIDs.size()) {286 // Construct Nodes and set up each InCount287 auto N = NextIDs.size();288 SmallVector<MCDCNode> Nodes(N);289 for (unsigned ID = 0; ID < N; ++ID) {290 for (unsigned C = 0; C < 2; ++C) {291#ifndef NDEBUG292 Indices[ID][C] = INT_MIN;293#endif294 auto NextID = NextIDs[ID][C];295 Nodes[ID].NextIDs[C] = NextID;296 if (NextID >= 0)297 ++Nodes[NextID].InCount;298 }299 }300 301 // Sort key ordered by <-Width, Ord>302 SmallVector<std::tuple<int, /// -Width303 unsigned, /// Ord304 int, /// ID305 unsigned /// Cond (0 or 1)306 >>307 Decisions;308 309 // Traverse Nodes to assign Idx310 SmallVector<int> Q;311 assert(Nodes[0].InCount == 0);312 Nodes[0].Width = 1;313 Q.push_back(0);314 315 unsigned Ord = 0;316 while (!Q.empty()) {317 auto IID = Q.begin();318 int ID = *IID;319 Q.erase(IID);320 auto &Node = Nodes[ID];321 assert(Node.Width > 0);322 323 for (unsigned I = 0; I < 2; ++I) {324 auto NextID = Node.NextIDs[I];325 assert(NextID != 0 && "NextID should not point to the top");326 if (NextID < 0) {327 // Decision328 Decisions.emplace_back(-Node.Width, Ord++, ID, I);329 assert(Ord == Decisions.size());330 continue;331 }332 333 // Inter Node334 auto &NextNode = Nodes[NextID];335 assert(NextNode.InCount > 0);336 337 // Assign Idx338 assert(Indices[ID][I] == INT_MIN);339 Indices[ID][I] = NextNode.Width;340 auto NextWidth = int64_t(NextNode.Width) + Node.Width;341 if (NextWidth > HardMaxTVs) {342 NumTestVectors = HardMaxTVs; // Overflow343 return;344 }345 NextNode.Width = NextWidth;346 347 // Ready if all incomings are processed.348 // Or NextNode.Width hasn't been confirmed yet.349 if (--NextNode.InCount == 0)350 Q.push_back(NextID);351 }352 }353 354 llvm::sort(Decisions);355 356 // Assign TestVector Indices in Decision Nodes357 int64_t CurIdx = 0;358 for (auto [NegWidth, Ord, ID, C] : Decisions) {359 int Width = -NegWidth;360 assert(Nodes[ID].Width == Width);361 assert(Nodes[ID].NextIDs[C] < 0);362 assert(Indices[ID][C] == INT_MIN);363 Indices[ID][C] = Offset + CurIdx;364 CurIdx += Width;365 if (CurIdx > HardMaxTVs) {366 NumTestVectors = HardMaxTVs; // Overflow367 return;368 }369 }370 371 assert(CurIdx < HardMaxTVs);372 NumTestVectors = CurIdx;373 374#ifndef NDEBUG375 for (const auto &Idxs : Indices)376 for (auto Idx : Idxs)377 assert(Idx != INT_MIN);378 SavedNodes = std::move(Nodes);379#endif380}381 382namespace {383 384/// Construct this->NextIDs with Branches for TVIdxBuilder to use it385/// before MCDCRecordProcessor().386class NextIDsBuilder {387protected:388 SmallVector<mcdc::ConditionIDs> NextIDs;389 390public:391 NextIDsBuilder(const ArrayRef<const CounterMappingRegion *> Branches)392 : NextIDs(Branches.size()) {393#ifndef NDEBUG394 DenseSet<mcdc::ConditionID> SeenIDs;395#endif396 for (const auto *Branch : Branches) {397 const auto &BranchParams = Branch->getBranchParams();398 assert(SeenIDs.insert(BranchParams.ID).second && "Duplicate CondID");399 NextIDs[BranchParams.ID] = BranchParams.Conds;400 }401 assert(SeenIDs.size() == Branches.size());402 }403};404 405class MCDCRecordProcessor : NextIDsBuilder, mcdc::TVIdxBuilder {406 /// A bitmap representing the executed test vectors for a boolean expression.407 /// Each index of the bitmap corresponds to a possible test vector. An index408 /// with a bit value of '1' indicates that the corresponding Test Vector409 /// identified by that index was executed.410 const BitVector &Bitmap;411 412 /// Decision Region to which the ExecutedTestVectorBitmap applies.413 const CounterMappingRegion &Region;414 const mcdc::DecisionParameters &DecisionParams;415 416 /// Array of branch regions corresponding each conditions in the boolean417 /// expression.418 ArrayRef<const CounterMappingRegion *> Branches;419 420 /// Total number of conditions in the boolean expression.421 unsigned NumConditions;422 423 /// Vector used to track whether a condition is constant folded.424 MCDCRecord::BoolVector Folded;425 426 /// Mapping of calculated MC/DC Independence Pairs for each condition.427 MCDCRecord::TVPairMap IndependencePairs;428 429 /// Storage for ExecVectors430 /// ExecVectors is the alias of its 0th element.431 std::array<MCDCRecord::TestVectors, 2> ExecVectorsByCond;432 433 /// Actual executed Test Vectors for the boolean expression, based on434 /// ExecutedTestVectorBitmap.435 MCDCRecord::TestVectors &ExecVectors;436 437#ifndef NDEBUG438 DenseSet<unsigned> TVIdxs;439#endif440 441 bool IsVersion11;442 443public:444 MCDCRecordProcessor(const BitVector &Bitmap,445 const CounterMappingRegion &Region,446 ArrayRef<const CounterMappingRegion *> Branches,447 bool IsVersion11)448 : NextIDsBuilder(Branches), TVIdxBuilder(this->NextIDs), Bitmap(Bitmap),449 Region(Region), DecisionParams(Region.getDecisionParams()),450 Branches(Branches), NumConditions(DecisionParams.NumConditions),451 Folded{{BitVector(NumConditions), BitVector(NumConditions)}},452 IndependencePairs(NumConditions), ExecVectors(ExecVectorsByCond[false]),453 IsVersion11(IsVersion11) {}454 455private:456 // Walk the binary decision diagram and try assigning both false and true to457 // each node. When a terminal node (ID == 0) is reached, fill in the value in458 // the truth table.459 void buildTestVector(MCDCRecord::TestVector &TV, mcdc::ConditionID ID,460 int TVIdx) {461 for (auto MCDCCond : {MCDCRecord::MCDC_False, MCDCRecord::MCDC_True}) {462 static_assert(MCDCRecord::MCDC_False == 0);463 static_assert(MCDCRecord::MCDC_True == 1);464 TV.set(ID, MCDCCond);465 auto NextID = NextIDs[ID][MCDCCond];466 auto NextTVIdx = TVIdx + Indices[ID][MCDCCond];467 assert(NextID == SavedNodes[ID].NextIDs[MCDCCond]);468 if (NextID >= 0) {469 buildTestVector(TV, NextID, NextTVIdx);470 continue;471 }472 473 assert(TVIdx < SavedNodes[ID].Width);474 assert(TVIdxs.insert(NextTVIdx).second && "Duplicate TVIdx");475 476 if (!Bitmap[IsVersion11477 ? DecisionParams.BitmapIdx * CHAR_BIT + TV.getIndex()478 : DecisionParams.BitmapIdx - NumTestVectors + NextTVIdx])479 continue;480 481 // Copy the completed test vector to the vector of testvectors.482 // The final value (T,F) is equal to the last non-dontcare state on the483 // path (in a short-circuiting system).484 ExecVectorsByCond[MCDCCond].push_back({TV, MCDCCond});485 }486 487 // Reset back to DontCare.488 TV.set(ID, MCDCRecord::MCDC_DontCare);489 }490 491 /// Walk the bits in the bitmap. A bit set to '1' indicates that the test492 /// vector at the corresponding index was executed during a test run.493 void findExecutedTestVectors() {494 // Walk the binary decision diagram to enumerate all possible test vectors.495 // We start at the root node (ID == 0) with all values being DontCare.496 // `TVIdx` starts with 0 and is in the traversal.497 // `Index` encodes the bitmask of true values and is initially 0.498 MCDCRecord::TestVector TV(NumConditions);499 buildTestVector(TV, 0, 0);500 assert(TVIdxs.size() == unsigned(NumTestVectors) &&501 "TVIdxs wasn't fulfilled");502 503 // Fill ExecVectors order by False items and True items.504 // ExecVectors is the alias of ExecVectorsByCond[false], so505 // Append ExecVectorsByCond[true] on it.506 auto &ExecVectorsT = ExecVectorsByCond[true];507 ExecVectors.append(std::make_move_iterator(ExecVectorsT.begin()),508 std::make_move_iterator(ExecVectorsT.end()));509 }510 511public:512 /// Process the MC/DC Record in order to produce a result for a boolean513 /// expression. This process includes tracking the conditions that comprise514 /// the decision region, calculating the list of all possible test vectors,515 /// marking the executed test vectors, and then finding an Independence Pair516 /// out of the executed test vectors for each condition in the boolean517 /// expression. A condition is tracked to ensure that its ID can be mapped to518 /// its ordinal position in the boolean expression. The condition's source519 /// location is also tracked, as well as whether it is constant folded (in520 /// which case it is excuded from the metric).521 MCDCRecord processMCDCRecord() {522 MCDCRecord::CondIDMap PosToID;523 MCDCRecord::LineColPairMap CondLoc;524 525 // Walk the Record's BranchRegions (representing Conditions) in order to:526 // - Hash the condition based on its corresponding ID. This will be used to527 // calculate the test vectors.528 // - Keep a map of the condition's ordinal position (1, 2, 3, 4) to its529 // actual ID. This will be used to visualize the conditions in the530 // correct order.531 // - Keep track of the condition source location. This will be used to532 // visualize where the condition is.533 // - Record whether the condition is constant folded so that we exclude it534 // from being measured.535 for (auto [I, B] : enumerate(Branches)) {536 const auto &BranchParams = B->getBranchParams();537 PosToID[I] = BranchParams.ID;538 CondLoc[I] = B->startLoc();539 Folded[false][I] = B->FalseCount.isZero();540 Folded[true][I] = B->Count.isZero();541 }542 543 // Using Profile Bitmap from runtime, mark the executed test vectors.544 findExecutedTestVectors();545 546 // Record Test vectors, executed vectors, and independence pairs.547 return MCDCRecord(Region, std::move(ExecVectors), std::move(Folded),548 std::move(PosToID), std::move(CondLoc));549 }550};551 552} // namespace553 554Expected<MCDCRecord> CounterMappingContext::evaluateMCDCRegion(555 const CounterMappingRegion &Region,556 ArrayRef<const CounterMappingRegion *> Branches, bool IsVersion11) {557 558 MCDCRecordProcessor MCDCProcessor(Bitmap, Region, Branches, IsVersion11);559 return MCDCProcessor.processMCDCRecord();560}561 562unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const {563 struct StackElem {564 Counter ICounter;565 int64_t LHS = 0;566 enum {567 KNeverVisited = 0,568 KVisitedOnce = 1,569 KVisitedTwice = 2,570 } VisitCount = KNeverVisited;571 };572 573 std::stack<StackElem> CounterStack;574 CounterStack.push({C});575 576 int64_t LastPoppedValue;577 578 while (!CounterStack.empty()) {579 StackElem &Current = CounterStack.top();580 581 switch (Current.ICounter.getKind()) {582 case Counter::Zero:583 LastPoppedValue = 0;584 CounterStack.pop();585 break;586 case Counter::CounterValueReference:587 LastPoppedValue = Current.ICounter.getCounterID();588 CounterStack.pop();589 break;590 case Counter::Expression: {591 if (Current.ICounter.getExpressionID() >= Expressions.size()) {592 LastPoppedValue = 0;593 CounterStack.pop();594 } else {595 const auto &E = Expressions[Current.ICounter.getExpressionID()];596 if (Current.VisitCount == StackElem::KNeverVisited) {597 CounterStack.push(StackElem{E.LHS});598 Current.VisitCount = StackElem::KVisitedOnce;599 } else if (Current.VisitCount == StackElem::KVisitedOnce) {600 Current.LHS = LastPoppedValue;601 CounterStack.push(StackElem{E.RHS});602 Current.VisitCount = StackElem::KVisitedTwice;603 } else {604 int64_t LHS = Current.LHS;605 int64_t RHS = LastPoppedValue;606 LastPoppedValue = std::max(LHS, RHS);607 CounterStack.pop();608 }609 }610 break;611 }612 }613 }614 615 return LastPoppedValue;616}617 618void FunctionRecordIterator::skipOtherFiles() {619 while (Current != Records.end() && !Filename.empty() &&620 Filename != Current->Filenames[0])621 advanceOne();622 if (Current == Records.end())623 *this = FunctionRecordIterator();624}625 626ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename(627 StringRef Filename) const {628 size_t FilenameHash = hash_value(Filename);629 auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash);630 if (RecordIt == FilenameHash2RecordIndices.end())631 return {};632 return RecordIt->second;633}634 635static unsigned getMaxCounterID(const CounterMappingContext &Ctx,636 const CoverageMappingRecord &Record) {637 unsigned MaxCounterID = 0;638 for (const auto &Region : Record.MappingRegions) {639 MaxCounterID = std::max(MaxCounterID, Ctx.getMaxCounterID(Region.Count));640 }641 return MaxCounterID;642}643 644/// Returns the bit count645static unsigned getMaxBitmapSize(const CoverageMappingRecord &Record,646 bool IsVersion11) {647 unsigned MaxBitmapIdx = 0;648 unsigned NumConditions = 0;649 // Scan max(BitmapIdx).650 // Note that `<=` is used insted of `<`, because `BitmapIdx == 0` is valid651 // and `MaxBitmapIdx is `unsigned`. `BitmapIdx` is unique in the record.652 for (const auto &Region : reverse(Record.MappingRegions)) {653 if (Region.Kind != CounterMappingRegion::MCDCDecisionRegion)654 continue;655 const auto &DecisionParams = Region.getDecisionParams();656 if (MaxBitmapIdx <= DecisionParams.BitmapIdx) {657 MaxBitmapIdx = DecisionParams.BitmapIdx;658 NumConditions = DecisionParams.NumConditions;659 }660 }661 662 if (IsVersion11)663 MaxBitmapIdx = MaxBitmapIdx * CHAR_BIT +664 llvm::alignTo(uint64_t(1) << NumConditions, CHAR_BIT);665 666 return MaxBitmapIdx;667}668 669namespace {670 671/// Collect Decisions, Branchs, and Expansions and associate them.672class MCDCDecisionRecorder {673private:674 /// This holds the DecisionRegion and MCDCBranches under it.675 /// Also traverses Expansion(s).676 /// The Decision has the number of MCDCBranches and will complete677 /// when it is filled with unique ConditionID of MCDCBranches.678 struct DecisionRecord {679 const CounterMappingRegion *DecisionRegion;680 681 /// They are reflected from DecisionRegion for convenience.682 mcdc::DecisionParameters DecisionParams;683 LineColPair DecisionStartLoc;684 LineColPair DecisionEndLoc;685 686 /// This is passed to `MCDCRecordProcessor`, so this should be compatible687 /// to`ArrayRef<const CounterMappingRegion *>`.688 SmallVector<const CounterMappingRegion *> MCDCBranches;689 690 /// IDs that are stored in MCDCBranches691 /// Complete when all IDs (1 to NumConditions) are met.692 DenseSet<mcdc::ConditionID> ConditionIDs;693 694 /// Set of IDs of Expansion(s) that are relevant to DecisionRegion695 /// and its children (via expansions).696 /// FileID pointed by ExpandedFileID is dedicated to the expansion, so697 /// the location in the expansion doesn't matter.698 DenseSet<unsigned> ExpandedFileIDs;699 700 DecisionRecord(const CounterMappingRegion &Decision)701 : DecisionRegion(&Decision),702 DecisionParams(Decision.getDecisionParams()),703 DecisionStartLoc(Decision.startLoc()),704 DecisionEndLoc(Decision.endLoc()) {705 assert(Decision.Kind == CounterMappingRegion::MCDCDecisionRegion);706 }707 708 /// Determine whether DecisionRecord dominates `R`.709 bool dominates(const CounterMappingRegion &R) const {710 // Determine whether `R` is included in `DecisionRegion`.711 if (R.FileID == DecisionRegion->FileID &&712 R.startLoc() >= DecisionStartLoc && R.endLoc() <= DecisionEndLoc)713 return true;714 715 // Determine whether `R` is pointed by any of Expansions.716 return ExpandedFileIDs.contains(R.FileID);717 }718 719 enum Result {720 NotProcessed = 0, /// Irrelevant to this Decision721 Processed, /// Added to this Decision722 Completed, /// Added and filled this Decision723 };724 725 /// Add Branch into the Decision726 /// \param Branch expects MCDCBranchRegion727 /// \returns NotProcessed/Processed/Completed728 Result addBranch(const CounterMappingRegion &Branch) {729 assert(Branch.Kind == CounterMappingRegion::MCDCBranchRegion);730 731 auto ConditionID = Branch.getBranchParams().ID;732 733 if (ConditionIDs.contains(ConditionID) ||734 ConditionID >= DecisionParams.NumConditions)735 return NotProcessed;736 737 if (!this->dominates(Branch))738 return NotProcessed;739 740 assert(MCDCBranches.size() < DecisionParams.NumConditions);741 742 // Put `ID=0` in front of `MCDCBranches` for convenience743 // even if `MCDCBranches` is not topological.744 if (ConditionID == 0)745 MCDCBranches.insert(MCDCBranches.begin(), &Branch);746 else747 MCDCBranches.push_back(&Branch);748 749 // Mark `ID` as `assigned`.750 ConditionIDs.insert(ConditionID);751 752 // `Completed` when `MCDCBranches` is full753 return (MCDCBranches.size() == DecisionParams.NumConditions ? Completed754 : Processed);755 }756 757 /// Record Expansion if it is relevant to this Decision.758 /// Each `Expansion` may nest.759 /// \returns true if recorded.760 bool recordExpansion(const CounterMappingRegion &Expansion) {761 if (!this->dominates(Expansion))762 return false;763 764 ExpandedFileIDs.insert(Expansion.ExpandedFileID);765 return true;766 }767 };768 769private:770 /// Decisions in progress771 /// DecisionRecord is added for each MCDCDecisionRegion.772 /// DecisionRecord is removed when Decision is completed.773 SmallVector<DecisionRecord> Decisions;774 775public:776 ~MCDCDecisionRecorder() {777 assert(Decisions.empty() && "All Decisions have not been resolved");778 }779 780 /// Register Region and start recording.781 void registerDecision(const CounterMappingRegion &Decision) {782 Decisions.emplace_back(Decision);783 }784 785 void recordExpansion(const CounterMappingRegion &Expansion) {786 any_of(Decisions, [&Expansion](auto &Decision) {787 return Decision.recordExpansion(Expansion);788 });789 }790 791 using DecisionAndBranches =792 std::pair<const CounterMappingRegion *, /// Decision793 SmallVector<const CounterMappingRegion *> /// Branches794 >;795 796 /// Add MCDCBranchRegion to DecisionRecord.797 /// \param Branch to be processed798 /// \returns DecisionsAndBranches if DecisionRecord completed.799 /// Or returns nullopt.800 std::optional<DecisionAndBranches>801 processBranch(const CounterMappingRegion &Branch) {802 // Seek each Decision and apply Region to it.803 for (auto DecisionIter = Decisions.begin(), DecisionEnd = Decisions.end();804 DecisionIter != DecisionEnd; ++DecisionIter)805 switch (DecisionIter->addBranch(Branch)) {806 case DecisionRecord::NotProcessed:807 continue;808 case DecisionRecord::Processed:809 return std::nullopt;810 case DecisionRecord::Completed:811 DecisionAndBranches Result =812 std::make_pair(DecisionIter->DecisionRegion,813 std::move(DecisionIter->MCDCBranches));814 Decisions.erase(DecisionIter); // No longer used.815 return Result;816 }817 818 llvm_unreachable("Branch not found in Decisions");819 }820};821 822} // namespace823 824Error CoverageMapping::loadFunctionRecord(825 const CoverageMappingRecord &Record,826 const std::optional<std::reference_wrapper<IndexedInstrProfReader>>827 &ProfileReader) {828 StringRef OrigFuncName = Record.FunctionName;829 if (OrigFuncName.empty())830 return make_error<CoverageMapError>(coveragemap_error::malformed,831 "record function name is empty");832 833 if (Record.Filenames.empty())834 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);835 else836 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);837 838 CounterMappingContext Ctx(Record.Expressions);839 840 std::vector<uint64_t> Counts;841 if (ProfileReader) {842 if (Error E = ProfileReader.value().get().getFunctionCounts(843 Record.FunctionName, Record.FunctionHash, Counts)) {844 instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E)));845 if (IPE == instrprof_error::hash_mismatch) {846 FuncHashMismatches.emplace_back(std::string(Record.FunctionName),847 Record.FunctionHash);848 return Error::success();849 }850 if (IPE != instrprof_error::unknown_function)851 return make_error<InstrProfError>(IPE);852 Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0);853 }854 } else {855 Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0);856 }857 Ctx.setCounts(Counts);858 859 bool IsVersion11 =860 ProfileReader && ProfileReader.value().get().getVersion() <861 IndexedInstrProf::ProfVersion::Version12;862 863 BitVector Bitmap;864 if (ProfileReader) {865 if (Error E = ProfileReader.value().get().getFunctionBitmap(866 Record.FunctionName, Record.FunctionHash, Bitmap)) {867 instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E)));868 if (IPE == instrprof_error::hash_mismatch) {869 FuncHashMismatches.emplace_back(std::string(Record.FunctionName),870 Record.FunctionHash);871 return Error::success();872 }873 if (IPE != instrprof_error::unknown_function)874 return make_error<InstrProfError>(IPE);875 Bitmap = BitVector(getMaxBitmapSize(Record, IsVersion11));876 }877 } else {878 Bitmap = BitVector(getMaxBitmapSize(Record, false));879 }880 Ctx.setBitmap(std::move(Bitmap));881 882 assert(!Record.MappingRegions.empty() && "Function has no regions");883 884 // This coverage record is a zero region for a function that's unused in885 // some TU, but used in a different TU. Ignore it. The coverage maps from the886 // the other TU will either be loaded (providing full region counts) or they887 // won't (in which case we don't unintuitively report functions as uncovered888 // when they have non-zero counts in the profile).889 if (Record.MappingRegions.size() == 1 &&890 Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)891 return Error::success();892 893 MCDCDecisionRecorder MCDCDecisions;894 FunctionRecord Function(OrigFuncName, Record.Filenames);895 for (const auto &Region : Record.MappingRegions) {896 // MCDCDecisionRegion should be handled first since it overlaps with897 // others inside.898 if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) {899 MCDCDecisions.registerDecision(Region);900 continue;901 }902 Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);903 if (auto E = ExecutionCount.takeError()) {904 consumeError(std::move(E));905 return Error::success();906 }907 Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount);908 if (auto E = AltExecutionCount.takeError()) {909 consumeError(std::move(E));910 return Error::success();911 }912 Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount);913 914 // Record ExpansionRegion.915 if (Region.Kind == CounterMappingRegion::ExpansionRegion) {916 MCDCDecisions.recordExpansion(Region);917 continue;918 }919 920 // Do nothing unless MCDCBranchRegion.921 if (Region.Kind != CounterMappingRegion::MCDCBranchRegion)922 continue;923 924 auto Result = MCDCDecisions.processBranch(Region);925 if (!Result) // Any Decision doesn't complete.926 continue;927 928 auto MCDCDecision = Result->first;929 auto &MCDCBranches = Result->second;930 931 // Since the bitmap identifies the executed test vectors for an MC/DC932 // DecisionRegion, all of the information is now available to process.933 // This is where the bulk of the MC/DC progressing takes place.934 Expected<MCDCRecord> Record =935 Ctx.evaluateMCDCRegion(*MCDCDecision, MCDCBranches, IsVersion11);936 if (auto E = Record.takeError()) {937 consumeError(std::move(E));938 return Error::success();939 }940 941 // Save the MC/DC Record so that it can be visualized later.942 Function.pushMCDCRecord(std::move(*Record));943 }944 945 // Don't create records for (filenames, function) pairs we've already seen.946 auto FilenamesHash = hash_combine_range(Record.Filenames);947 if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)948 return Error::success();949 950 Functions.push_back(std::move(Function));951 952 // Performance optimization: keep track of the indices of the function records953 // which correspond to each filename. This can be used to substantially speed954 // up queries for coverage info in a file.955 unsigned RecordIndex = Functions.size() - 1;956 for (StringRef Filename : Record.Filenames) {957 auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)];958 // Note that there may be duplicates in the filename set for a function959 // record, because of e.g. macro expansions in the function in which both960 // the macro and the function are defined in the same file.961 if (RecordIndices.empty() || RecordIndices.back() != RecordIndex)962 RecordIndices.push_back(RecordIndex);963 }964 965 return Error::success();966}967 968// This function is for memory optimization by shortening the lifetimes969// of CoverageMappingReader instances.970Error CoverageMapping::loadFromReaders(971 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,972 std::optional<std::reference_wrapper<IndexedInstrProfReader>>973 &ProfileReader,974 CoverageMapping &Coverage) {975 assert(!Coverage.SingleByteCoverage || !ProfileReader ||976 *Coverage.SingleByteCoverage ==977 ProfileReader.value().get().hasSingleByteCoverage());978 Coverage.SingleByteCoverage =979 !ProfileReader || ProfileReader.value().get().hasSingleByteCoverage();980 for (const auto &CoverageReader : CoverageReaders) {981 for (auto RecordOrErr : *CoverageReader) {982 if (Error E = RecordOrErr.takeError())983 return E;984 const auto &Record = *RecordOrErr;985 if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader))986 return E;987 }988 }989 return Error::success();990}991 992Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(993 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,994 std::optional<std::reference_wrapper<IndexedInstrProfReader>>995 &ProfileReader) {996 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());997 if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage))998 return std::move(E);999 return std::move(Coverage);1000}1001 1002// If E is a no_data_found error, returns success. Otherwise returns E.1003static Error handleMaybeNoDataFoundError(Error E) {1004 return handleErrors(std::move(E), [](const CoverageMapError &CME) {1005 if (CME.get() == coveragemap_error::no_data_found)1006 return static_cast<Error>(Error::success());1007 return make_error<CoverageMapError>(CME.get(), CME.getMessage());1008 });1009}1010 1011Error CoverageMapping::loadFromFile(1012 StringRef Filename, StringRef Arch, StringRef CompilationDir,1013 std::optional<std::reference_wrapper<IndexedInstrProfReader>>1014 &ProfileReader,1015 CoverageMapping &Coverage, bool &DataFound,1016 SmallVectorImpl<object::BuildID> *FoundBinaryIDs) {1017 auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(1018 Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false);1019 if (std::error_code EC = CovMappingBufOrErr.getError())1020 return createFileError(Filename, errorCodeToError(EC));1021 MemoryBufferRef CovMappingBufRef =1022 CovMappingBufOrErr.get()->getMemBufferRef();1023 SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers;1024 1025 SmallVector<object::BuildIDRef> BinaryIDs;1026 auto CoverageReadersOrErr = BinaryCoverageReader::create(1027 CovMappingBufRef, Arch, Buffers, CompilationDir,1028 FoundBinaryIDs ? &BinaryIDs : nullptr);1029 if (Error E = CoverageReadersOrErr.takeError()) {1030 E = handleMaybeNoDataFoundError(std::move(E));1031 if (E)1032 return createFileError(Filename, std::move(E));1033 return E;1034 }1035 1036 SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers;1037 for (auto &Reader : CoverageReadersOrErr.get())1038 Readers.push_back(std::move(Reader));1039 if (FoundBinaryIDs && !Readers.empty()) {1040 llvm::append_range(*FoundBinaryIDs,1041 llvm::map_range(BinaryIDs, [](object::BuildIDRef BID) {1042 return object::BuildID(BID);1043 }));1044 }1045 DataFound |= !Readers.empty();1046 if (Error E = loadFromReaders(Readers, ProfileReader, Coverage))1047 return createFileError(Filename, std::move(E));1048 return Error::success();1049}1050 1051Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(1052 ArrayRef<StringRef> ObjectFilenames,1053 std::optional<StringRef> ProfileFilename, vfs::FileSystem &FS,1054 ArrayRef<StringRef> Arches, StringRef CompilationDir,1055 const object::BuildIDFetcher *BIDFetcher, bool CheckBinaryIDs) {1056 std::unique_ptr<IndexedInstrProfReader> ProfileReader;1057 if (ProfileFilename) {1058 auto ProfileReaderOrErr =1059 IndexedInstrProfReader::create(ProfileFilename.value(), FS);1060 if (Error E = ProfileReaderOrErr.takeError())1061 return createFileError(ProfileFilename.value(), std::move(E));1062 ProfileReader = std::move(ProfileReaderOrErr.get());1063 }1064 auto ProfileReaderRef =1065 ProfileReader1066 ? std::optional<std::reference_wrapper<IndexedInstrProfReader>>(1067 *ProfileReader)1068 : std::nullopt;1069 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());1070 bool DataFound = false;1071 1072 auto GetArch = [&](size_t Idx) {1073 if (Arches.empty())1074 return StringRef();1075 if (Arches.size() == 1)1076 return Arches.front();1077 return Arches[Idx];1078 };1079 1080 SmallVector<object::BuildID> FoundBinaryIDs;1081 for (const auto &File : llvm::enumerate(ObjectFilenames)) {1082 if (Error E = loadFromFile(File.value(), GetArch(File.index()),1083 CompilationDir, ProfileReaderRef, *Coverage,1084 DataFound, &FoundBinaryIDs))1085 return std::move(E);1086 }1087 1088 if (BIDFetcher) {1089 std::vector<object::BuildID> ProfileBinaryIDs;1090 if (ProfileReader)1091 if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs))1092 return createFileError(ProfileFilename.value(), std::move(E));1093 1094 SmallVector<object::BuildIDRef> BinaryIDsToFetch;1095 if (!ProfileBinaryIDs.empty()) {1096 const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) {1097 return std::lexicographical_compare(A.begin(), A.end(), B.begin(),1098 B.end());1099 };1100 llvm::sort(FoundBinaryIDs, Compare);1101 std::set_difference(1102 ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(),1103 FoundBinaryIDs.begin(), FoundBinaryIDs.end(),1104 std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare);1105 }1106 1107 for (object::BuildIDRef BinaryID : BinaryIDsToFetch) {1108 std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID);1109 if (PathOpt) {1110 std::string Path = std::move(*PathOpt);1111 StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef();1112 if (Error E = loadFromFile(Path, Arch, CompilationDir, ProfileReaderRef,1113 *Coverage, DataFound))1114 return std::move(E);1115 } else if (CheckBinaryIDs) {1116 return createFileError(1117 ProfileFilename.value(),1118 createStringError(errc::no_such_file_or_directory,1119 "Missing binary ID: " +1120 llvm::toHex(BinaryID, /*LowerCase=*/true)));1121 }1122 }1123 }1124 1125 if (!DataFound)1126 return createFileError(1127 join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "),1128 make_error<CoverageMapError>(coveragemap_error::no_data_found));1129 return std::move(Coverage);1130}1131 1132namespace {1133 1134/// Distributes functions into instantiation sets.1135///1136/// An instantiation set is a collection of functions that have the same source1137/// code, ie, template functions specializations.1138class FunctionInstantiationSetCollector {1139 using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;1140 MapT InstantiatedFunctions;1141 1142public:1143 void insert(const FunctionRecord &Function, unsigned FileID) {1144 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();1145 while (I != E && I->FileID != FileID)1146 ++I;1147 assert(I != E && "function does not cover the given file");1148 auto &Functions = InstantiatedFunctions[I->startLoc()];1149 Functions.push_back(&Function);1150 }1151 1152 MapT::iterator begin() { return InstantiatedFunctions.begin(); }1153 MapT::iterator end() { return InstantiatedFunctions.end(); }1154};1155 1156class SegmentBuilder {1157 std::vector<CoverageSegment> &Segments;1158 SmallVector<const CountedRegion *, 8> ActiveRegions;1159 1160 SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}1161 1162 /// Emit a segment with the count from \p Region starting at \p StartLoc.1163 //1164 /// \p IsRegionEntry: The segment is at the start of a new non-gap region.1165 /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.1166 void startSegment(const CountedRegion &Region, LineColPair StartLoc,1167 bool IsRegionEntry, bool EmitSkippedRegion = false) {1168 bool HasCount = !EmitSkippedRegion &&1169 (Region.Kind != CounterMappingRegion::SkippedRegion);1170 1171 // If the new segment wouldn't affect coverage rendering, skip it.1172 if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {1173 const auto &Last = Segments.back();1174 if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&1175 !Last.IsRegionEntry)1176 return;1177 }1178 1179 if (HasCount)1180 Segments.emplace_back(StartLoc.first, StartLoc.second,1181 Region.ExecutionCount, IsRegionEntry,1182 Region.Kind == CounterMappingRegion::GapRegion);1183 else1184 Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);1185 1186 LLVM_DEBUG({1187 const auto &Last = Segments.back();1188 dbgs() << "Segment at " << Last.Line << ":" << Last.Col1189 << " (count = " << Last.Count << ")"1190 << (Last.IsRegionEntry ? ", RegionEntry" : "")1191 << (!Last.HasCount ? ", Skipped" : "")1192 << (Last.IsGapRegion ? ", Gap" : "") << "\n";1193 });1194 }1195 1196 /// Emit segments for active regions which end before \p Loc.1197 ///1198 /// \p Loc: The start location of the next region. If std::nullopt, all active1199 /// regions are completed.1200 /// \p FirstCompletedRegion: Index of the first completed region.1201 void completeRegionsUntil(std::optional<LineColPair> Loc,1202 unsigned FirstCompletedRegion) {1203 // Sort the completed regions by end location. This makes it simple to1204 // emit closing segments in sorted order.1205 auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;1206 std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),1207 [](const CountedRegion *L, const CountedRegion *R) {1208 return L->endLoc() < R->endLoc();1209 });1210 1211 // Emit segments for all completed regions.1212 for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;1213 ++I) {1214 const auto *CompletedRegion = ActiveRegions[I];1215 assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&1216 "Completed region ends after start of new region");1217 1218 const auto *PrevCompletedRegion = ActiveRegions[I - 1];1219 auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();1220 1221 // Don't emit any more segments if they start where the new region begins.1222 if (Loc && CompletedSegmentLoc == *Loc)1223 break;1224 1225 // Don't emit a segment if the next completed region ends at the same1226 // location as this one.1227 if (CompletedSegmentLoc == CompletedRegion->endLoc())1228 continue;1229 1230 // Use the count from the last completed region which ends at this loc.1231 for (unsigned J = I + 1; J < E; ++J)1232 if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())1233 CompletedRegion = ActiveRegions[J];1234 1235 startSegment(*CompletedRegion, CompletedSegmentLoc, false);1236 }1237 1238 auto Last = ActiveRegions.back();1239 if (FirstCompletedRegion && Last->endLoc() != *Loc) {1240 // If there's a gap after the end of the last completed region and the1241 // start of the new region, use the last active region to fill the gap.1242 startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),1243 false);1244 } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {1245 // Emit a skipped segment if there are no more active regions. This1246 // ensures that gaps between functions are marked correctly.1247 startSegment(*Last, Last->endLoc(), false, true);1248 }1249 1250 // Pop the completed regions.1251 ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());1252 }1253 1254 void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {1255 for (const auto &CR : enumerate(Regions)) {1256 auto CurStartLoc = CR.value().startLoc();1257 1258 // Active regions which end before the current region need to be popped.1259 auto CompletedRegions =1260 std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),1261 [&](const CountedRegion *Region) {1262 return !(Region->endLoc() <= CurStartLoc);1263 });1264 if (CompletedRegions != ActiveRegions.end()) {1265 unsigned FirstCompletedRegion =1266 std::distance(ActiveRegions.begin(), CompletedRegions);1267 completeRegionsUntil(CurStartLoc, FirstCompletedRegion);1268 }1269 1270 bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;1271 1272 // Try to emit a segment for the current region.1273 if (CurStartLoc == CR.value().endLoc()) {1274 // Avoid making zero-length regions active. If it's the last region,1275 // emit a skipped segment. Otherwise use its predecessor's count.1276 const bool Skipped =1277 (CR.index() + 1) == Regions.size() ||1278 CR.value().Kind == CounterMappingRegion::SkippedRegion;1279 startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),1280 CurStartLoc, !GapRegion, Skipped);1281 // If it is skipped segment, create a segment with last pushed1282 // regions's count at CurStartLoc.1283 if (Skipped && !ActiveRegions.empty())1284 startSegment(*ActiveRegions.back(), CurStartLoc, false);1285 continue;1286 }1287 if (CR.index() + 1 == Regions.size() ||1288 CurStartLoc != Regions[CR.index() + 1].startLoc()) {1289 // Emit a segment if the next region doesn't start at the same location1290 // as this one.1291 startSegment(CR.value(), CurStartLoc, !GapRegion);1292 }1293 1294 // This region is active (i.e not completed).1295 ActiveRegions.push_back(&CR.value());1296 }1297 1298 // Complete any remaining active regions.1299 if (!ActiveRegions.empty())1300 completeRegionsUntil(std::nullopt, 0);1301 }1302 1303 /// Sort a nested sequence of regions from a single file.1304 static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {1305 llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) {1306 if (LHS.startLoc() != RHS.startLoc())1307 return LHS.startLoc() < RHS.startLoc();1308 if (LHS.endLoc() != RHS.endLoc())1309 // When LHS completely contains RHS, we sort LHS first.1310 return RHS.endLoc() < LHS.endLoc();1311 // If LHS and RHS cover the same area, we need to sort them according1312 // to their kinds so that the most suitable region will become "active"1313 // in combineRegions(). Because we accumulate counter values only from1314 // regions of the same kind as the first region of the area, prefer1315 // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.1316 static_assert(CounterMappingRegion::CodeRegion <1317 CounterMappingRegion::ExpansionRegion &&1318 CounterMappingRegion::ExpansionRegion <1319 CounterMappingRegion::SkippedRegion,1320 "Unexpected order of region kind values");1321 return LHS.Kind < RHS.Kind;1322 });1323 }1324 1325 /// Combine counts of regions which cover the same area.1326 static ArrayRef<CountedRegion>1327 combineRegions(MutableArrayRef<CountedRegion> Regions) {1328 if (Regions.empty())1329 return Regions;1330 auto Active = Regions.begin();1331 auto End = Regions.end();1332 for (auto I = Regions.begin() + 1; I != End; ++I) {1333 if (Active->startLoc() != I->startLoc() ||1334 Active->endLoc() != I->endLoc()) {1335 // Shift to the next region.1336 ++Active;1337 if (Active != I)1338 *Active = *I;1339 continue;1340 }1341 // Merge duplicate region.1342 // If CodeRegions and ExpansionRegions cover the same area, it's probably1343 // a macro which is fully expanded to another macro. In that case, we need1344 // to accumulate counts only from CodeRegions, or else the area will be1345 // counted twice.1346 // On the other hand, a macro may have a nested macro in its body. If the1347 // outer macro is used several times, the ExpansionRegion for the nested1348 // macro will also be added several times. These ExpansionRegions cover1349 // the same source locations and have to be combined to reach the correct1350 // value for that area.1351 // We add counts of the regions of the same kind as the active region1352 // to handle the both situations.1353 if (I->Kind == Active->Kind)1354 Active->ExecutionCount += I->ExecutionCount;1355 }1356 return Regions.drop_back(std::distance(++Active, End));1357 }1358 1359public:1360 /// Build a sorted list of CoverageSegments from a list of Regions.1361 static std::vector<CoverageSegment>1362 buildSegments(MutableArrayRef<CountedRegion> Regions) {1363 std::vector<CoverageSegment> Segments;1364 SegmentBuilder Builder(Segments);1365 1366 sortNestedRegions(Regions);1367 ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);1368 1369 LLVM_DEBUG({1370 dbgs() << "Combined regions:\n";1371 for (const auto &CR : CombinedRegions)1372 dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> "1373 << CR.LineEnd << ":" << CR.ColumnEnd1374 << " (count=" << CR.ExecutionCount << ")\n";1375 });1376 1377 Builder.buildSegmentsImpl(CombinedRegions);1378 1379#ifndef NDEBUG1380 for (unsigned I = 1, E = Segments.size(); I < E; ++I) {1381 const auto &L = Segments[I - 1];1382 const auto &R = Segments[I];1383 if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {1384 if (L.Line == R.Line && L.Col == R.Col && !L.HasCount)1385 continue;1386 LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col1387 << " followed by " << R.Line << ":" << R.Col << "\n");1388 assert(false && "Coverage segments not unique or sorted");1389 }1390 }1391#endif1392 1393 return Segments;1394 }1395};1396 1397} // end anonymous namespace1398 1399std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {1400 std::vector<StringRef> Filenames;1401 for (const auto &Function : getCoveredFunctions())1402 llvm::append_range(Filenames, Function.Filenames);1403 llvm::sort(Filenames);1404 auto Last = llvm::unique(Filenames);1405 Filenames.erase(Last, Filenames.end());1406 return Filenames;1407}1408 1409static SmallBitVector gatherFileIDs(StringRef SourceFile,1410 const FunctionRecord &Function) {1411 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);1412 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)1413 if (SourceFile == Function.Filenames[I])1414 FilenameEquivalence[I] = true;1415 return FilenameEquivalence;1416}1417 1418/// Return the ID of the file where the definition of the function is located.1419static std::optional<unsigned>1420findMainViewFileID(const FunctionRecord &Function) {1421 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);1422 for (const auto &CR : Function.CountedRegions)1423 if (CR.Kind == CounterMappingRegion::ExpansionRegion)1424 IsNotExpandedFile[CR.ExpandedFileID] = false;1425 int I = IsNotExpandedFile.find_first();1426 if (I == -1)1427 return std::nullopt;1428 return I;1429}1430 1431/// Check if SourceFile is the file that contains the definition of1432/// the Function. Return the ID of the file in that case or std::nullopt1433/// otherwise.1434static std::optional<unsigned>1435findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) {1436 std::optional<unsigned> I = findMainViewFileID(Function);1437 if (I && SourceFile == Function.Filenames[*I])1438 return I;1439 return std::nullopt;1440}1441 1442static bool isExpansion(const CountedRegion &R, unsigned FileID) {1443 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;1444}1445 1446CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {1447 assert(SingleByteCoverage);1448 CoverageData FileCoverage(*SingleByteCoverage, Filename);1449 std::vector<CountedRegion> Regions;1450 1451 // Look up the function records in the given file. Due to hash collisions on1452 // the filename, we may get back some records that are not in the file.1453 ArrayRef<unsigned> RecordIndices =1454 getImpreciseRecordIndicesForFilename(Filename);1455 for (unsigned RecordIndex : RecordIndices) {1456 const FunctionRecord &Function = Functions[RecordIndex];1457 auto MainFileID = findMainViewFileID(Filename, Function);1458 auto FileIDs = gatherFileIDs(Filename, Function);1459 for (const auto &CR : Function.CountedRegions)1460 if (FileIDs.test(CR.FileID)) {1461 Regions.push_back(CR);1462 if (MainFileID && isExpansion(CR, *MainFileID))1463 FileCoverage.Expansions.emplace_back(CR, Function);1464 }1465 // Capture branch regions specific to the function (excluding expansions).1466 for (const auto &CR : Function.CountedBranchRegions)1467 if (FileIDs.test(CR.FileID))1468 FileCoverage.BranchRegions.push_back(CR);1469 // Capture MCDC records specific to the function.1470 for (const auto &MR : Function.MCDCRecords)1471 if (FileIDs.test(MR.getDecisionRegion().FileID))1472 FileCoverage.MCDCRecords.push_back(MR);1473 }1474 1475 LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");1476 FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);1477 1478 return FileCoverage;1479}1480 1481std::vector<InstantiationGroup>1482CoverageMapping::getInstantiationGroups(StringRef Filename) const {1483 FunctionInstantiationSetCollector InstantiationSetCollector;1484 // Look up the function records in the given file. Due to hash collisions on1485 // the filename, we may get back some records that are not in the file.1486 ArrayRef<unsigned> RecordIndices =1487 getImpreciseRecordIndicesForFilename(Filename);1488 for (unsigned RecordIndex : RecordIndices) {1489 const FunctionRecord &Function = Functions[RecordIndex];1490 auto MainFileID = findMainViewFileID(Filename, Function);1491 if (!MainFileID)1492 continue;1493 InstantiationSetCollector.insert(Function, *MainFileID);1494 }1495 1496 std::vector<InstantiationGroup> Result;1497 for (auto &InstantiationSet : InstantiationSetCollector) {1498 InstantiationGroup IG{InstantiationSet.first.first,1499 InstantiationSet.first.second,1500 std::move(InstantiationSet.second)};1501 Result.emplace_back(std::move(IG));1502 }1503 return Result;1504}1505 1506CoverageData1507CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {1508 auto MainFileID = findMainViewFileID(Function);1509 if (!MainFileID)1510 return CoverageData();1511 1512 assert(SingleByteCoverage);1513 CoverageData FunctionCoverage(*SingleByteCoverage,1514 Function.Filenames[*MainFileID]);1515 std::vector<CountedRegion> Regions;1516 for (const auto &CR : Function.CountedRegions)1517 if (CR.FileID == *MainFileID) {1518 Regions.push_back(CR);1519 if (isExpansion(CR, *MainFileID))1520 FunctionCoverage.Expansions.emplace_back(CR, Function);1521 }1522 // Capture branch regions specific to the function (excluding expansions).1523 for (const auto &CR : Function.CountedBranchRegions)1524 if (CR.FileID == *MainFileID)1525 FunctionCoverage.BranchRegions.push_back(CR);1526 1527 // Capture MCDC records specific to the function.1528 for (const auto &MR : Function.MCDCRecords)1529 if (MR.getDecisionRegion().FileID == *MainFileID)1530 FunctionCoverage.MCDCRecords.push_back(MR);1531 1532 LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name1533 << "\n");1534 FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);1535 1536 return FunctionCoverage;1537}1538 1539CoverageData CoverageMapping::getCoverageForExpansion(1540 const ExpansionRecord &Expansion) const {1541 assert(SingleByteCoverage);1542 CoverageData ExpansionCoverage(1543 *SingleByteCoverage, Expansion.Function.Filenames[Expansion.FileID]);1544 std::vector<CountedRegion> Regions;1545 for (const auto &CR : Expansion.Function.CountedRegions)1546 if (CR.FileID == Expansion.FileID) {1547 Regions.push_back(CR);1548 if (isExpansion(CR, Expansion.FileID))1549 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);1550 }1551 for (const auto &CR : Expansion.Function.CountedBranchRegions)1552 // Capture branch regions that only pertain to the corresponding expansion.1553 if (CR.FileID == Expansion.FileID)1554 ExpansionCoverage.BranchRegions.push_back(CR);1555 1556 LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "1557 << Expansion.FileID << "\n");1558 ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);1559 1560 return ExpansionCoverage;1561}1562 1563LineCoverageStats::LineCoverageStats(1564 ArrayRef<const CoverageSegment *> LineSegments,1565 const CoverageSegment *WrappedSegment, unsigned Line)1566 : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),1567 LineSegments(LineSegments), WrappedSegment(WrappedSegment) {1568 // Find the minimum number of regions which start in this line.1569 unsigned MinRegionCount = 0;1570 auto isStartOfRegion = [](const CoverageSegment *S) {1571 return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;1572 };1573 for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)1574 if (isStartOfRegion(LineSegments[I]))1575 ++MinRegionCount;1576 1577 bool StartOfSkippedRegion = !LineSegments.empty() &&1578 !LineSegments.front()->HasCount &&1579 LineSegments.front()->IsRegionEntry;1580 1581 HasMultipleRegions = MinRegionCount > 1;1582 Mapped =1583 !StartOfSkippedRegion &&1584 ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));1585 1586 // if there is any starting segment at this line with a counter, it must be1587 // mapped1588 Mapped |= any_of(LineSegments, [](const auto *Seq) {1589 return Seq->IsRegionEntry && Seq->HasCount;1590 });1591 1592 if (!Mapped) {1593 return;1594 }1595 1596 // Pick the max count from the non-gap, region entry segments and the1597 // wrapped count.1598 if (WrappedSegment)1599 ExecutionCount = WrappedSegment->Count;1600 if (!MinRegionCount)1601 return;1602 for (const auto *LS : LineSegments)1603 if (isStartOfRegion(LS))1604 ExecutionCount = std::max(ExecutionCount, LS->Count);1605}1606 1607LineCoverageIterator &LineCoverageIterator::operator++() {1608 if (Next == CD.end()) {1609 Stats = LineCoverageStats();1610 Ended = true;1611 return *this;1612 }1613 if (Segments.size())1614 WrappedSegment = Segments.back();1615 Segments.clear();1616 while (Next != CD.end() && Next->Line == Line)1617 Segments.push_back(&*Next++);1618 Stats = LineCoverageStats(Segments, WrappedSegment, Line);1619 ++Line;1620 return *this;1621}1622 1623static std::string getCoverageMapErrString(coveragemap_error Err,1624 const std::string &ErrMsg = "") {1625 std::string Msg;1626 raw_string_ostream OS(Msg);1627 1628 switch (Err) {1629 case coveragemap_error::success:1630 OS << "success";1631 break;1632 case coveragemap_error::eof:1633 OS << "end of File";1634 break;1635 case coveragemap_error::no_data_found:1636 OS << "no coverage data found";1637 break;1638 case coveragemap_error::unsupported_version:1639 OS << "unsupported coverage format version";1640 break;1641 case coveragemap_error::truncated:1642 OS << "truncated coverage data";1643 break;1644 case coveragemap_error::malformed:1645 OS << "malformed coverage data";1646 break;1647 case coveragemap_error::decompression_failed:1648 OS << "failed to decompress coverage data (zlib)";1649 break;1650 case coveragemap_error::invalid_or_missing_arch_specifier:1651 OS << "`-arch` specifier is invalid or missing for universal binary";1652 break;1653 }1654 1655 // If optional error message is not empty, append it to the message.1656 if (!ErrMsg.empty())1657 OS << ": " << ErrMsg;1658 1659 return Msg;1660}1661 1662namespace {1663 1664// FIXME: This class is only here to support the transition to llvm::Error. It1665// will be removed once this transition is complete. Clients should prefer to1666// deal with the Error value directly, rather than converting to error_code.1667class CoverageMappingErrorCategoryType : public std::error_category {1668 const char *name() const noexcept override { return "llvm.coveragemap"; }1669 std::string message(int IE) const override {1670 return getCoverageMapErrString(static_cast<coveragemap_error>(IE));1671 }1672};1673 1674} // end anonymous namespace1675 1676std::string CoverageMapError::message() const {1677 return getCoverageMapErrString(Err, Msg);1678}1679 1680const std::error_category &llvm::coverage::coveragemap_category() {1681 static CoverageMappingErrorCategoryType ErrorCategory;1682 return ErrorCategory;1683}1684 1685char CoverageMapError::ID = 0;1686