diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp | 1633 |
1 files changed, 1633 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/contrib/llvm-project/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp new file mode 100644 index 000000000000..21ce0ac17d61 --- /dev/null +++ b/contrib/llvm-project/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -0,0 +1,1633 @@ +//===- CoverageMapping.cpp - Code coverage mapping support ----------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains support for clang's and llvm's instrumentation based +// code coverage. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ProfileData/Coverage/CoverageMapping.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallBitVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Object/BuildID.h" +#include "llvm/ProfileData/Coverage/CoverageMappingReader.h" +#include "llvm/ProfileData/InstrProfReader.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Errc.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/VirtualFileSystem.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <cmath> +#include <cstdint> +#include <iterator> +#include <map> +#include <memory> +#include <optional> +#include <stack> +#include <string> +#include <system_error> +#include <utility> +#include <vector> + +using namespace llvm; +using namespace coverage; + +#define DEBUG_TYPE "coverage-mapping" + +Counter CounterExpressionBuilder::get(const CounterExpression &E) { + auto It = ExpressionIndices.find(E); + if (It != ExpressionIndices.end()) + return Counter::getExpression(It->second); + unsigned I = Expressions.size(); + Expressions.push_back(E); + ExpressionIndices[E] = I; + return Counter::getExpression(I); +} + +void CounterExpressionBuilder::extractTerms(Counter C, int Factor, + SmallVectorImpl<Term> &Terms) { + switch (C.getKind()) { + case Counter::Zero: + break; + case Counter::CounterValueReference: + Terms.emplace_back(C.getCounterID(), Factor); + break; + case Counter::Expression: + const auto &E = Expressions[C.getExpressionID()]; + extractTerms(E.LHS, Factor, Terms); + extractTerms( + E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms); + break; + } +} + +Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { + // Gather constant terms. + SmallVector<Term, 32> Terms; + extractTerms(ExpressionTree, +1, Terms); + + // If there are no terms, this is just a zero. The algorithm below assumes at + // least one term. + if (Terms.size() == 0) + return Counter::getZero(); + + // Group the terms by counter ID. + llvm::sort(Terms, [](const Term &LHS, const Term &RHS) { + return LHS.CounterID < RHS.CounterID; + }); + + // Combine terms by counter ID to eliminate counters that sum to zero. + auto Prev = Terms.begin(); + for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { + if (I->CounterID == Prev->CounterID) { + Prev->Factor += I->Factor; + continue; + } + ++Prev; + *Prev = *I; + } + Terms.erase(++Prev, Terms.end()); + + Counter C; + // Create additions. We do this before subtractions to avoid constructs like + // ((0 - X) + Y), as opposed to (Y - X). + for (auto T : Terms) { + if (T.Factor <= 0) + continue; + for (int I = 0; I < T.Factor; ++I) + if (C.isZero()) + C = Counter::getCounter(T.CounterID); + else + C = get(CounterExpression(CounterExpression::Add, C, + Counter::getCounter(T.CounterID))); + } + + // Create subtractions. + for (auto T : Terms) { + if (T.Factor >= 0) + continue; + for (int I = 0; I < -T.Factor; ++I) + C = get(CounterExpression(CounterExpression::Subtract, C, + Counter::getCounter(T.CounterID))); + } + return C; +} + +Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS, bool Simplify) { + auto Cnt = get(CounterExpression(CounterExpression::Add, LHS, RHS)); + return Simplify ? simplify(Cnt) : Cnt; +} + +Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS, + bool Simplify) { + auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS)); + return Simplify ? simplify(Cnt) : Cnt; +} + +void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { + switch (C.getKind()) { + case Counter::Zero: + OS << '0'; + return; + case Counter::CounterValueReference: + OS << '#' << C.getCounterID(); + break; + case Counter::Expression: { + if (C.getExpressionID() >= Expressions.size()) + return; + const auto &E = Expressions[C.getExpressionID()]; + OS << '('; + dump(E.LHS, OS); + OS << (E.Kind == CounterExpression::Subtract ? " - " : " + "); + dump(E.RHS, OS); + OS << ')'; + break; + } + } + if (CounterValues.empty()) + return; + Expected<int64_t> Value = evaluate(C); + if (auto E = Value.takeError()) { + consumeError(std::move(E)); + return; + } + OS << '[' << *Value << ']'; +} + +Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { + struct StackElem { + Counter ICounter; + int64_t LHS = 0; + enum { + KNeverVisited = 0, + KVisitedOnce = 1, + KVisitedTwice = 2, + } VisitCount = KNeverVisited; + }; + + std::stack<StackElem> CounterStack; + CounterStack.push({C}); + + int64_t LastPoppedValue; + + while (!CounterStack.empty()) { + StackElem &Current = CounterStack.top(); + + switch (Current.ICounter.getKind()) { + case Counter::Zero: + LastPoppedValue = 0; + CounterStack.pop(); + break; + case Counter::CounterValueReference: + if (Current.ICounter.getCounterID() >= CounterValues.size()) + return errorCodeToError(errc::argument_out_of_domain); + LastPoppedValue = CounterValues[Current.ICounter.getCounterID()]; + CounterStack.pop(); + break; + case Counter::Expression: { + if (Current.ICounter.getExpressionID() >= Expressions.size()) + return errorCodeToError(errc::argument_out_of_domain); + const auto &E = Expressions[Current.ICounter.getExpressionID()]; + if (Current.VisitCount == StackElem::KNeverVisited) { + CounterStack.push(StackElem{E.LHS}); + Current.VisitCount = StackElem::KVisitedOnce; + } else if (Current.VisitCount == StackElem::KVisitedOnce) { + Current.LHS = LastPoppedValue; + CounterStack.push(StackElem{E.RHS}); + Current.VisitCount = StackElem::KVisitedTwice; + } else { + int64_t LHS = Current.LHS; + int64_t RHS = LastPoppedValue; + LastPoppedValue = + E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS; + CounterStack.pop(); + } + break; + } + } + } + + return LastPoppedValue; +} + +mcdc::TVIdxBuilder::TVIdxBuilder(const SmallVectorImpl<ConditionIDs> &NextIDs, + int Offset) + : Indices(NextIDs.size()) { + // Construct Nodes and set up each InCount + auto N = NextIDs.size(); + SmallVector<MCDCNode> Nodes(N); + for (unsigned ID = 0; ID < N; ++ID) { + for (unsigned C = 0; C < 2; ++C) { +#ifndef NDEBUG + Indices[ID][C] = INT_MIN; +#endif + auto NextID = NextIDs[ID][C]; + Nodes[ID].NextIDs[C] = NextID; + if (NextID >= 0) + ++Nodes[NextID].InCount; + } + } + + // Sort key ordered by <-Width, Ord> + SmallVector<std::tuple<int, /// -Width + unsigned, /// Ord + int, /// ID + unsigned /// Cond (0 or 1) + >> + Decisions; + + // Traverse Nodes to assign Idx + SmallVector<int> Q; + assert(Nodes[0].InCount == 0); + Nodes[0].Width = 1; + Q.push_back(0); + + unsigned Ord = 0; + while (!Q.empty()) { + auto IID = Q.begin(); + int ID = *IID; + Q.erase(IID); + auto &Node = Nodes[ID]; + assert(Node.Width > 0); + + for (unsigned I = 0; I < 2; ++I) { + auto NextID = Node.NextIDs[I]; + assert(NextID != 0 && "NextID should not point to the top"); + if (NextID < 0) { + // Decision + Decisions.emplace_back(-Node.Width, Ord++, ID, I); + assert(Ord == Decisions.size()); + continue; + } + + // Inter Node + auto &NextNode = Nodes[NextID]; + assert(NextNode.InCount > 0); + + // Assign Idx + assert(Indices[ID][I] == INT_MIN); + Indices[ID][I] = NextNode.Width; + auto NextWidth = int64_t(NextNode.Width) + Node.Width; + if (NextWidth > HardMaxTVs) { + NumTestVectors = HardMaxTVs; // Overflow + return; + } + NextNode.Width = NextWidth; + + // Ready if all incomings are processed. + // Or NextNode.Width hasn't been confirmed yet. + if (--NextNode.InCount == 0) + Q.push_back(NextID); + } + } + + llvm::sort(Decisions); + + // Assign TestVector Indices in Decision Nodes + int64_t CurIdx = 0; + for (auto [NegWidth, Ord, ID, C] : Decisions) { + int Width = -NegWidth; + assert(Nodes[ID].Width == Width); + assert(Nodes[ID].NextIDs[C] < 0); + assert(Indices[ID][C] == INT_MIN); + Indices[ID][C] = Offset + CurIdx; + CurIdx += Width; + if (CurIdx > HardMaxTVs) { + NumTestVectors = HardMaxTVs; // Overflow + return; + } + } + + assert(CurIdx < HardMaxTVs); + NumTestVectors = CurIdx; + +#ifndef NDEBUG + for (const auto &Idxs : Indices) + for (auto Idx : Idxs) + assert(Idx != INT_MIN); + SavedNodes = std::move(Nodes); +#endif +} + +namespace { + +/// Construct this->NextIDs with Branches for TVIdxBuilder to use it +/// before MCDCRecordProcessor(). +class NextIDsBuilder { +protected: + SmallVector<mcdc::ConditionIDs> NextIDs; + +public: + NextIDsBuilder(const ArrayRef<const CounterMappingRegion *> Branches) + : NextIDs(Branches.size()) { +#ifndef NDEBUG + DenseSet<mcdc::ConditionID> SeenIDs; +#endif + for (const auto *Branch : Branches) { + const auto &BranchParams = Branch->getBranchParams(); + assert(SeenIDs.insert(BranchParams.ID).second && "Duplicate CondID"); + NextIDs[BranchParams.ID] = BranchParams.Conds; + } + assert(SeenIDs.size() == Branches.size()); + } +}; + +class MCDCRecordProcessor : NextIDsBuilder, mcdc::TVIdxBuilder { + /// A bitmap representing the executed test vectors for a boolean expression. + /// Each index of the bitmap corresponds to a possible test vector. An index + /// with a bit value of '1' indicates that the corresponding Test Vector + /// identified by that index was executed. + const BitVector &Bitmap; + + /// Decision Region to which the ExecutedTestVectorBitmap applies. + const CounterMappingRegion &Region; + const mcdc::DecisionParameters &DecisionParams; + + /// Array of branch regions corresponding each conditions in the boolean + /// expression. + ArrayRef<const CounterMappingRegion *> Branches; + + /// Total number of conditions in the boolean expression. + unsigned NumConditions; + + /// Vector used to track whether a condition is constant folded. + MCDCRecord::BoolVector Folded; + + /// Mapping of calculated MC/DC Independence Pairs for each condition. + MCDCRecord::TVPairMap IndependencePairs; + + /// Storage for ExecVectors + /// ExecVectors is the alias of its 0th element. + std::array<MCDCRecord::TestVectors, 2> ExecVectorsByCond; + + /// Actual executed Test Vectors for the boolean expression, based on + /// ExecutedTestVectorBitmap. + MCDCRecord::TestVectors &ExecVectors; + + /// Number of False items in ExecVectors + unsigned NumExecVectorsF; + +#ifndef NDEBUG + DenseSet<unsigned> TVIdxs; +#endif + + bool IsVersion11; + +public: + MCDCRecordProcessor(const BitVector &Bitmap, + const CounterMappingRegion &Region, + ArrayRef<const CounterMappingRegion *> Branches, + bool IsVersion11) + : NextIDsBuilder(Branches), TVIdxBuilder(this->NextIDs), Bitmap(Bitmap), + Region(Region), DecisionParams(Region.getDecisionParams()), + Branches(Branches), NumConditions(DecisionParams.NumConditions), + Folded(NumConditions, false), IndependencePairs(NumConditions), + ExecVectors(ExecVectorsByCond[false]), IsVersion11(IsVersion11) {} + +private: + // Walk the binary decision diagram and try assigning both false and true to + // each node. When a terminal node (ID == 0) is reached, fill in the value in + // the truth table. + void buildTestVector(MCDCRecord::TestVector &TV, mcdc::ConditionID ID, + int TVIdx) { + for (auto MCDCCond : {MCDCRecord::MCDC_False, MCDCRecord::MCDC_True}) { + static_assert(MCDCRecord::MCDC_False == 0); + static_assert(MCDCRecord::MCDC_True == 1); + TV.set(ID, MCDCCond); + auto NextID = NextIDs[ID][MCDCCond]; + auto NextTVIdx = TVIdx + Indices[ID][MCDCCond]; + assert(NextID == SavedNodes[ID].NextIDs[MCDCCond]); + if (NextID >= 0) { + buildTestVector(TV, NextID, NextTVIdx); + continue; + } + + assert(TVIdx < SavedNodes[ID].Width); + assert(TVIdxs.insert(NextTVIdx).second && "Duplicate TVIdx"); + + if (!Bitmap[IsVersion11 + ? DecisionParams.BitmapIdx * CHAR_BIT + TV.getIndex() + : DecisionParams.BitmapIdx - NumTestVectors + NextTVIdx]) + continue; + + // Copy the completed test vector to the vector of testvectors. + // The final value (T,F) is equal to the last non-dontcare state on the + // path (in a short-circuiting system). + ExecVectorsByCond[MCDCCond].push_back({TV, MCDCCond}); + } + + // Reset back to DontCare. + TV.set(ID, MCDCRecord::MCDC_DontCare); + } + + /// Walk the bits in the bitmap. A bit set to '1' indicates that the test + /// vector at the corresponding index was executed during a test run. + void findExecutedTestVectors() { + // Walk the binary decision diagram to enumerate all possible test vectors. + // We start at the root node (ID == 0) with all values being DontCare. + // `TVIdx` starts with 0 and is in the traversal. + // `Index` encodes the bitmask of true values and is initially 0. + MCDCRecord::TestVector TV(NumConditions); + buildTestVector(TV, 0, 0); + assert(TVIdxs.size() == unsigned(NumTestVectors) && + "TVIdxs wasn't fulfilled"); + + // Fill ExecVectors order by False items and True items. + // ExecVectors is the alias of ExecVectorsByCond[false], so + // Append ExecVectorsByCond[true] on it. + NumExecVectorsF = ExecVectors.size(); + auto &ExecVectorsT = ExecVectorsByCond[true]; + ExecVectors.append(std::make_move_iterator(ExecVectorsT.begin()), + std::make_move_iterator(ExecVectorsT.end())); + } + + // Find an independence pair for each condition: + // - The condition is true in one test and false in the other. + // - The decision outcome is true one test and false in the other. + // - All other conditions' values must be equal or marked as "don't care". + void findIndependencePairs() { + unsigned NumTVs = ExecVectors.size(); + for (unsigned I = NumExecVectorsF; I < NumTVs; ++I) { + const auto &[A, ACond] = ExecVectors[I]; + assert(ACond == MCDCRecord::MCDC_True); + for (unsigned J = 0; J < NumExecVectorsF; ++J) { + const auto &[B, BCond] = ExecVectors[J]; + assert(BCond == MCDCRecord::MCDC_False); + // If the two vectors differ in exactly one condition, ignoring DontCare + // conditions, we have found an independence pair. + auto AB = A.getDifferences(B); + if (AB.count() == 1) + IndependencePairs.insert( + {AB.find_first(), std::make_pair(J + 1, I + 1)}); + } + } + } + +public: + /// Process the MC/DC Record in order to produce a result for a boolean + /// expression. This process includes tracking the conditions that comprise + /// the decision region, calculating the list of all possible test vectors, + /// marking the executed test vectors, and then finding an Independence Pair + /// out of the executed test vectors for each condition in the boolean + /// expression. A condition is tracked to ensure that its ID can be mapped to + /// its ordinal position in the boolean expression. The condition's source + /// location is also tracked, as well as whether it is constant folded (in + /// which case it is excuded from the metric). + MCDCRecord processMCDCRecord() { + unsigned I = 0; + MCDCRecord::CondIDMap PosToID; + MCDCRecord::LineColPairMap CondLoc; + + // Walk the Record's BranchRegions (representing Conditions) in order to: + // - Hash the condition based on its corresponding ID. This will be used to + // calculate the test vectors. + // - Keep a map of the condition's ordinal position (1, 2, 3, 4) to its + // actual ID. This will be used to visualize the conditions in the + // correct order. + // - Keep track of the condition source location. This will be used to + // visualize where the condition is. + // - Record whether the condition is constant folded so that we exclude it + // from being measured. + for (const auto *B : Branches) { + const auto &BranchParams = B->getBranchParams(); + PosToID[I] = BranchParams.ID; + CondLoc[I] = B->startLoc(); + Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero()); + } + + // Using Profile Bitmap from runtime, mark the executed test vectors. + findExecutedTestVectors(); + + // Compare executed test vectors against each other to find an independence + // pairs for each condition. This processing takes the most time. + findIndependencePairs(); + + // Record Test vectors, executed vectors, and independence pairs. + return MCDCRecord(Region, std::move(ExecVectors), + std::move(IndependencePairs), std::move(Folded), + std::move(PosToID), std::move(CondLoc)); + } +}; + +} // namespace + +Expected<MCDCRecord> CounterMappingContext::evaluateMCDCRegion( + const CounterMappingRegion &Region, + ArrayRef<const CounterMappingRegion *> Branches, bool IsVersion11) { + + MCDCRecordProcessor MCDCProcessor(Bitmap, Region, Branches, IsVersion11); + return MCDCProcessor.processMCDCRecord(); +} + +unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const { + struct StackElem { + Counter ICounter; + int64_t LHS = 0; + enum { + KNeverVisited = 0, + KVisitedOnce = 1, + KVisitedTwice = 2, + } VisitCount = KNeverVisited; + }; + + std::stack<StackElem> CounterStack; + CounterStack.push({C}); + + int64_t LastPoppedValue; + + while (!CounterStack.empty()) { + StackElem &Current = CounterStack.top(); + + switch (Current.ICounter.getKind()) { + case Counter::Zero: + LastPoppedValue = 0; + CounterStack.pop(); + break; + case Counter::CounterValueReference: + LastPoppedValue = Current.ICounter.getCounterID(); + CounterStack.pop(); + break; + case Counter::Expression: { + if (Current.ICounter.getExpressionID() >= Expressions.size()) { + LastPoppedValue = 0; + CounterStack.pop(); + } else { + const auto &E = Expressions[Current.ICounter.getExpressionID()]; + if (Current.VisitCount == StackElem::KNeverVisited) { + CounterStack.push(StackElem{E.LHS}); + Current.VisitCount = StackElem::KVisitedOnce; + } else if (Current.VisitCount == StackElem::KVisitedOnce) { + Current.LHS = LastPoppedValue; + CounterStack.push(StackElem{E.RHS}); + Current.VisitCount = StackElem::KVisitedTwice; + } else { + int64_t LHS = Current.LHS; + int64_t RHS = LastPoppedValue; + LastPoppedValue = std::max(LHS, RHS); + CounterStack.pop(); + } + } + break; + } + } + } + + return LastPoppedValue; +} + +void FunctionRecordIterator::skipOtherFiles() { + while (Current != Records.end() && !Filename.empty() && + Filename != Current->Filenames[0]) + ++Current; + if (Current == Records.end()) + *this = FunctionRecordIterator(); +} + +ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename( + StringRef Filename) const { + size_t FilenameHash = hash_value(Filename); + auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash); + if (RecordIt == FilenameHash2RecordIndices.end()) + return {}; + return RecordIt->second; +} + +static unsigned getMaxCounterID(const CounterMappingContext &Ctx, + const CoverageMappingRecord &Record) { + unsigned MaxCounterID = 0; + for (const auto &Region : Record.MappingRegions) { + MaxCounterID = std::max(MaxCounterID, Ctx.getMaxCounterID(Region.Count)); + } + return MaxCounterID; +} + +/// Returns the bit count +static unsigned getMaxBitmapSize(const CoverageMappingRecord &Record, + bool IsVersion11) { + unsigned MaxBitmapIdx = 0; + unsigned NumConditions = 0; + // Scan max(BitmapIdx). + // Note that `<=` is used insted of `<`, because `BitmapIdx == 0` is valid + // and `MaxBitmapIdx is `unsigned`. `BitmapIdx` is unique in the record. + for (const auto &Region : reverse(Record.MappingRegions)) { + if (Region.Kind != CounterMappingRegion::MCDCDecisionRegion) + continue; + const auto &DecisionParams = Region.getDecisionParams(); + if (MaxBitmapIdx <= DecisionParams.BitmapIdx) { + MaxBitmapIdx = DecisionParams.BitmapIdx; + NumConditions = DecisionParams.NumConditions; + } + } + + if (IsVersion11) + MaxBitmapIdx = MaxBitmapIdx * CHAR_BIT + + llvm::alignTo(uint64_t(1) << NumConditions, CHAR_BIT); + + return MaxBitmapIdx; +} + +namespace { + +/// Collect Decisions, Branchs, and Expansions and associate them. +class MCDCDecisionRecorder { +private: + /// This holds the DecisionRegion and MCDCBranches under it. + /// Also traverses Expansion(s). + /// The Decision has the number of MCDCBranches and will complete + /// when it is filled with unique ConditionID of MCDCBranches. + struct DecisionRecord { + const CounterMappingRegion *DecisionRegion; + + /// They are reflected from DecisionRegion for convenience. + mcdc::DecisionParameters DecisionParams; + LineColPair DecisionStartLoc; + LineColPair DecisionEndLoc; + + /// This is passed to `MCDCRecordProcessor`, so this should be compatible + /// to`ArrayRef<const CounterMappingRegion *>`. + SmallVector<const CounterMappingRegion *> MCDCBranches; + + /// IDs that are stored in MCDCBranches + /// Complete when all IDs (1 to NumConditions) are met. + DenseSet<mcdc::ConditionID> ConditionIDs; + + /// Set of IDs of Expansion(s) that are relevant to DecisionRegion + /// and its children (via expansions). + /// FileID pointed by ExpandedFileID is dedicated to the expansion, so + /// the location in the expansion doesn't matter. + DenseSet<unsigned> ExpandedFileIDs; + + DecisionRecord(const CounterMappingRegion &Decision) + : DecisionRegion(&Decision), + DecisionParams(Decision.getDecisionParams()), + DecisionStartLoc(Decision.startLoc()), + DecisionEndLoc(Decision.endLoc()) { + assert(Decision.Kind == CounterMappingRegion::MCDCDecisionRegion); + } + + /// Determine whether DecisionRecord dominates `R`. + bool dominates(const CounterMappingRegion &R) const { + // Determine whether `R` is included in `DecisionRegion`. + if (R.FileID == DecisionRegion->FileID && + R.startLoc() >= DecisionStartLoc && R.endLoc() <= DecisionEndLoc) + return true; + + // Determine whether `R` is pointed by any of Expansions. + return ExpandedFileIDs.contains(R.FileID); + } + + enum Result { + NotProcessed = 0, /// Irrelevant to this Decision + Processed, /// Added to this Decision + Completed, /// Added and filled this Decision + }; + + /// Add Branch into the Decision + /// \param Branch expects MCDCBranchRegion + /// \returns NotProcessed/Processed/Completed + Result addBranch(const CounterMappingRegion &Branch) { + assert(Branch.Kind == CounterMappingRegion::MCDCBranchRegion); + + auto ConditionID = Branch.getBranchParams().ID; + + if (ConditionIDs.contains(ConditionID) || + ConditionID >= DecisionParams.NumConditions) + return NotProcessed; + + if (!this->dominates(Branch)) + return NotProcessed; + + assert(MCDCBranches.size() < DecisionParams.NumConditions); + + // Put `ID=0` in front of `MCDCBranches` for convenience + // even if `MCDCBranches` is not topological. + if (ConditionID == 0) + MCDCBranches.insert(MCDCBranches.begin(), &Branch); + else + MCDCBranches.push_back(&Branch); + + // Mark `ID` as `assigned`. + ConditionIDs.insert(ConditionID); + + // `Completed` when `MCDCBranches` is full + return (MCDCBranches.size() == DecisionParams.NumConditions ? Completed + : Processed); + } + + /// Record Expansion if it is relevant to this Decision. + /// Each `Expansion` may nest. + /// \returns true if recorded. + bool recordExpansion(const CounterMappingRegion &Expansion) { + if (!this->dominates(Expansion)) + return false; + + ExpandedFileIDs.insert(Expansion.ExpandedFileID); + return true; + } + }; + +private: + /// Decisions in progress + /// DecisionRecord is added for each MCDCDecisionRegion. + /// DecisionRecord is removed when Decision is completed. + SmallVector<DecisionRecord> Decisions; + +public: + ~MCDCDecisionRecorder() { + assert(Decisions.empty() && "All Decisions have not been resolved"); + } + + /// Register Region and start recording. + void registerDecision(const CounterMappingRegion &Decision) { + Decisions.emplace_back(Decision); + } + + void recordExpansion(const CounterMappingRegion &Expansion) { + any_of(Decisions, [&Expansion](auto &Decision) { + return Decision.recordExpansion(Expansion); + }); + } + + using DecisionAndBranches = + std::pair<const CounterMappingRegion *, /// Decision + SmallVector<const CounterMappingRegion *> /// Branches + >; + + /// Add MCDCBranchRegion to DecisionRecord. + /// \param Branch to be processed + /// \returns DecisionsAndBranches if DecisionRecord completed. + /// Or returns nullopt. + std::optional<DecisionAndBranches> + processBranch(const CounterMappingRegion &Branch) { + // Seek each Decision and apply Region to it. + for (auto DecisionIter = Decisions.begin(), DecisionEnd = Decisions.end(); + DecisionIter != DecisionEnd; ++DecisionIter) + switch (DecisionIter->addBranch(Branch)) { + case DecisionRecord::NotProcessed: + continue; + case DecisionRecord::Processed: + return std::nullopt; + case DecisionRecord::Completed: + DecisionAndBranches Result = + std::make_pair(DecisionIter->DecisionRegion, + std::move(DecisionIter->MCDCBranches)); + Decisions.erase(DecisionIter); // No longer used. + return Result; + } + + llvm_unreachable("Branch not found in Decisions"); + } +}; + +} // namespace + +Error CoverageMapping::loadFunctionRecord( + const CoverageMappingRecord &Record, + IndexedInstrProfReader &ProfileReader) { + StringRef OrigFuncName = Record.FunctionName; + if (OrigFuncName.empty()) + return make_error<CoverageMapError>(coveragemap_error::malformed, + "record function name is empty"); + + if (Record.Filenames.empty()) + OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); + else + OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); + + CounterMappingContext Ctx(Record.Expressions); + + std::vector<uint64_t> Counts; + if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, + Record.FunctionHash, Counts)) { + instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E))); + if (IPE == instrprof_error::hash_mismatch) { + FuncHashMismatches.emplace_back(std::string(Record.FunctionName), + Record.FunctionHash); + return Error::success(); + } + if (IPE != instrprof_error::unknown_function) + return make_error<InstrProfError>(IPE); + Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0); + } + Ctx.setCounts(Counts); + + bool IsVersion11 = + ProfileReader.getVersion() < IndexedInstrProf::ProfVersion::Version12; + + BitVector Bitmap; + if (Error E = ProfileReader.getFunctionBitmap(Record.FunctionName, + Record.FunctionHash, Bitmap)) { + instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E))); + if (IPE == instrprof_error::hash_mismatch) { + FuncHashMismatches.emplace_back(std::string(Record.FunctionName), + Record.FunctionHash); + return Error::success(); + } + if (IPE != instrprof_error::unknown_function) + return make_error<InstrProfError>(IPE); + Bitmap = BitVector(getMaxBitmapSize(Record, IsVersion11)); + } + Ctx.setBitmap(std::move(Bitmap)); + + assert(!Record.MappingRegions.empty() && "Function has no regions"); + + // This coverage record is a zero region for a function that's unused in + // some TU, but used in a different TU. Ignore it. The coverage maps from the + // the other TU will either be loaded (providing full region counts) or they + // won't (in which case we don't unintuitively report functions as uncovered + // when they have non-zero counts in the profile). + if (Record.MappingRegions.size() == 1 && + Record.MappingRegions[0].Count.isZero() && Counts[0] > 0) + return Error::success(); + + MCDCDecisionRecorder MCDCDecisions; + FunctionRecord Function(OrigFuncName, Record.Filenames); + for (const auto &Region : Record.MappingRegions) { + // MCDCDecisionRegion should be handled first since it overlaps with + // others inside. + if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) { + MCDCDecisions.registerDecision(Region); + continue; + } + Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); + if (auto E = ExecutionCount.takeError()) { + consumeError(std::move(E)); + return Error::success(); + } + Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount); + if (auto E = AltExecutionCount.takeError()) { + consumeError(std::move(E)); + return Error::success(); + } + Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount, + ProfileReader.hasSingleByteCoverage()); + + // Record ExpansionRegion. + if (Region.Kind == CounterMappingRegion::ExpansionRegion) { + MCDCDecisions.recordExpansion(Region); + continue; + } + + // Do nothing unless MCDCBranchRegion. + if (Region.Kind != CounterMappingRegion::MCDCBranchRegion) + continue; + + auto Result = MCDCDecisions.processBranch(Region); + if (!Result) // Any Decision doesn't complete. + continue; + + auto MCDCDecision = Result->first; + auto &MCDCBranches = Result->second; + + // Since the bitmap identifies the executed test vectors for an MC/DC + // DecisionRegion, all of the information is now available to process. + // This is where the bulk of the MC/DC progressing takes place. + Expected<MCDCRecord> Record = + Ctx.evaluateMCDCRegion(*MCDCDecision, MCDCBranches, IsVersion11); + if (auto E = Record.takeError()) { + consumeError(std::move(E)); + return Error::success(); + } + + // Save the MC/DC Record so that it can be visualized later. + Function.pushMCDCRecord(std::move(*Record)); + } + + // Don't create records for (filenames, function) pairs we've already seen. + auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), + Record.Filenames.end()); + if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) + return Error::success(); + + Functions.push_back(std::move(Function)); + + // Performance optimization: keep track of the indices of the function records + // which correspond to each filename. This can be used to substantially speed + // up queries for coverage info in a file. + unsigned RecordIndex = Functions.size() - 1; + for (StringRef Filename : Record.Filenames) { + auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)]; + // Note that there may be duplicates in the filename set for a function + // record, because of e.g. macro expansions in the function in which both + // the macro and the function are defined in the same file. + if (RecordIndices.empty() || RecordIndices.back() != RecordIndex) + RecordIndices.push_back(RecordIndex); + } + + return Error::success(); +} + +// This function is for memory optimization by shortening the lifetimes +// of CoverageMappingReader instances. +Error CoverageMapping::loadFromReaders( + ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, + IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) { + for (const auto &CoverageReader : CoverageReaders) { + for (auto RecordOrErr : *CoverageReader) { + if (Error E = RecordOrErr.takeError()) + return E; + const auto &Record = *RecordOrErr; + if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader)) + return E; + } + } + return Error::success(); +} + +Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( + ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, + IndexedInstrProfReader &ProfileReader) { + auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); + if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage)) + return std::move(E); + return std::move(Coverage); +} + +// If E is a no_data_found error, returns success. Otherwise returns E. +static Error handleMaybeNoDataFoundError(Error E) { + return handleErrors( + std::move(E), [](const CoverageMapError &CME) { + if (CME.get() == coveragemap_error::no_data_found) + return static_cast<Error>(Error::success()); + return make_error<CoverageMapError>(CME.get(), CME.getMessage()); + }); +} + +Error CoverageMapping::loadFromFile( + StringRef Filename, StringRef Arch, StringRef CompilationDir, + IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage, + bool &DataFound, SmallVectorImpl<object::BuildID> *FoundBinaryIDs) { + auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN( + Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false); + if (std::error_code EC = CovMappingBufOrErr.getError()) + return createFileError(Filename, errorCodeToError(EC)); + MemoryBufferRef CovMappingBufRef = + CovMappingBufOrErr.get()->getMemBufferRef(); + SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; + + SmallVector<object::BuildIDRef> BinaryIDs; + auto CoverageReadersOrErr = BinaryCoverageReader::create( + CovMappingBufRef, Arch, Buffers, CompilationDir, + FoundBinaryIDs ? &BinaryIDs : nullptr); + if (Error E = CoverageReadersOrErr.takeError()) { + E = handleMaybeNoDataFoundError(std::move(E)); + if (E) + return createFileError(Filename, std::move(E)); + return E; + } + + SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; + for (auto &Reader : CoverageReadersOrErr.get()) + Readers.push_back(std::move(Reader)); + if (FoundBinaryIDs && !Readers.empty()) { + llvm::append_range(*FoundBinaryIDs, + llvm::map_range(BinaryIDs, [](object::BuildIDRef BID) { + return object::BuildID(BID); + })); + } + DataFound |= !Readers.empty(); + if (Error E = loadFromReaders(Readers, ProfileReader, Coverage)) + return createFileError(Filename, std::move(E)); + return Error::success(); +} + +Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( + ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename, + vfs::FileSystem &FS, ArrayRef<StringRef> Arches, StringRef CompilationDir, + const object::BuildIDFetcher *BIDFetcher, bool CheckBinaryIDs) { + auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename, FS); + if (Error E = ProfileReaderOrErr.takeError()) + return createFileError(ProfileFilename, std::move(E)); + auto ProfileReader = std::move(ProfileReaderOrErr.get()); + auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); + bool DataFound = false; + + auto GetArch = [&](size_t Idx) { + if (Arches.empty()) + return StringRef(); + if (Arches.size() == 1) + return Arches.front(); + return Arches[Idx]; + }; + + SmallVector<object::BuildID> FoundBinaryIDs; + for (const auto &File : llvm::enumerate(ObjectFilenames)) { + if (Error E = + loadFromFile(File.value(), GetArch(File.index()), CompilationDir, + *ProfileReader, *Coverage, DataFound, &FoundBinaryIDs)) + return std::move(E); + } + + if (BIDFetcher) { + std::vector<object::BuildID> ProfileBinaryIDs; + if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs)) + return createFileError(ProfileFilename, std::move(E)); + + SmallVector<object::BuildIDRef> BinaryIDsToFetch; + if (!ProfileBinaryIDs.empty()) { + const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) { + return std::lexicographical_compare(A.begin(), A.end(), B.begin(), + B.end()); + }; + llvm::sort(FoundBinaryIDs, Compare); + std::set_difference( + ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(), + FoundBinaryIDs.begin(), FoundBinaryIDs.end(), + std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare); + } + + for (object::BuildIDRef BinaryID : BinaryIDsToFetch) { + std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID); + if (PathOpt) { + std::string Path = std::move(*PathOpt); + StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef(); + if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader, + *Coverage, DataFound)) + return std::move(E); + } else if (CheckBinaryIDs) { + return createFileError( + ProfileFilename, + createStringError(errc::no_such_file_or_directory, + "Missing binary ID: " + + llvm::toHex(BinaryID, /*LowerCase=*/true))); + } + } + } + + if (!DataFound) + return createFileError( + join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "), + make_error<CoverageMapError>(coveragemap_error::no_data_found)); + return std::move(Coverage); +} + +namespace { + +/// Distributes functions into instantiation sets. +/// +/// An instantiation set is a collection of functions that have the same source +/// code, ie, template functions specializations. +class FunctionInstantiationSetCollector { + using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; + MapT InstantiatedFunctions; + +public: + void insert(const FunctionRecord &Function, unsigned FileID) { + auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); + while (I != E && I->FileID != FileID) + ++I; + assert(I != E && "function does not cover the given file"); + auto &Functions = InstantiatedFunctions[I->startLoc()]; + Functions.push_back(&Function); + } + + MapT::iterator begin() { return InstantiatedFunctions.begin(); } + MapT::iterator end() { return InstantiatedFunctions.end(); } +}; + +class SegmentBuilder { + std::vector<CoverageSegment> &Segments; + SmallVector<const CountedRegion *, 8> ActiveRegions; + + SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} + + /// Emit a segment with the count from \p Region starting at \p StartLoc. + // + /// \p IsRegionEntry: The segment is at the start of a new non-gap region. + /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. + void startSegment(const CountedRegion &Region, LineColPair StartLoc, + bool IsRegionEntry, bool EmitSkippedRegion = false) { + bool HasCount = !EmitSkippedRegion && + (Region.Kind != CounterMappingRegion::SkippedRegion); + + // If the new segment wouldn't affect coverage rendering, skip it. + if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { + const auto &Last = Segments.back(); + if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && + !Last.IsRegionEntry) + return; + } + + if (HasCount) + Segments.emplace_back(StartLoc.first, StartLoc.second, + Region.ExecutionCount, IsRegionEntry, + Region.Kind == CounterMappingRegion::GapRegion); + else + Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); + + LLVM_DEBUG({ + const auto &Last = Segments.back(); + dbgs() << "Segment at " << Last.Line << ":" << Last.Col + << " (count = " << Last.Count << ")" + << (Last.IsRegionEntry ? ", RegionEntry" : "") + << (!Last.HasCount ? ", Skipped" : "") + << (Last.IsGapRegion ? ", Gap" : "") << "\n"; + }); + } + + /// Emit segments for active regions which end before \p Loc. + /// + /// \p Loc: The start location of the next region. If std::nullopt, all active + /// regions are completed. + /// \p FirstCompletedRegion: Index of the first completed region. + void completeRegionsUntil(std::optional<LineColPair> Loc, + unsigned FirstCompletedRegion) { + // Sort the completed regions by end location. This makes it simple to + // emit closing segments in sorted order. + auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; + std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), + [](const CountedRegion *L, const CountedRegion *R) { + return L->endLoc() < R->endLoc(); + }); + + // Emit segments for all completed regions. + for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; + ++I) { + const auto *CompletedRegion = ActiveRegions[I]; + assert((!Loc || CompletedRegion->endLoc() <= *Loc) && + "Completed region ends after start of new region"); + + const auto *PrevCompletedRegion = ActiveRegions[I - 1]; + auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); + + // Don't emit any more segments if they start where the new region begins. + if (Loc && CompletedSegmentLoc == *Loc) + break; + + // Don't emit a segment if the next completed region ends at the same + // location as this one. + if (CompletedSegmentLoc == CompletedRegion->endLoc()) + continue; + + // Use the count from the last completed region which ends at this loc. + for (unsigned J = I + 1; J < E; ++J) + if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) + CompletedRegion = ActiveRegions[J]; + + startSegment(*CompletedRegion, CompletedSegmentLoc, false); + } + + auto Last = ActiveRegions.back(); + if (FirstCompletedRegion && Last->endLoc() != *Loc) { + // If there's a gap after the end of the last completed region and the + // start of the new region, use the last active region to fill the gap. + startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), + false); + } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { + // Emit a skipped segment if there are no more active regions. This + // ensures that gaps between functions are marked correctly. + startSegment(*Last, Last->endLoc(), false, true); + } + + // Pop the completed regions. + ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); + } + + void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { + for (const auto &CR : enumerate(Regions)) { + auto CurStartLoc = CR.value().startLoc(); + + // Active regions which end before the current region need to be popped. + auto CompletedRegions = + std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), + [&](const CountedRegion *Region) { + return !(Region->endLoc() <= CurStartLoc); + }); + if (CompletedRegions != ActiveRegions.end()) { + unsigned FirstCompletedRegion = + std::distance(ActiveRegions.begin(), CompletedRegions); + completeRegionsUntil(CurStartLoc, FirstCompletedRegion); + } + + bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; + + // Try to emit a segment for the current region. + if (CurStartLoc == CR.value().endLoc()) { + // Avoid making zero-length regions active. If it's the last region, + // emit a skipped segment. Otherwise use its predecessor's count. + const bool Skipped = + (CR.index() + 1) == Regions.size() || + CR.value().Kind == CounterMappingRegion::SkippedRegion; + startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), + CurStartLoc, !GapRegion, Skipped); + // If it is skipped segment, create a segment with last pushed + // regions's count at CurStartLoc. + if (Skipped && !ActiveRegions.empty()) + startSegment(*ActiveRegions.back(), CurStartLoc, false); + continue; + } + if (CR.index() + 1 == Regions.size() || + CurStartLoc != Regions[CR.index() + 1].startLoc()) { + // Emit a segment if the next region doesn't start at the same location + // as this one. + startSegment(CR.value(), CurStartLoc, !GapRegion); + } + + // This region is active (i.e not completed). + ActiveRegions.push_back(&CR.value()); + } + + // Complete any remaining active regions. + if (!ActiveRegions.empty()) + completeRegionsUntil(std::nullopt, 0); + } + + /// Sort a nested sequence of regions from a single file. + static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { + llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { + if (LHS.startLoc() != RHS.startLoc()) + return LHS.startLoc() < RHS.startLoc(); + if (LHS.endLoc() != RHS.endLoc()) + // When LHS completely contains RHS, we sort LHS first. + return RHS.endLoc() < LHS.endLoc(); + // If LHS and RHS cover the same area, we need to sort them according + // to their kinds so that the most suitable region will become "active" + // in combineRegions(). Because we accumulate counter values only from + // regions of the same kind as the first region of the area, prefer + // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. + static_assert(CounterMappingRegion::CodeRegion < + CounterMappingRegion::ExpansionRegion && + CounterMappingRegion::ExpansionRegion < + CounterMappingRegion::SkippedRegion, + "Unexpected order of region kind values"); + return LHS.Kind < RHS.Kind; + }); + } + + /// Combine counts of regions which cover the same area. + static ArrayRef<CountedRegion> + combineRegions(MutableArrayRef<CountedRegion> Regions) { + if (Regions.empty()) + return Regions; + auto Active = Regions.begin(); + auto End = Regions.end(); + for (auto I = Regions.begin() + 1; I != End; ++I) { + if (Active->startLoc() != I->startLoc() || + Active->endLoc() != I->endLoc()) { + // Shift to the next region. + ++Active; + if (Active != I) + *Active = *I; + continue; + } + // Merge duplicate region. + // If CodeRegions and ExpansionRegions cover the same area, it's probably + // a macro which is fully expanded to another macro. In that case, we need + // to accumulate counts only from CodeRegions, or else the area will be + // counted twice. + // On the other hand, a macro may have a nested macro in its body. If the + // outer macro is used several times, the ExpansionRegion for the nested + // macro will also be added several times. These ExpansionRegions cover + // the same source locations and have to be combined to reach the correct + // value for that area. + // We add counts of the regions of the same kind as the active region + // to handle the both situations. + if (I->Kind == Active->Kind) { + assert(I->HasSingleByteCoverage == Active->HasSingleByteCoverage && + "Regions are generated in different coverage modes"); + if (I->HasSingleByteCoverage) + Active->ExecutionCount = Active->ExecutionCount || I->ExecutionCount; + else + Active->ExecutionCount += I->ExecutionCount; + } + } + return Regions.drop_back(std::distance(++Active, End)); + } + +public: + /// Build a sorted list of CoverageSegments from a list of Regions. + static std::vector<CoverageSegment> + buildSegments(MutableArrayRef<CountedRegion> Regions) { + std::vector<CoverageSegment> Segments; + SegmentBuilder Builder(Segments); + + sortNestedRegions(Regions); + ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); + + LLVM_DEBUG({ + dbgs() << "Combined regions:\n"; + for (const auto &CR : CombinedRegions) + dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " + << CR.LineEnd << ":" << CR.ColumnEnd + << " (count=" << CR.ExecutionCount << ")\n"; + }); + + Builder.buildSegmentsImpl(CombinedRegions); + +#ifndef NDEBUG + for (unsigned I = 1, E = Segments.size(); I < E; ++I) { + const auto &L = Segments[I - 1]; + const auto &R = Segments[I]; + if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { + if (L.Line == R.Line && L.Col == R.Col && !L.HasCount) + continue; + LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col + << " followed by " << R.Line << ":" << R.Col << "\n"); + assert(false && "Coverage segments not unique or sorted"); + } + } +#endif + + return Segments; + } +}; + +} // end anonymous namespace + +std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { + std::vector<StringRef> Filenames; + for (const auto &Function : getCoveredFunctions()) + llvm::append_range(Filenames, Function.Filenames); + llvm::sort(Filenames); + auto Last = llvm::unique(Filenames); + Filenames.erase(Last, Filenames.end()); + return Filenames; +} + +static SmallBitVector gatherFileIDs(StringRef SourceFile, + const FunctionRecord &Function) { + SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); + for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) + if (SourceFile == Function.Filenames[I]) + FilenameEquivalence[I] = true; + return FilenameEquivalence; +} + +/// Return the ID of the file where the definition of the function is located. +static std::optional<unsigned> +findMainViewFileID(const FunctionRecord &Function) { + SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); + for (const auto &CR : Function.CountedRegions) + if (CR.Kind == CounterMappingRegion::ExpansionRegion) + IsNotExpandedFile[CR.ExpandedFileID] = false; + int I = IsNotExpandedFile.find_first(); + if (I == -1) + return std::nullopt; + return I; +} + +/// Check if SourceFile is the file that contains the definition of +/// the Function. Return the ID of the file in that case or std::nullopt +/// otherwise. +static std::optional<unsigned> +findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) { + std::optional<unsigned> I = findMainViewFileID(Function); + if (I && SourceFile == Function.Filenames[*I]) + return I; + return std::nullopt; +} + +static bool isExpansion(const CountedRegion &R, unsigned FileID) { + return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; +} + +CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { + CoverageData FileCoverage(Filename); + std::vector<CountedRegion> Regions; + + // Look up the function records in the given file. Due to hash collisions on + // the filename, we may get back some records that are not in the file. + ArrayRef<unsigned> RecordIndices = + getImpreciseRecordIndicesForFilename(Filename); + for (unsigned RecordIndex : RecordIndices) { + const FunctionRecord &Function = Functions[RecordIndex]; + auto MainFileID = findMainViewFileID(Filename, Function); + auto FileIDs = gatherFileIDs(Filename, Function); + for (const auto &CR : Function.CountedRegions) + if (FileIDs.test(CR.FileID)) { + Regions.push_back(CR); + if (MainFileID && isExpansion(CR, *MainFileID)) + FileCoverage.Expansions.emplace_back(CR, Function); + } + // Capture branch regions specific to the function (excluding expansions). + for (const auto &CR : Function.CountedBranchRegions) + if (FileIDs.test(CR.FileID) && (CR.FileID == CR.ExpandedFileID)) + FileCoverage.BranchRegions.push_back(CR); + // Capture MCDC records specific to the function. + for (const auto &MR : Function.MCDCRecords) + if (FileIDs.test(MR.getDecisionRegion().FileID)) + FileCoverage.MCDCRecords.push_back(MR); + } + + LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); + FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); + + return FileCoverage; +} + +std::vector<InstantiationGroup> +CoverageMapping::getInstantiationGroups(StringRef Filename) const { + FunctionInstantiationSetCollector InstantiationSetCollector; + // Look up the function records in the given file. Due to hash collisions on + // the filename, we may get back some records that are not in the file. + ArrayRef<unsigned> RecordIndices = + getImpreciseRecordIndicesForFilename(Filename); + for (unsigned RecordIndex : RecordIndices) { + const FunctionRecord &Function = Functions[RecordIndex]; + auto MainFileID = findMainViewFileID(Filename, Function); + if (!MainFileID) + continue; + InstantiationSetCollector.insert(Function, *MainFileID); + } + + std::vector<InstantiationGroup> Result; + for (auto &InstantiationSet : InstantiationSetCollector) { + InstantiationGroup IG{InstantiationSet.first.first, + InstantiationSet.first.second, + std::move(InstantiationSet.second)}; + Result.emplace_back(std::move(IG)); + } + return Result; +} + +CoverageData +CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { + auto MainFileID = findMainViewFileID(Function); + if (!MainFileID) + return CoverageData(); + + CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); + std::vector<CountedRegion> Regions; + for (const auto &CR : Function.CountedRegions) + if (CR.FileID == *MainFileID) { + Regions.push_back(CR); + if (isExpansion(CR, *MainFileID)) + FunctionCoverage.Expansions.emplace_back(CR, Function); + } + // Capture branch regions specific to the function (excluding expansions). + for (const auto &CR : Function.CountedBranchRegions) + if (CR.FileID == *MainFileID) + FunctionCoverage.BranchRegions.push_back(CR); + + // Capture MCDC records specific to the function. + for (const auto &MR : Function.MCDCRecords) + if (MR.getDecisionRegion().FileID == *MainFileID) + FunctionCoverage.MCDCRecords.push_back(MR); + + LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name + << "\n"); + FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); + + return FunctionCoverage; +} + +CoverageData CoverageMapping::getCoverageForExpansion( + const ExpansionRecord &Expansion) const { + CoverageData ExpansionCoverage( + Expansion.Function.Filenames[Expansion.FileID]); + std::vector<CountedRegion> Regions; + for (const auto &CR : Expansion.Function.CountedRegions) + if (CR.FileID == Expansion.FileID) { + Regions.push_back(CR); + if (isExpansion(CR, Expansion.FileID)) + ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); + } + for (const auto &CR : Expansion.Function.CountedBranchRegions) + // Capture branch regions that only pertain to the corresponding expansion. + if (CR.FileID == Expansion.FileID) + ExpansionCoverage.BranchRegions.push_back(CR); + + LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " + << Expansion.FileID << "\n"); + ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); + + return ExpansionCoverage; +} + +LineCoverageStats::LineCoverageStats( + ArrayRef<const CoverageSegment *> LineSegments, + const CoverageSegment *WrappedSegment, unsigned Line) + : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), + LineSegments(LineSegments), WrappedSegment(WrappedSegment) { + // Find the minimum number of regions which start in this line. + unsigned MinRegionCount = 0; + auto isStartOfRegion = [](const CoverageSegment *S) { + return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; + }; + for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) + if (isStartOfRegion(LineSegments[I])) + ++MinRegionCount; + + bool StartOfSkippedRegion = !LineSegments.empty() && + !LineSegments.front()->HasCount && + LineSegments.front()->IsRegionEntry; + + HasMultipleRegions = MinRegionCount > 1; + Mapped = + !StartOfSkippedRegion && + ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); + + // if there is any starting segment at this line with a counter, it must be + // mapped + Mapped |= std::any_of( + LineSegments.begin(), LineSegments.end(), + [](const auto *Seq) { return Seq->IsRegionEntry && Seq->HasCount; }); + + if (!Mapped) { + return; + } + + // Pick the max count from the non-gap, region entry segments and the + // wrapped count. + if (WrappedSegment) + ExecutionCount = WrappedSegment->Count; + if (!MinRegionCount) + return; + for (const auto *LS : LineSegments) + if (isStartOfRegion(LS)) + ExecutionCount = std::max(ExecutionCount, LS->Count); +} + +LineCoverageIterator &LineCoverageIterator::operator++() { + if (Next == CD.end()) { + Stats = LineCoverageStats(); + Ended = true; + return *this; + } + if (Segments.size()) + WrappedSegment = Segments.back(); + Segments.clear(); + while (Next != CD.end() && Next->Line == Line) + Segments.push_back(&*Next++); + Stats = LineCoverageStats(Segments, WrappedSegment, Line); + ++Line; + return *this; +} + +static std::string getCoverageMapErrString(coveragemap_error Err, + const std::string &ErrMsg = "") { + std::string Msg; + raw_string_ostream OS(Msg); + + switch (Err) { + case coveragemap_error::success: + OS << "success"; + break; + case coveragemap_error::eof: + OS << "end of File"; + break; + case coveragemap_error::no_data_found: + OS << "no coverage data found"; + break; + case coveragemap_error::unsupported_version: + OS << "unsupported coverage format version"; + break; + case coveragemap_error::truncated: + OS << "truncated coverage data"; + break; + case coveragemap_error::malformed: + OS << "malformed coverage data"; + break; + case coveragemap_error::decompression_failed: + OS << "failed to decompress coverage data (zlib)"; + break; + case coveragemap_error::invalid_or_missing_arch_specifier: + OS << "`-arch` specifier is invalid or missing for universal binary"; + break; + } + + // If optional error message is not empty, append it to the message. + if (!ErrMsg.empty()) + OS << ": " << ErrMsg; + + return Msg; +} + +namespace { + +// FIXME: This class is only here to support the transition to llvm::Error. It +// will be removed once this transition is complete. Clients should prefer to +// deal with the Error value directly, rather than converting to error_code. +class CoverageMappingErrorCategoryType : public std::error_category { + const char *name() const noexcept override { return "llvm.coveragemap"; } + std::string message(int IE) const override { + return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); + } +}; + +} // end anonymous namespace + +std::string CoverageMapError::message() const { + return getCoverageMapErrString(Err, Msg); +} + +const std::error_category &llvm::coverage::coveragemap_category() { + static CoverageMappingErrorCategoryType ErrorCategory; + return ErrorCategory; +} + +char CoverageMapError::ID = 0; |