================
@@ -353,71 +331,30 @@ class MCDCRecordProcessor {
}
}
- /// 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.
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;
}
----------------
MaskRay wrote:
I left some notes on
https://maskray.me/blog/2024-01-28-mc-dc-and-compiler-implementations
GCC has a pending patch implementing MC/DC as well and they apply an algorithm
described by _Efficient Test Coverage Measurement for MC/DC_, which is linear
in terms of the number of conditions.
https://github.com/llvm/llvm-project/pull/79727
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
