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