https://github.com/chapuni updated https://github.com/llvm/llvm-project/pull/80676
>From d168e0cb85eb150caa7ab241f136c5a23f79ba38 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi <geek4ci...@gmail.com> Date: Mon, 5 Feb 2024 00:33:40 +0900 Subject: [PATCH 1/5] Implement MCDCTVIdxBuilder and MCDCTestVectorBuilder (LLVM side) This accept current version of profdata. The output might be different. See also https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798 --- .../ProfileData/Coverage/CoverageMapping.h | 24 ++ .../ProfileData/Coverage/CoverageMapping.cpp | 226 +++++++++++++----- llvm/test/tools/llvm-cov/mcdc-const.test | 28 +-- llvm/test/tools/llvm-cov/mcdc-general.test | 16 +- 4 files changed, 214 insertions(+), 80 deletions(-) diff --git a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h index 88ec60c7aa33c..62867275a8524 100644 --- a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h +++ b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h @@ -32,6 +32,7 @@ #include "llvm/Support/raw_ostream.h" #include <cassert> #include <cstdint> +#include <functional> #include <iterator> #include <memory> #include <sstream> @@ -557,6 +558,29 @@ struct MCDCRecord { } }; +class MCDCTVIdxBuilder { +public: + struct MCDCNode { + int InCount = 0; + unsigned Width; + struct { + int ID; + int Idx; + } Conds[2]; + }; + + SmallVector<MCDCNode> Nodes; + unsigned NumTestVectors; + +public: + using NodeIDs = std::tuple<unsigned, // ID1 (ends with 0) + unsigned, // ID1 for False + unsigned // ID1 for True + >; + + MCDCTVIdxBuilder(std::function<NodeIDs(bool TellSize)> Fetcher); +}; + /// A Counter mapping context is used to connect the counters, expressions /// and the obtained counter values. class CounterMappingContext { diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index 39e43f86eab5e..d3a60c664b9e9 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -223,6 +223,171 @@ Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { return LastPoppedValue; } +MCDCTVIdxBuilder::MCDCTVIdxBuilder( + std::function<NodeIDs(bool TellSize)> Fetcher) { + // Build Nodes and set up each InCount + int MaxID = -1; + Nodes.resize(std::get<0>(Fetcher(true))); + while (true) { + auto [ID1, FalseID1, TrueID1] = Fetcher(false); + if (ID1 == 0) + break; + if (Nodes.size() < ID1) + Nodes.resize(ID1); + int ID = ID1 - 1; + MaxID = std::max(MaxID, ID); + auto &Node = Nodes[ID]; + Node.Conds[0].ID = FalseID1 - 1; + Node.Conds[1].ID = TrueID1 - 1; + for (unsigned I = 0; I < 2; ++I) { + int NextID = Node.Conds[I].ID; + if (NextID >= 0) + ++Nodes[NextID].InCount; + } + } + + if (MaxID < 0) + return; + + // 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()) { + int ID = *Q.begin(); + Q.erase(Q.begin()); + auto &Node = Nodes[ID]; + assert(Node.Width > 0); + + for (unsigned I = 0; I < 2; ++I) { + int NextID = Node.Conds[I].ID; + assert(NextID != 0); + if (NextID < 0) { + Decisions.emplace_back(-Node.Width, Ord++, ID, I); + assert(Ord == Decisions.size()); + continue; + } + + auto &NextNode = Nodes[NextID]; + assert(NextNode.InCount > 0); + Node.Conds[I].Idx = NextNode.Width; // ??? + NextNode.Width += Node.Width; + if (--NextNode.InCount == 0) + Q.push_back(NextID); + } + } + + std::sort(Decisions.begin(), Decisions.end()); + + // Assign TestVector Index + unsigned CurIdx = 0; + for (auto [NegWidth, Ord, ID, C] : Decisions) { + unsigned Width = -NegWidth; + auto &Node = Nodes[ID]; + assert(Node.Width == Width); + assert(Node.Conds[C].Idx == 0); + assert(Node.Conds[C].ID < 0); + Node.Conds[C].Idx = CurIdx; + CurIdx += Width; + } + NumTestVectors = CurIdx; +} + +namespace { + +class MCDCTestVectorBuilder : public MCDCTVIdxBuilder { + MCDCRecord::TestVectors TestVectors; + const BitVector &Bitmap; + unsigned BitmapIdx; +#ifndef NDEBUG + DenseSet<unsigned> TVIDs; +#endif + + class BranchProvider { + ArrayRef<const CounterMappingRegion *> Branches; + unsigned BranchIdx = 0; + + public: + BranchProvider(ArrayRef<const CounterMappingRegion *> Branches) + : Branches(Branches) {} + + std::function<NodeIDs(bool)> getFetcher() { + return [this](bool TellSize) { + if (TellSize) + return NodeIDs(Branches.size(), 0, 0); + if (BranchIdx >= Branches.size()) + return NodeIDs(0, 0, 0); + const auto *B = Branches[BranchIdx++]; + return NodeIDs(B->MCDCParams.ID, B->MCDCParams.FalseID, + B->MCDCParams.TrueID); + }; + } + }; + +public: + MCDCTestVectorBuilder(ArrayRef<const CounterMappingRegion *> Branches, + const BitVector &Bitmap, unsigned BitmapIdx) + : MCDCTVIdxBuilder(BranchProvider(Branches).getFetcher()), Bitmap(Bitmap), + BitmapIdx(BitmapIdx) {} + +protected: + MCDCRecord::TestVector TempTV; + + void buildTestVector(int ID = 0, unsigned TVIdx = 0, unsigned Index = 0) { + const auto &Node = Nodes[ID]; + + for (unsigned I = 0; I < 2; ++I) { + auto MCDCCond = (I ? MCDCRecord::MCDC_True : MCDCRecord::MCDC_False); + const auto &Cond = Node.Conds[I]; + auto NextID = Cond.ID; + Index |= I << ID; + TempTV[ID] = MCDCCond; + if (NextID >= 0) { + buildTestVector(NextID, TVIdx + Cond.Idx, Index); + continue; + } + + auto FinalTVIdx = Cond.Idx + TVIdx; + assert(TVIdx < Node.Width); +#ifndef NDEBUG + assert(!TVIDs.contains(FinalTVIdx)); + TVIDs.insert(FinalTVIdx); +#endif + + assert(BitmapIdx + Index < Bitmap.size() && "Bitmap overrun"); + if (!Bitmap[BitmapIdx + Index]) + continue; + + TestVectors.push_back(TempTV); + TestVectors.back().push_back(MCDCCond); + } + + // Reset back to DontCare. + TempTV[ID] = MCDCRecord::MCDC_DontCare; + } + +public: + MCDCRecord::TestVectors findExecutedTestVectors() { + TempTV.resize(Nodes.size(), MCDCRecord::MCDC_DontCare); + buildTestVector(); + assert(TVIDs.size() == NumTestVectors); + return std::move(TestVectors); + } +}; + +} // namespace + class MCDCRecordProcessor { /// A bitmap representing the executed test vectors for a boolean expression. /// Each index of the bitmap corresponds to a possible test vector. An index @@ -251,9 +416,6 @@ class MCDCRecordProcessor { /// Mapping of calculated MC/DC Independence Pairs for each condition. MCDCRecord::TVPairMap IndependencePairs; - /// Total number of possible Test Vectors for the boolean expression. - MCDCRecord::TestVectors TestVectors; - /// Actual executed Test Vectors for the boolean expression, based on /// ExecutedTestVectorBitmap. MCDCRecord::TestVectors ExecVectors; @@ -265,56 +427,9 @@ class MCDCRecordProcessor { : Bitmap(Bitmap), Region(Region), Branches(Branches), NumConditions(Region.MCDCParams.NumConditions), BitmapIdx(Region.MCDCParams.BitmapIdx * CHAR_BIT), - Folded(NumConditions, false), IndependencePairs(NumConditions), - TestVectors((size_t)1 << NumConditions) {} + Folded(NumConditions, false), IndependencePairs(NumConditions) {} private: - void recordTestVector(MCDCRecord::TestVector &TV, unsigned Index, - MCDCRecord::CondState Result) { - // Copy the completed test vector to the vector of testvectors. - TestVectors[Index] = TV; - - // The final value (T,F) is equal to the last non-dontcare state on the - // path (in a short-circuiting system). - TestVectors[Index].push_back(Result); - } - - // 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, unsigned ID, - unsigned Index) { - const CounterMappingRegion *Branch = Map[ID]; - - TV[ID - 1] = MCDCRecord::MCDC_False; - if (Branch->MCDCParams.FalseID > 0) - buildTestVector(TV, Branch->MCDCParams.FalseID, Index); - else - recordTestVector(TV, Index, MCDCRecord::MCDC_False); - - Index |= 1 << (ID - 1); - TV[ID - 1] = MCDCRecord::MCDC_True; - if (Branch->MCDCParams.TrueID > 0) - buildTestVector(TV, Branch->MCDCParams.TrueID, Index); - else - recordTestVector(TV, Index, MCDCRecord::MCDC_True); - - // Reset back to DontCare. - TV[ID - 1] = 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() { - for (unsigned Idx = 0; Idx < (1u << NumConditions); ++Idx) { - assert(BitmapIdx + Idx < Bitmap.size() && "Bitmap overrun"); - if (Bitmap[BitmapIdx + Idx] == 0) - continue; - assert(!TestVectors[Idx].empty() && "Test Vector doesn't exist."); - ExecVectors.push_back(TestVectors[Idx]); - } - } - // 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. @@ -378,14 +493,9 @@ class MCDCRecordProcessor { Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero()); } - // Walk the binary decision diagram to enumerate all possible test vectors. - // We start at the root node (ID == 1) with all values being DontCare. - // `Index` encodes the bitmask of true values and is initially 0. - MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare); - buildTestVector(TV, 1, 0); - // Using Profile Bitmap from runtime, mark the executed test vectors. - findExecutedTestVectors(); + ExecVectors = MCDCTestVectorBuilder(Branches, Bitmap, BitmapIdx) + .findExecutedTestVectors(); // Compare executed test vectors against each other to find an independence // pairs for each condition. This processing takes the most time. diff --git a/llvm/test/tools/llvm-cov/mcdc-const.test b/llvm/test/tools/llvm-cov/mcdc-const.test index 0b2c9c98d5355..5424625cf6a6b 100644 --- a/llvm/test/tools/llvm-cov/mcdc-const.test +++ b/llvm/test/tools/llvm-cov/mcdc-const.test @@ -61,8 +61,8 @@ // CHECKFULLCASE: | C1-Pair: constant folded // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C = T } -// CHECKFULLCASE-NEXT: | 2 { F, C = T } +// CHECKFULLCASE: | 1 { F, C = T } +// CHECKFULLCASE-NEXT: | 2 { T, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% @@ -106,8 +106,8 @@ // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, - = T } +// CHECKFULLCASE: | 1 { F, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered @@ -118,8 +118,8 @@ // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, T = T } +// CHECKFULLCASE: | 1 { F, C, T = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered @@ -151,26 +151,26 @@ // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: covered: (2,3) // CHECKFULLCASE: | MC/DC Coverage for Decision: 100.00% -// CHECKFULLCASE: | 1 { T, -, C = T } -// CHECKFULLCASE-NEXT: | 2 { F, T, C = T } +// CHECKFULLCASE: | 1 { F, T, C = T } +// CHECKFULLCASE-NEXT: | 2 { T, -, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, - = T } +// CHECKFULLCASE: | 1 { F, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, -, C = T } -// CHECKFULLCASE-NEXT: | 2 { F, T, C = T } +// CHECKFULLCASE: | 1 { F, T, C = T } +// CHECKFULLCASE-NEXT: | 2 { T, -, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, T = T } +// CHECKFULLCASE: | 1 { F, C, T = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered diff --git a/llvm/test/tools/llvm-cov/mcdc-general.test b/llvm/test/tools/llvm-cov/mcdc-general.test index 753036bedaf17..4b59ce59d638e 100644 --- a/llvm/test/tools/llvm-cov/mcdc-general.test +++ b/llvm/test/tools/llvm-cov/mcdc-general.test @@ -19,16 +19,16 @@ // CHECK-NEXT: | // CHECK-NEXT: | C1, C2, C3, C4 Result // CHECK-NEXT: | 1 { F, -, F, - = F } -// CHECK-NEXT: | 2 { T, F, F, - = F } -// CHECK-NEXT: | 3 { F, -, T, F = F } +// CHECK-NEXT: | 2 { F, -, T, F = F } +// CHECK-NEXT: | 3 { T, F, F, - = F } // CHECK-NEXT: | 4 { T, F, T, F = F } -// CHECK-NEXT: | 5 { T, T, -, - = T } -// CHECK-NEXT: | 6 { T, F, T, T = T } +// CHECK-NEXT: | 5 { T, F, T, T = T } +// CHECK-NEXT: | 6 { T, T, -, - = T } // CHECK-NEXT: | -// CHECK-NEXT: | C1-Pair: covered: (1,5) -// CHECK-NEXT: | C2-Pair: covered: (2,5) -// CHECK-NEXT: | C3-Pair: covered: (2,6) -// CHECK-NEXT: | C4-Pair: covered: (4,6) +// CHECK-NEXT: | C1-Pair: covered: (1,6) +// CHECK-NEXT: | C2-Pair: covered: (3,6) +// CHECK-NEXT: | C3-Pair: covered: (3,5) +// CHECK-NEXT: | C4-Pair: covered: (4,5) // CHECK-NEXT: | MC/DC Coverage for Decision: 100.00% // CHECK-NEXT: | // CHECK-NEXT: ------------------ >From 35b19ea47f34bb14b30fca25572fcd55a3b6b3b5 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi <geek4ci...@gmail.com> Date: Tue, 6 Feb 2024 17:21:04 +0900 Subject: [PATCH 2/5] Revert "Implement MCDCTVIdxBuilder and MCDCTestVectorBuilder (LLVM side)" This reverts commit d168e0cb85eb150caa7ab241f136c5a23f79ba38. --- .../ProfileData/Coverage/CoverageMapping.h | 24 -- .../ProfileData/Coverage/CoverageMapping.cpp | 226 +++++------------- llvm/test/tools/llvm-cov/mcdc-const.test | 28 +-- llvm/test/tools/llvm-cov/mcdc-general.test | 16 +- 4 files changed, 80 insertions(+), 214 deletions(-) diff --git a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h index 62867275a8524..88ec60c7aa33c 100644 --- a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h +++ b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h @@ -32,7 +32,6 @@ #include "llvm/Support/raw_ostream.h" #include <cassert> #include <cstdint> -#include <functional> #include <iterator> #include <memory> #include <sstream> @@ -558,29 +557,6 @@ struct MCDCRecord { } }; -class MCDCTVIdxBuilder { -public: - struct MCDCNode { - int InCount = 0; - unsigned Width; - struct { - int ID; - int Idx; - } Conds[2]; - }; - - SmallVector<MCDCNode> Nodes; - unsigned NumTestVectors; - -public: - using NodeIDs = std::tuple<unsigned, // ID1 (ends with 0) - unsigned, // ID1 for False - unsigned // ID1 for True - >; - - MCDCTVIdxBuilder(std::function<NodeIDs(bool TellSize)> Fetcher); -}; - /// A Counter mapping context is used to connect the counters, expressions /// and the obtained counter values. class CounterMappingContext { diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index d3a60c664b9e9..39e43f86eab5e 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -223,171 +223,6 @@ Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { return LastPoppedValue; } -MCDCTVIdxBuilder::MCDCTVIdxBuilder( - std::function<NodeIDs(bool TellSize)> Fetcher) { - // Build Nodes and set up each InCount - int MaxID = -1; - Nodes.resize(std::get<0>(Fetcher(true))); - while (true) { - auto [ID1, FalseID1, TrueID1] = Fetcher(false); - if (ID1 == 0) - break; - if (Nodes.size() < ID1) - Nodes.resize(ID1); - int ID = ID1 - 1; - MaxID = std::max(MaxID, ID); - auto &Node = Nodes[ID]; - Node.Conds[0].ID = FalseID1 - 1; - Node.Conds[1].ID = TrueID1 - 1; - for (unsigned I = 0; I < 2; ++I) { - int NextID = Node.Conds[I].ID; - if (NextID >= 0) - ++Nodes[NextID].InCount; - } - } - - if (MaxID < 0) - return; - - // 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()) { - int ID = *Q.begin(); - Q.erase(Q.begin()); - auto &Node = Nodes[ID]; - assert(Node.Width > 0); - - for (unsigned I = 0; I < 2; ++I) { - int NextID = Node.Conds[I].ID; - assert(NextID != 0); - if (NextID < 0) { - Decisions.emplace_back(-Node.Width, Ord++, ID, I); - assert(Ord == Decisions.size()); - continue; - } - - auto &NextNode = Nodes[NextID]; - assert(NextNode.InCount > 0); - Node.Conds[I].Idx = NextNode.Width; // ??? - NextNode.Width += Node.Width; - if (--NextNode.InCount == 0) - Q.push_back(NextID); - } - } - - std::sort(Decisions.begin(), Decisions.end()); - - // Assign TestVector Index - unsigned CurIdx = 0; - for (auto [NegWidth, Ord, ID, C] : Decisions) { - unsigned Width = -NegWidth; - auto &Node = Nodes[ID]; - assert(Node.Width == Width); - assert(Node.Conds[C].Idx == 0); - assert(Node.Conds[C].ID < 0); - Node.Conds[C].Idx = CurIdx; - CurIdx += Width; - } - NumTestVectors = CurIdx; -} - -namespace { - -class MCDCTestVectorBuilder : public MCDCTVIdxBuilder { - MCDCRecord::TestVectors TestVectors; - const BitVector &Bitmap; - unsigned BitmapIdx; -#ifndef NDEBUG - DenseSet<unsigned> TVIDs; -#endif - - class BranchProvider { - ArrayRef<const CounterMappingRegion *> Branches; - unsigned BranchIdx = 0; - - public: - BranchProvider(ArrayRef<const CounterMappingRegion *> Branches) - : Branches(Branches) {} - - std::function<NodeIDs(bool)> getFetcher() { - return [this](bool TellSize) { - if (TellSize) - return NodeIDs(Branches.size(), 0, 0); - if (BranchIdx >= Branches.size()) - return NodeIDs(0, 0, 0); - const auto *B = Branches[BranchIdx++]; - return NodeIDs(B->MCDCParams.ID, B->MCDCParams.FalseID, - B->MCDCParams.TrueID); - }; - } - }; - -public: - MCDCTestVectorBuilder(ArrayRef<const CounterMappingRegion *> Branches, - const BitVector &Bitmap, unsigned BitmapIdx) - : MCDCTVIdxBuilder(BranchProvider(Branches).getFetcher()), Bitmap(Bitmap), - BitmapIdx(BitmapIdx) {} - -protected: - MCDCRecord::TestVector TempTV; - - void buildTestVector(int ID = 0, unsigned TVIdx = 0, unsigned Index = 0) { - const auto &Node = Nodes[ID]; - - for (unsigned I = 0; I < 2; ++I) { - auto MCDCCond = (I ? MCDCRecord::MCDC_True : MCDCRecord::MCDC_False); - const auto &Cond = Node.Conds[I]; - auto NextID = Cond.ID; - Index |= I << ID; - TempTV[ID] = MCDCCond; - if (NextID >= 0) { - buildTestVector(NextID, TVIdx + Cond.Idx, Index); - continue; - } - - auto FinalTVIdx = Cond.Idx + TVIdx; - assert(TVIdx < Node.Width); -#ifndef NDEBUG - assert(!TVIDs.contains(FinalTVIdx)); - TVIDs.insert(FinalTVIdx); -#endif - - assert(BitmapIdx + Index < Bitmap.size() && "Bitmap overrun"); - if (!Bitmap[BitmapIdx + Index]) - continue; - - TestVectors.push_back(TempTV); - TestVectors.back().push_back(MCDCCond); - } - - // Reset back to DontCare. - TempTV[ID] = MCDCRecord::MCDC_DontCare; - } - -public: - MCDCRecord::TestVectors findExecutedTestVectors() { - TempTV.resize(Nodes.size(), MCDCRecord::MCDC_DontCare); - buildTestVector(); - assert(TVIDs.size() == NumTestVectors); - return std::move(TestVectors); - } -}; - -} // namespace - class MCDCRecordProcessor { /// A bitmap representing the executed test vectors for a boolean expression. /// Each index of the bitmap corresponds to a possible test vector. An index @@ -416,6 +251,9 @@ class MCDCRecordProcessor { /// Mapping of calculated MC/DC Independence Pairs for each condition. MCDCRecord::TVPairMap IndependencePairs; + /// Total number of possible Test Vectors for the boolean expression. + MCDCRecord::TestVectors TestVectors; + /// Actual executed Test Vectors for the boolean expression, based on /// ExecutedTestVectorBitmap. MCDCRecord::TestVectors ExecVectors; @@ -427,9 +265,56 @@ class MCDCRecordProcessor { : Bitmap(Bitmap), Region(Region), Branches(Branches), NumConditions(Region.MCDCParams.NumConditions), BitmapIdx(Region.MCDCParams.BitmapIdx * CHAR_BIT), - Folded(NumConditions, false), IndependencePairs(NumConditions) {} + Folded(NumConditions, false), IndependencePairs(NumConditions), + TestVectors((size_t)1 << NumConditions) {} private: + void recordTestVector(MCDCRecord::TestVector &TV, unsigned Index, + MCDCRecord::CondState Result) { + // Copy the completed test vector to the vector of testvectors. + TestVectors[Index] = TV; + + // The final value (T,F) is equal to the last non-dontcare state on the + // path (in a short-circuiting system). + TestVectors[Index].push_back(Result); + } + + // 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, unsigned ID, + unsigned Index) { + const CounterMappingRegion *Branch = Map[ID]; + + TV[ID - 1] = MCDCRecord::MCDC_False; + if (Branch->MCDCParams.FalseID > 0) + buildTestVector(TV, Branch->MCDCParams.FalseID, Index); + else + recordTestVector(TV, Index, MCDCRecord::MCDC_False); + + Index |= 1 << (ID - 1); + TV[ID - 1] = MCDCRecord::MCDC_True; + if (Branch->MCDCParams.TrueID > 0) + buildTestVector(TV, Branch->MCDCParams.TrueID, Index); + else + recordTestVector(TV, Index, MCDCRecord::MCDC_True); + + // Reset back to DontCare. + TV[ID - 1] = 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() { + for (unsigned Idx = 0; Idx < (1u << NumConditions); ++Idx) { + assert(BitmapIdx + Idx < Bitmap.size() && "Bitmap overrun"); + if (Bitmap[BitmapIdx + Idx] == 0) + continue; + assert(!TestVectors[Idx].empty() && "Test Vector doesn't exist."); + ExecVectors.push_back(TestVectors[Idx]); + } + } + // 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. @@ -493,9 +378,14 @@ class MCDCRecordProcessor { Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero()); } + // Walk the binary decision diagram to enumerate all possible test vectors. + // We start at the root node (ID == 1) with all values being DontCare. + // `Index` encodes the bitmask of true values and is initially 0. + MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare); + buildTestVector(TV, 1, 0); + // Using Profile Bitmap from runtime, mark the executed test vectors. - ExecVectors = MCDCTestVectorBuilder(Branches, Bitmap, BitmapIdx) - .findExecutedTestVectors(); + findExecutedTestVectors(); // Compare executed test vectors against each other to find an independence // pairs for each condition. This processing takes the most time. diff --git a/llvm/test/tools/llvm-cov/mcdc-const.test b/llvm/test/tools/llvm-cov/mcdc-const.test index 5424625cf6a6b..0b2c9c98d5355 100644 --- a/llvm/test/tools/llvm-cov/mcdc-const.test +++ b/llvm/test/tools/llvm-cov/mcdc-const.test @@ -61,8 +61,8 @@ // CHECKFULLCASE: | C1-Pair: constant folded // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { F, C = T } -// CHECKFULLCASE-NEXT: | 2 { T, C = T } +// CHECKFULLCASE: | 1 { T, C = T } +// CHECKFULLCASE-NEXT: | 2 { F, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% @@ -106,8 +106,8 @@ // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { F, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } +// CHECKFULLCASE: | 1 { T, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { F, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered @@ -118,8 +118,8 @@ // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { F, C, T = T } -// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } +// CHECKFULLCASE: | 1 { T, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { F, C, T = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered @@ -151,26 +151,26 @@ // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: covered: (2,3) // CHECKFULLCASE: | MC/DC Coverage for Decision: 100.00% -// CHECKFULLCASE: | 1 { F, T, C = T } -// CHECKFULLCASE-NEXT: | 2 { T, -, C = T } +// CHECKFULLCASE: | 1 { T, -, C = T } +// CHECKFULLCASE-NEXT: | 2 { F, T, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { F, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } +// CHECKFULLCASE: | 1 { T, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { F, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { F, T, C = T } -// CHECKFULLCASE-NEXT: | 2 { T, -, C = T } +// CHECKFULLCASE: | 1 { T, -, C = T } +// CHECKFULLCASE-NEXT: | 2 { F, T, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { F, C, T = T } -// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } +// CHECKFULLCASE: | 1 { T, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { F, C, T = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered diff --git a/llvm/test/tools/llvm-cov/mcdc-general.test b/llvm/test/tools/llvm-cov/mcdc-general.test index 4b59ce59d638e..753036bedaf17 100644 --- a/llvm/test/tools/llvm-cov/mcdc-general.test +++ b/llvm/test/tools/llvm-cov/mcdc-general.test @@ -19,16 +19,16 @@ // CHECK-NEXT: | // CHECK-NEXT: | C1, C2, C3, C4 Result // CHECK-NEXT: | 1 { F, -, F, - = F } -// CHECK-NEXT: | 2 { F, -, T, F = F } -// CHECK-NEXT: | 3 { T, F, F, - = F } +// CHECK-NEXT: | 2 { T, F, F, - = F } +// CHECK-NEXT: | 3 { F, -, T, F = F } // CHECK-NEXT: | 4 { T, F, T, F = F } -// CHECK-NEXT: | 5 { T, F, T, T = T } -// CHECK-NEXT: | 6 { T, T, -, - = T } +// CHECK-NEXT: | 5 { T, T, -, - = T } +// CHECK-NEXT: | 6 { T, F, T, T = T } // CHECK-NEXT: | -// CHECK-NEXT: | C1-Pair: covered: (1,6) -// CHECK-NEXT: | C2-Pair: covered: (3,6) -// CHECK-NEXT: | C3-Pair: covered: (3,5) -// CHECK-NEXT: | C4-Pair: covered: (4,5) +// CHECK-NEXT: | C1-Pair: covered: (1,5) +// CHECK-NEXT: | C2-Pair: covered: (2,5) +// CHECK-NEXT: | C3-Pair: covered: (2,6) +// CHECK-NEXT: | C4-Pair: covered: (4,6) // CHECK-NEXT: | MC/DC Coverage for Decision: 100.00% // CHECK-NEXT: | // CHECK-NEXT: ------------------ >From 8c777ebbea6f5d005de2112b88eceec9b5eeeadd Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi <geek4ci...@gmail.com> Date: Tue, 6 Feb 2024 17:06:11 +0900 Subject: [PATCH 3/5] [Coverage] MCDCRecordProcessor: Find `ExecVectors` directly Deprecate `TestVectors`, since no one uses it. This affects the output order of ExecVectors. The current impl emits sorted by binary value of ExecVector. This impl emits along the traversal of `buildTestVector()`. --- .../ProfileData/Coverage/CoverageMapping.cpp | 31 +++++++------------ llvm/test/tools/llvm-cov/mcdc-const.test | 28 ++++++++--------- llvm/test/tools/llvm-cov/mcdc-general.test | 16 +++++----- 3 files changed, 33 insertions(+), 42 deletions(-) diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index 6b189c3146328..eb0996e33b70d 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -253,9 +253,6 @@ class MCDCRecordProcessor { /// Mapping of calculated MC/DC Independence Pairs for each condition. MCDCRecord::TVPairMap IndependencePairs; - /// Total number of possible Test Vectors for the boolean expression. - MCDCRecord::TestVectors TestVectors; - /// Actual executed Test Vectors for the boolean expression, based on /// ExecutedTestVectorBitmap. MCDCRecord::TestVectors ExecVectors; @@ -267,18 +264,20 @@ class MCDCRecordProcessor { : Bitmap(Bitmap), Region(Region), Branches(Branches), NumConditions(Region.MCDCParams.NumConditions), BitmapIdx(Region.MCDCParams.BitmapIdx * CHAR_BIT), - Folded(NumConditions, false), IndependencePairs(NumConditions), - TestVectors((size_t)1 << NumConditions) {} + Folded(NumConditions, false), IndependencePairs(NumConditions) {} private: void recordTestVector(MCDCRecord::TestVector &TV, unsigned Index, MCDCRecord::CondState Result) { + if (!Bitmap[BitmapIdx + Index]) + return; + // Copy the completed test vector to the vector of testvectors. - TestVectors[Index] = TV; + ExecVectors.push_back(TV); // The final value (T,F) is equal to the last non-dontcare state on the // path (in a short-circuiting system). - TestVectors[Index].push_back(Result); + ExecVectors.back().push_back(Result); } // Walk the binary decision diagram and try assigning both false and true to @@ -308,13 +307,11 @@ class MCDCRecordProcessor { /// 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() { - for (unsigned Idx = 0; Idx < (1u << NumConditions); ++Idx) { - assert(BitmapIdx + Idx < Bitmap.size() && "Bitmap overrun"); - if (Bitmap[BitmapIdx + Idx] == 0) - continue; - assert(!TestVectors[Idx].empty() && "Test Vector doesn't exist."); - ExecVectors.push_back(TestVectors[Idx]); - } + // Walk the binary decision diagram to enumerate all possible test vectors. + // We start at the root node (ID == 1) with all values being DontCare. + // `Index` encodes the bitmask of true values and is initially 0. + MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare); + buildTestVector(TV, 1, 0); } // Find an independence pair for each condition: @@ -380,12 +377,6 @@ class MCDCRecordProcessor { Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero()); } - // Walk the binary decision diagram to enumerate all possible test vectors. - // We start at the root node (ID == 1) with all values being DontCare. - // `Index` encodes the bitmask of true values and is initially 0. - MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare); - buildTestVector(TV, 1, 0); - // Using Profile Bitmap from runtime, mark the executed test vectors. findExecutedTestVectors(); diff --git a/llvm/test/tools/llvm-cov/mcdc-const.test b/llvm/test/tools/llvm-cov/mcdc-const.test index 0b2c9c98d5355..5424625cf6a6b 100644 --- a/llvm/test/tools/llvm-cov/mcdc-const.test +++ b/llvm/test/tools/llvm-cov/mcdc-const.test @@ -61,8 +61,8 @@ // CHECKFULLCASE: | C1-Pair: constant folded // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C = T } -// CHECKFULLCASE-NEXT: | 2 { F, C = T } +// CHECKFULLCASE: | 1 { F, C = T } +// CHECKFULLCASE-NEXT: | 2 { T, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% @@ -106,8 +106,8 @@ // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, - = T } +// CHECKFULLCASE: | 1 { F, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered @@ -118,8 +118,8 @@ // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, T = T } +// CHECKFULLCASE: | 1 { F, C, T = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered @@ -151,26 +151,26 @@ // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: covered: (2,3) // CHECKFULLCASE: | MC/DC Coverage for Decision: 100.00% -// CHECKFULLCASE: | 1 { T, -, C = T } -// CHECKFULLCASE-NEXT: | 2 { F, T, C = T } +// CHECKFULLCASE: | 1 { F, T, C = T } +// CHECKFULLCASE-NEXT: | 2 { T, -, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, - = T } +// CHECKFULLCASE: | 1 { F, C, - = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, -, C = T } -// CHECKFULLCASE-NEXT: | 2 { F, T, C = T } +// CHECKFULLCASE: | 1 { F, T, C = T } +// CHECKFULLCASE-NEXT: | 2 { T, -, C = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: not covered // CHECKFULLCASE-NEXT: | C3-Pair: constant folded // CHECKFULLCASE: | MC/DC Coverage for Decision: 0.00% -// CHECKFULLCASE: | 1 { T, C, - = T } -// CHECKFULLCASE-NEXT: | 2 { F, C, T = T } +// CHECKFULLCASE: | 1 { F, C, T = T } +// CHECKFULLCASE-NEXT: | 2 { T, C, - = T } // CHECKFULLCASE: | C1-Pair: not covered // CHECKFULLCASE-NEXT: | C2-Pair: constant folded // CHECKFULLCASE-NEXT: | C3-Pair: not covered diff --git a/llvm/test/tools/llvm-cov/mcdc-general.test b/llvm/test/tools/llvm-cov/mcdc-general.test index 753036bedaf17..4b59ce59d638e 100644 --- a/llvm/test/tools/llvm-cov/mcdc-general.test +++ b/llvm/test/tools/llvm-cov/mcdc-general.test @@ -19,16 +19,16 @@ // CHECK-NEXT: | // CHECK-NEXT: | C1, C2, C3, C4 Result // CHECK-NEXT: | 1 { F, -, F, - = F } -// CHECK-NEXT: | 2 { T, F, F, - = F } -// CHECK-NEXT: | 3 { F, -, T, F = F } +// CHECK-NEXT: | 2 { F, -, T, F = F } +// CHECK-NEXT: | 3 { T, F, F, - = F } // CHECK-NEXT: | 4 { T, F, T, F = F } -// CHECK-NEXT: | 5 { T, T, -, - = T } -// CHECK-NEXT: | 6 { T, F, T, T = T } +// CHECK-NEXT: | 5 { T, F, T, T = T } +// CHECK-NEXT: | 6 { T, T, -, - = T } // CHECK-NEXT: | -// CHECK-NEXT: | C1-Pair: covered: (1,5) -// CHECK-NEXT: | C2-Pair: covered: (2,5) -// CHECK-NEXT: | C3-Pair: covered: (2,6) -// CHECK-NEXT: | C4-Pair: covered: (4,6) +// CHECK-NEXT: | C1-Pair: covered: (1,6) +// CHECK-NEXT: | C2-Pair: covered: (3,6) +// CHECK-NEXT: | C3-Pair: covered: (3,5) +// CHECK-NEXT: | C4-Pair: covered: (4,5) // CHECK-NEXT: | MC/DC Coverage for Decision: 100.00% // CHECK-NEXT: | // CHECK-NEXT: ------------------ >From 5432aecffd203f232842607ff581a20cbbf1ba3b Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi <geek4ci...@gmail.com> Date: Mon, 5 Feb 2024 00:33:40 +0900 Subject: [PATCH 4/5] Implement MCDCTVIdxBuilder (LLVM side) This accepts current version of profdata. The output might be different. See also https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798 --- .../ProfileData/Coverage/CoverageMapping.h | 24 +++ .../ProfileData/Coverage/CoverageMapping.cpp | 162 +++++++++++++++--- 2 files changed, 166 insertions(+), 20 deletions(-) diff --git a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h index 88ec60c7aa33c..45c28e6cfd792 100644 --- a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h +++ b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h @@ -32,6 +32,7 @@ #include "llvm/Support/raw_ostream.h" #include <cassert> #include <cstdint> +#include <functional> #include <iterator> #include <memory> #include <sstream> @@ -557,6 +558,29 @@ struct MCDCRecord { } }; +class MCDCTVIdxBuilder { +public: + struct MCDCNode { + int InCount = 0; + int Width; + struct { + int ID; + int Idx; + } Conds[2]; + }; + + SmallVector<MCDCNode> Nodes; + unsigned NumTestVectors; + +public: + using NodeIDs = std::tuple<unsigned, // ID1 (ends with 0) + unsigned, // ID1 for False + unsigned // ID1 for True + >; + + MCDCTVIdxBuilder(std::function<NodeIDs(bool TellSize)> Fetcher); +}; + /// A Counter mapping context is used to connect the counters, expressions /// and the obtained counter values. class CounterMappingContext { diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index eb0996e33b70d..5eb78f7a78571 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -223,9 +223,119 @@ Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { return LastPoppedValue; } +MCDCTVIdxBuilder::MCDCTVIdxBuilder( + std::function<NodeIDs(bool TellSize)> Fetcher) { + // Build Nodes and set up each InCount + int MaxID = -1; + Nodes.resize(std::get<0>(Fetcher(true))); + while (true) { + auto [ID1, FalseID1, TrueID1] = Fetcher(false); + if (ID1 == 0) + break; + int ID = ID1 - 1; + MaxID = std::max(MaxID, ID); + auto &Node = Nodes[ID]; + Node.Conds[0].ID = FalseID1 - 1; + Node.Conds[1].ID = TrueID1 - 1; + for (unsigned I = 0; I < 2; ++I) { +#ifndef NDEBUG + Node.Conds[I].Idx = INT_MIN; +#endif + int NextID = Node.Conds[I].ID; + if (NextID >= 0) + ++Nodes[NextID].InCount; + } + } + + if (MaxID < 0) + return; + + // 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()) { + int ID = *Q.begin(); + Q.erase(Q.begin()); + auto &Node = Nodes[ID]; + assert(Node.Width > 0); + + for (unsigned I = 0; I < 2; ++I) { + int NextID = Node.Conds[I].ID; + assert(NextID != 0); + if (NextID < 0) { + Decisions.emplace_back(-Node.Width, Ord++, ID, I); + assert(Ord == Decisions.size()); + continue; + } + + auto &NextNode = Nodes[NextID]; + assert(NextNode.InCount > 0); + assert(Node.Conds[I].Idx == INT_MIN); + Node.Conds[I].Idx = NextNode.Width; + NextNode.Width += Node.Width; + if (--NextNode.InCount == 0) + Q.push_back(NextID); + } + } + + std::sort(Decisions.begin(), Decisions.end()); + + // Assign TestVector Index + unsigned CurIdx = 0; + for (auto [NegWidth, Ord, ID, C] : Decisions) { + int Width = -NegWidth; + assert(Nodes[ID].Width == Width); + assert(Nodes[ID].Conds[C].Idx == INT_MIN); + assert(Nodes[ID].Conds[C].ID < 0); + Nodes[ID].Conds[C].Idx = CurIdx; + CurIdx += Width; + } + NumTestVectors = CurIdx; + +#ifndef NDEBUG + for (const auto &Node : Nodes) + for (const auto &Cond : Node.Conds) + assert(Cond.Idx != INT_MIN); +#endif +} + namespace { -class MCDCRecordProcessor { +class BranchProvider { + using NodeIDs = MCDCTVIdxBuilder::NodeIDs; + ArrayRef<const CounterMappingRegion *> Branches; + unsigned BranchIdx = 0; + +public: + BranchProvider(ArrayRef<const CounterMappingRegion *> Branches) + : Branches(Branches) {} + + std::function<NodeIDs(bool)> getFetcher() { + return [this](bool TellSize) { + if (TellSize) + return NodeIDs(Branches.size(), 0, 0); + if (BranchIdx >= Branches.size()) + return NodeIDs(0, 0, 0); + const auto *B = Branches[BranchIdx++]; + return NodeIDs(B->MCDCParams.ID, B->MCDCParams.FalseID, + B->MCDCParams.TrueID); + }; + } +}; + +class MCDCRecordProcessor : MCDCTVIdxBuilder { /// 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 @@ -257,18 +367,28 @@ class MCDCRecordProcessor { /// ExecutedTestVectorBitmap. MCDCRecord::TestVectors ExecVectors; +#ifndef NDEBUG + DenseSet<unsigned> TVIDs; +#endif + public: MCDCRecordProcessor(const BitVector &Bitmap, const CounterMappingRegion &Region, ArrayRef<const CounterMappingRegion *> Branches) - : Bitmap(Bitmap), Region(Region), Branches(Branches), + : MCDCTVIdxBuilder(BranchProvider(Branches).getFetcher()), Bitmap(Bitmap), + Region(Region), Branches(Branches), NumConditions(Region.MCDCParams.NumConditions), BitmapIdx(Region.MCDCParams.BitmapIdx * CHAR_BIT), Folded(NumConditions, false), IndependencePairs(NumConditions) {} private: - void recordTestVector(MCDCRecord::TestVector &TV, unsigned Index, + void recordTestVector(MCDCRecord::TestVector &TV, int TVIdx, unsigned Index, MCDCRecord::CondState Result) { +#ifndef NDEBUG + assert(!TVIDs.contains(TVIdx)); + TVIDs.insert(TVIdx); +#endif + if (!Bitmap[BitmapIdx + Index]) return; @@ -283,25 +403,26 @@ class MCDCRecordProcessor { // 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, unsigned ID, + void buildTestVector(MCDCRecord::TestVector &TV, int ID, int TVIdx, unsigned Index) { - const CounterMappingRegion *Branch = Map[ID]; - - TV[ID - 1] = MCDCRecord::MCDC_False; - if (Branch->MCDCParams.FalseID > 0) - buildTestVector(TV, Branch->MCDCParams.FalseID, Index); - else - recordTestVector(TV, Index, MCDCRecord::MCDC_False); - - Index |= 1 << (ID - 1); - TV[ID - 1] = MCDCRecord::MCDC_True; - if (Branch->MCDCParams.TrueID > 0) - buildTestVector(TV, Branch->MCDCParams.TrueID, Index); - else - recordTestVector(TV, Index, MCDCRecord::MCDC_True); + const auto &Node = Nodes[ID]; + + for (unsigned I = 0; I < 2; ++I) { + auto MCDCCond = (I ? MCDCRecord::MCDC_True : MCDCRecord::MCDC_False); + const auto &Cond = Node.Conds[I]; + auto NextID = Cond.ID; + Index |= I << ID; + TV[ID] = MCDCCond; + if (NextID >= 0) { + buildTestVector(TV, NextID, TVIdx + Cond.Idx, Index); + } else { + assert(TVIdx < Node.Width); + recordTestVector(TV, Cond.Idx + TVIdx, Index, MCDCCond); + } + } // Reset back to DontCare. - TV[ID - 1] = MCDCRecord::MCDC_DontCare; + TV[ID] = MCDCRecord::MCDC_DontCare; } /// Walk the bits in the bitmap. A bit set to '1' indicates that the test @@ -311,7 +432,8 @@ class MCDCRecordProcessor { // We start at the root node (ID == 1) with all values being DontCare. // `Index` encodes the bitmask of true values and is initially 0. MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare); - buildTestVector(TV, 1, 0); + buildTestVector(TV, 0, 0, 0); + assert(TVIDs.size() == NumTestVectors); } // Find an independence pair for each condition: >From 3ee8a6131de896869edd03f18e07e193c3229fe4 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi <geek4ci...@gmail.com> Date: Tue, 6 Feb 2024 21:41:43 +0900 Subject: [PATCH 5/5] Update comments and assertions --- .../ProfileData/Coverage/CoverageMapping.h | 14 +++++++--- .../ProfileData/Coverage/CoverageMapping.cpp | 28 +++++++++++-------- 2 files changed, 27 insertions(+), 15 deletions(-) diff --git a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h index 45c28e6cfd792..7341b41aed63d 100644 --- a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h +++ b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h @@ -558,14 +558,15 @@ struct MCDCRecord { } }; +/// Compute Conds[].Idx from Branch-like structure class MCDCTVIdxBuilder { public: struct MCDCNode { - int InCount = 0; - int Width; + int InCount = 0; /// Reference count; temporary use + int Width; /// Number of paths (>= 1) struct { - int ID; - int Idx; + int Idx; /// Index in TestVectors bitmap + int ID; /// Final Decision if ID<0, or NextID } Conds[2]; }; @@ -578,6 +579,11 @@ class MCDCTVIdxBuilder { unsigned // ID1 for True >; + /// Assign Idx + /// \param Fetcher Function to fetch NodeIDs. + /// returns {size,0,0} with TellSize=ture + /// returns {ID1,TrueID1,FalseID1} as the value + /// returns {0,0,0} as the terminator MCDCTVIdxBuilder(std::function<NodeIDs(bool TellSize)> Fetcher); }; diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index 5eb78f7a78571..cafb36c19c27f 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -266,25 +266,32 @@ MCDCTVIdxBuilder::MCDCTVIdxBuilder( unsigned Ord = 0; while (!Q.empty()) { - int ID = *Q.begin(); - Q.erase(Q.begin()); + 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) { int NextID = Node.Conds[I].ID; - assert(NextID != 0); + 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); assert(Node.Conds[I].Idx == INT_MIN); + + // Assign Idx Node.Conds[I].Idx = NextNode.Width; NextNode.Width += Node.Width; + + // Ready if all incomings are processed. if (--NextNode.InCount == 0) Q.push_back(NextID); } @@ -292,7 +299,7 @@ MCDCTVIdxBuilder::MCDCTVIdxBuilder( std::sort(Decisions.begin(), Decisions.end()); - // Assign TestVector Index + // Assign TestVector Indices in Decision Nodes unsigned CurIdx = 0; for (auto [NegWidth, Ord, ID, C] : Decisions) { int Width = -NegWidth; @@ -313,6 +320,7 @@ MCDCTVIdxBuilder::MCDCTVIdxBuilder( namespace { +/// Returns the fetcher to return {ID1,TrueID1,FalseID1} from Branches class BranchProvider { using NodeIDs = MCDCTVIdxBuilder::NodeIDs; ArrayRef<const CounterMappingRegion *> Branches; @@ -368,7 +376,7 @@ class MCDCRecordProcessor : MCDCTVIdxBuilder { MCDCRecord::TestVectors ExecVectors; #ifndef NDEBUG - DenseSet<unsigned> TVIDs; + DenseSet<unsigned> TVIdxs; #endif public: @@ -384,10 +392,7 @@ class MCDCRecordProcessor : MCDCTVIdxBuilder { private: void recordTestVector(MCDCRecord::TestVector &TV, int TVIdx, unsigned Index, MCDCRecord::CondState Result) { -#ifndef NDEBUG - assert(!TVIDs.contains(TVIdx)); - TVIDs.insert(TVIdx); -#endif + assert(TVIdxs.insert(TVIdx).second && "Duplicate TVIdx"); if (!Bitmap[BitmapIdx + Index]) return; @@ -429,11 +434,12 @@ class MCDCRecordProcessor : MCDCTVIdxBuilder { /// 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 == 1) with all values being DontCare. + // 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, MCDCRecord::MCDC_DontCare); buildTestVector(TV, 0, 0, 0); - assert(TVIDs.size() == NumTestVectors); + assert(TVIdxs.size() == NumTestVectors && "TVIdxs wasn't fulfilled"); } // Find an independence pair for each condition: _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
