Introduce mcdc::TVIdxBuilder (LLVM side, NFC) (#80676)

This is a preparation of incoming Clang changes (#82448) and just checks
`TVIdx` is calculated correctly. NFC.

`TVIdxBuilder` calculates deterministic Indices for each Condition Node.
It is used for `clang` to emit `TestVector` indices (aka ID) and for
`llvm-cov` to reconstruct `TestVectors`.

This includes the unittest `CoverageMappingTest.TVIdxBuilder`.

See also
https://discourse.llvm.org/t/rfc-coverage-new-algorithm-and-file-format-for-mc-dc/76798

1 files changed, 56 insertions, 0 deletions

diff --git a/llvm/unittests/ProfileData/CoverageMappingTest.cpp b/llvm/unittests/ProfileData/CoverageMappingTest.cpp
index 425b3d1..f063a33 100644
--- a/llvm/unittests/ProfileData/CoverageMappingTest.cpp
+++ b/llvm/unittests/ProfileData/CoverageMappingTest.cpp
@@ -16,6 +16,7 @@
 #include "llvm/Testing/Support/SupportHelpers.h"
 #include "gtest/gtest.h"
 
+#include <map>
 #include <ostream>
 #include <utility>
 
@@ -1074,4 +1075,59 @@ TEST(CoverageMappingTest, filename_compilation_dir) {
   }
 }
 
+TEST(CoverageMappingTest, TVIdxBuilder) {
+  // ((n0 && n3) || (n2 && n4) || (n1 && n5))
+  static const std::array<mcdc::ConditionIDs, 6> Branches = {{
+      {2, 3},
+      {-1, 5},
+      {1, 4},
+      {2, -1},
+      {1, -1},
+      {-1, -1},
+  }};
+  int Offset = 1000;
+  auto TheBuilder = mcdc::TVIdxBuilder(
+      SmallVector<mcdc::ConditionIDs>(ArrayRef(Branches)), Offset);
+  EXPECT_TRUE(TheBuilder.NumTestVectors < TheBuilder.HardMaxTVs);
+  EXPECT_EQ(TheBuilder.Indices.size(), 6u);
+  EXPECT_EQ(TheBuilder.NumTestVectors, 15);
+
+  std::map<int, int> Decisions;
+  for (unsigned I = 0; I < TheBuilder.Indices.size(); ++I) {
+    struct Rec {
+      int Width;
+      std::array<int, 2> Indices;
+    };
+    static const std::array<Rec, 6> IndicesRefs = {{
+        {1, {0, 0}},
+        {4, {1000, 0}},
+        {2, {0, 0}},
+        {1, {1, 1014}},
+        {2, {2, 1012}},
+        {4, {1004, 1008}},
+    }};
+    EXPECT_EQ(TheBuilder.Indices[I], IndicesRefs[I].Indices);
+
+#ifndef NDEBUG
+    const auto &Node = TheBuilder.SavedNodes[I];
+    EXPECT_EQ(Node.Width, IndicesRefs[I].Width);
+    for (int C = 0; C < 2; ++C) {
+      auto Index = TheBuilder.Indices[I][C];
+      if (Node.NextIDs[C] < 0)
+        EXPECT_TRUE(Decisions.insert({Index, Node.Width}).second);
+    }
+#endif
+  }
+
+#ifndef NDEBUG
+  int NextIdx = Offset;
+  for (const auto [Index, Width] : Decisions) {
+    EXPECT_EQ(Index, NextIdx);
+    NextIdx += Width;
+  }
+  // The sum of Width(s) is NumTVs.
+  EXPECT_EQ(NextIdx, Offset + TheBuilder.NumTestVectors);
+#endif
+}
+
 } // end anonymous namespace