From aa2fdc69d35ff1c4a6de8a8d8edcc4c15236bb15 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Fri, 27 Dec 2024 20:42:26 +0900 Subject: [Coverage] Move SingleByteCoverage out of CountedRegion (#110966) `SingleByteCoverage` is not per-region attribute at least. Move it into `CoverageData` since it comes from `profdata`. Depends on: #120841 --- llvm/lib/ProfileData/Coverage/CoverageMapping.cpp | 29 ++++++++++------------- 1 file changed, 13 insertions(+), 16 deletions(-) (limited to 'llvm/lib/ProfileData/Coverage/CoverageMapping.cpp') diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index 87d8bb1..1bf2e8d 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -805,7 +805,6 @@ Error CoverageMapping::loadFunctionRecord( else OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); - bool SingleByteCoverage = ProfileReader.hasSingleByteCoverage(); CounterMappingContext Ctx(Record.Expressions); std::vector Counts; @@ -871,10 +870,7 @@ Error CoverageMapping::loadFunctionRecord( consumeError(std::move(E)); return Error::success(); } - Function.pushRegion( - Region, (SingleByteCoverage && *ExecutionCount ? 1 : *ExecutionCount), - (SingleByteCoverage && *AltExecutionCount ? 1 : *AltExecutionCount), - SingleByteCoverage); + Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount); // Record ExpansionRegion. if (Region.Kind == CounterMappingRegion::ExpansionRegion) { @@ -936,6 +932,9 @@ Error CoverageMapping::loadFunctionRecord( Error CoverageMapping::loadFromReaders( ArrayRef> CoverageReaders, IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) { + assert(!Coverage.SingleByteCoverage || + *Coverage.SingleByteCoverage == ProfileReader.hasSingleByteCoverage()); + Coverage.SingleByteCoverage = ProfileReader.hasSingleByteCoverage(); for (const auto &CoverageReader : CoverageReaders) { for (auto RecordOrErr : *CoverageReader) { if (Error E = RecordOrErr.takeError()) @@ -1296,14 +1295,8 @@ class SegmentBuilder { // 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; - } + if (I->Kind == Active->Kind) + Active->ExecutionCount += I->ExecutionCount; } return Regions.drop_back(std::distance(++Active, End)); } @@ -1396,7 +1389,8 @@ static bool isExpansion(const CountedRegion &R, unsigned FileID) { } CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { - CoverageData FileCoverage(Filename); + assert(SingleByteCoverage); + CoverageData FileCoverage(*SingleByteCoverage, Filename); std::vector Regions; // Look up the function records in the given file. Due to hash collisions on @@ -1460,7 +1454,9 @@ CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { if (!MainFileID) return CoverageData(); - CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); + assert(SingleByteCoverage); + CoverageData FunctionCoverage(*SingleByteCoverage, + Function.Filenames[*MainFileID]); std::vector Regions; for (const auto &CR : Function.CountedRegions) if (CR.FileID == *MainFileID) { @@ -1487,8 +1483,9 @@ CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { CoverageData CoverageMapping::getCoverageForExpansion( const ExpansionRecord &Expansion) const { + assert(SingleByteCoverage); CoverageData ExpansionCoverage( - Expansion.Function.Filenames[Expansion.FileID]); + *SingleByteCoverage, Expansion.Function.Filenames[Expansion.FileID]); std::vector Regions; for (const auto &CR : Expansion.Function.CountedRegions) if (CR.FileID == Expansion.FileID) { -- cgit v1.1 From ee6f10d37232627137ce97388a5eb21b90907bfb Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Sat, 28 Dec 2024 17:48:30 +0900 Subject: [Coverage] Make `MCDCRecord::Folded` as `[false/true]` with BitVector. NFC. (#121190) For merging `MCDCRecord`s, `Folded` is expected to be promoted as "Non-folded". --- llvm/lib/ProfileData/Coverage/CoverageMapping.cpp | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'llvm/lib/ProfileData/Coverage/CoverageMapping.cpp') diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index 1bf2e8d..f95e311 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -392,8 +392,9 @@ public: : 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) {} + Folded{{BitVector(NumConditions), BitVector(NumConditions)}}, + IndependencePairs(NumConditions), ExecVectors(ExecVectorsByCond[false]), + IsVersion11(IsVersion11) {} private: // Walk the binary decision diagram and try assigning both false and true to @@ -485,7 +486,6 @@ public: /// 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; @@ -499,11 +499,12 @@ public: // 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) { + for (auto [I, B] : enumerate(Branches)) { const auto &BranchParams = B->getBranchParams(); PosToID[I] = BranchParams.ID; CondLoc[I] = B->startLoc(); - Folded[I++] = (B->Count.isZero() || B->FalseCount.isZero()); + Folded[false][I] = B->FalseCount.isZero(); + Folded[true][I] = B->Count.isZero(); } // Using Profile Bitmap from runtime, mark the executed test vectors. -- cgit v1.1 From 97097958fdf525e8c14fcdde94231bae72ea2673 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Tue, 7 Jan 2025 08:52:04 +0900 Subject: [Coverage] MCDC: Move findIndependencePairs deferred into MCDCRecord (#121188) The result of "Independence pairs" is not mergeable. This change makes defers re-calculation of "Independence pairs" after merging test vectors. No apparent behavior changes. --- llvm/lib/ProfileData/Coverage/CoverageMapping.cpp | 67 ++++++++++++----------- 1 file changed, 35 insertions(+), 32 deletions(-) (limited to 'llvm/lib/ProfileData/Coverage/CoverageMapping.cpp') diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index f95e311..e8f60d2 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -221,6 +221,40 @@ Expected CounterMappingContext::evaluate(const Counter &C) const { return LastPoppedValue; } +// 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 MCDCRecord::findIndependencePairs() { + if (IndependencePairs) + return; + + IndependencePairs.emplace(); + + unsigned NumTVs = TV.size(); + // Will be replaced to shorter expr. + unsigned TVTrueIdx = std::distance( + TV.begin(), + std::find_if(TV.begin(), TV.end(), + [&](auto I) { return (I.second == MCDCRecord::MCDC_True); }) + + ); + for (unsigned I = TVTrueIdx; I < NumTVs; ++I) { + const auto &[A, ACond] = TV[I]; + assert(ACond == MCDCRecord::MCDC_True); + for (unsigned J = 0; J < TVTrueIdx; ++J) { + const auto &[B, BCond] = TV[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)}); + } + } +} + mcdc::TVIdxBuilder::TVIdxBuilder(const SmallVectorImpl &NextIDs, int Offset) : Indices(NextIDs.size()) { @@ -375,9 +409,6 @@ class MCDCRecordProcessor : NextIDsBuilder, mcdc::TVIdxBuilder { /// ExecutedTestVectorBitmap. MCDCRecord::TestVectors &ExecVectors; - /// Number of False items in ExecVectors - unsigned NumExecVectorsF; - #ifndef NDEBUG DenseSet TVIdxs; #endif @@ -447,34 +478,11 @@ private: // 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 @@ -510,13 +518,8 @@ public: // 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), + return MCDCRecord(Region, std::move(ExecVectors), std::move(Folded), std::move(PosToID), std::move(CondLoc)); } }; -- cgit v1.1 From 61b294aa15e9e2149398a641121fc3e977284a17 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Thu, 9 Jan 2025 16:27:35 +0900 Subject: Introduce CounterExpressionBuilder::subst(C, Map) (#112698) This return a counter for each term in the expression replaced by ReplaceMap. At the moment, this doesn't update the Map, so Map is marked as `const`. --- llvm/lib/ProfileData/Coverage/CoverageMapping.cpp | 25 +++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'llvm/lib/ProfileData/Coverage/CoverageMapping.cpp') diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index e8f60d2..6d6678e 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -135,6 +135,31 @@ Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS, return Simplify ? simplify(Cnt) : Cnt; } +Counter CounterExpressionBuilder::subst(Counter C, const SubstMap &Map) { + // Replace C with the value found in Map even if C is Expression. + if (auto I = Map.find(C); I != Map.end()) + return I->second; + + if (!C.isExpression()) + return C; + + auto CE = Expressions[C.getExpressionID()]; + auto NewLHS = subst(CE.LHS, Map); + auto NewRHS = subst(CE.RHS, Map); + + // Reconstruct Expression with induced subexpressions. + switch (CE.Kind) { + case CounterExpression::Add: + C = add(NewLHS, NewRHS); + break; + case CounterExpression::Subtract: + C = subtract(NewLHS, NewRHS); + break; + } + + return C; +} + void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { switch (C.getKind()) { case Counter::Zero: -- cgit v1.1