[llvm-cov] Simplify and optimize MC/DC computation (#79727)

Update code from https://reviews.llvm.org/D138847

`buildTestVector` is a standard DFS (walking a reduced ordered binary
decision diagram). Avoid shouldCopyOffTestVectorFor{True,False}Path
complexity and redundant `Map[ID]` lookups.

`findIndependencePairs` unnecessarily uses four nested loops (n<=6) to
find independence pairs. Instead, enumerate the two execution vectors
and find the number of mismatches. This algorithm can be optimized using
the marking function technique described in _Efficient Test Coverage
Measurement for MC/DC,  2013_, but this may be overkill.

1 files changed, 41 insertions, 101 deletions

diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
index da8e1d8..937d95c 100644
--- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
+++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
@@ -286,17 +286,8 @@ public:
         TestVectors((size_t)1 << NumConditions) {}
 
 private:
-  void recordTestVector(MCDCRecord::TestVector &TV,
+  void recordTestVector(MCDCRecord::TestVector &TV, unsigned Index,
                         MCDCRecord::CondState Result) {
-    // Calculate an index that is used to identify the test vector in a vector
-    // of test vectors.  This index also corresponds to the index values of an
-    // MCDC Region's bitmap (see findExecutedTestVectors()).
-    unsigned Index = 0;
-    for (auto Cond = std::rbegin(TV); Cond != std::rend(TV); ++Cond) {
-      Index <<= 1;
-      Index |= (*Cond == MCDCRecord::MCDC_True) ? 0x1 : 0x0;
-    }
-
     // Copy the completed test vector to the vector of testvectors.
     TestVectors[Index] = TV;
 
@@ -305,38 +296,25 @@ private:
     TestVectors[Index].push_back(Result);
   }
 
-  void shouldCopyOffTestVectorForTruePath(MCDCRecord::TestVector &TV,
-                                          unsigned ID) {
-    // Branch regions are hashed based on an ID.
-    const CounterMappingRegion *Branch = Map[ID];
-
-    TV[ID - 1] = MCDCRecord::MCDC_True;
-    if (Branch->MCDCParams.TrueID > 0)
-      buildTestVector(TV, Branch->MCDCParams.TrueID);
-    else
-      recordTestVector(TV, MCDCRecord::MCDC_True);
-  }
-
-  void shouldCopyOffTestVectorForFalsePath(MCDCRecord::TestVector &TV,
-                                           unsigned ID) {
-    // Branch regions are hashed based on an ID.
+  // 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);
+      buildTestVector(TV, Branch->MCDCParams.FalseID, Index);
     else
-      recordTestVector(TV, MCDCRecord::MCDC_False);
-  }
+      recordTestVector(TV, Index, MCDCRecord::MCDC_False);
 
-  /// Starting with the base test vector, build a comprehensive list of
-  /// possible test vectors by recursively walking the branch condition IDs
-  /// provided. Once an end node is reached, record the test vector in a vector
-  /// of test vectors that can be matched against during MC/DC analysis, and
-  /// then reset the positions to 'DontCare'.
-  void buildTestVector(MCDCRecord::TestVector &TV, unsigned ID = 1) {
-    shouldCopyOffTestVectorForTruePath(TV, ID);
-    shouldCopyOffTestVectorForFalsePath(TV, ID);
+    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;
@@ -353,71 +331,33 @@ private:
     }
   }
 
-  /// For a given condition and two executed Test Vectors, A and B, see if the
-  /// two test vectors match forming an Independence Pair for the condition.
-  /// For two test vectors to match, the following must be satisfied:
-  /// - The condition's value in each test vector must be opposite.
-  /// - The result's value in each test vector must be opposite.
-  /// - All other conditions' values must be equal or marked as "don't care".
-  bool matchTestVectors(unsigned Aidx, unsigned Bidx, unsigned ConditionIdx) {
-    const MCDCRecord::TestVector &A = ExecVectors[Aidx];
-    const MCDCRecord::TestVector &B = ExecVectors[Bidx];
-
-    // If condition values in both A and B aren't opposites, no match.
-    // Because a value can be 0 (false), 1 (true), or -1 (DontCare), a check
-    // that "XOR != 1" will ensure that the values are opposites and that
-    // neither of them is a DontCare.
-    //  1 XOR  0 ==  1 | 0 XOR  0 ==  0 | -1 XOR  0 == -1
-    //  1 XOR  1 ==  0 | 0 XOR  1 ==  1 | -1 XOR  1 == -2
-    //  1 XOR -1 == -2 | 0 XOR -1 == -1 | -1 XOR -1 ==  0
-    if ((A[ConditionIdx] ^ B[ConditionIdx]) != 1)
-      return false;
-
-    // If the results of both A and B aren't opposites, no match.
-    if ((A[NumConditions] ^ B[NumConditions]) != 1)
-      return false;
-
-    for (unsigned Idx = 0; Idx < NumConditions; ++Idx) {
-      // Look for other conditions that don't match. Skip over the given
-      // Condition as well as any conditions marked as "don't care".
-      const auto ARecordTyForCond = A[Idx];
-      const auto BRecordTyForCond = B[Idx];
-      if (Idx == ConditionIdx ||
-          ARecordTyForCond == MCDCRecord::MCDC_DontCare ||
-          BRecordTyForCond == MCDCRecord::MCDC_DontCare)
-        continue;
-
-      // If there is a condition mismatch with any of the other conditions,
-      // there is no match for the test vectors.
-      if (ARecordTyForCond != BRecordTyForCond)
-        return false;
-    }
-
-    // Otherwise, match.
-    return true;
-  }
-
-  /// Find all possible Independence Pairs for a boolean expression given its
-  /// executed Test Vectors.  This process involves looking at each condition
-  /// and attempting to find two Test Vectors that "match", giving us a pair.
+  // 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 each condition.
-    for (unsigned C = 0; C < NumConditions; ++C) {
-      bool PairFound = false;
-
-      // For each executed test vector.
-      for (unsigned I = 0; !PairFound && I < NumTVs; ++I) {
-        // Compared to every other executed test vector.
-        for (unsigned J = 0; !PairFound && J < NumTVs; ++J) {
-          if (I == J)
+    for (unsigned I = 1; I < NumTVs; ++I) {
+      const MCDCRecord::TestVector &A = ExecVectors[I];
+      for (unsigned J = 0; J < I; ++J) {
+        const MCDCRecord::TestVector &B = ExecVectors[J];
+        // Enumerate two execution vectors whose outcomes are different.
+        if (A[NumConditions] == B[NumConditions])
+          continue;
+        unsigned Flip = NumConditions, Idx;
+        for (Idx = 0; Idx < NumConditions; ++Idx) {
+          MCDCRecord::CondState ACond = A[Idx], BCond = B[Idx];
+          if (ACond == BCond || ACond == MCDCRecord::MCDC_DontCare ||
+              BCond == MCDCRecord::MCDC_DontCare)
             continue;
-
-          // If a matching pair of vectors is found, record them.
-          if ((PairFound = matchTestVectors(I, J, C)))
-            IndependencePairs[C] = std::make_pair(I + 1, J + 1);
+          if (Flip != NumConditions)
+            break;
+          Flip = Idx;
         }
+        // If the two vectors differ in exactly one condition, ignoring DontCare
+        // conditions, we have found an independence pair.
+        if (Idx == NumConditions && Flip != NumConditions)
+          IndependencePairs.insert({Flip, std::make_pair(J + 1, I + 1)});
       }
     }
   }
@@ -454,11 +394,11 @@ public:
       Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero());
     }
 
-    // Initialize a base test vector as 'DontCare'.
+    // 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);
-
-    // Use the base test vector to build the list of all possible test vectors.
-    buildTestVector(TV);
+    buildTestVector(TV, 1, 0);
 
     // Using Profile Bitmap from runtime, mark the executed test vectors.
     findExecutedTestVectors(ExecutedTestVectorBitmap);