Key metrics for code coverage include:

• function coverage: determines whether each function beenexecuted.
• line coverage (aka statement coverage): determines whether everyline has been executed.
• branch coverage: ensures that both the true and false branches ofeach conditional statement or the conditional of each loop statementbeen evaluated.

Condition coverage offers a more fine-grained evaluation of branchcoverage. It requires that each individual boolean subexpression(condition) within a compound expression be evaluated to both true andfalse. For example, in the boolean expressionif (a>0 && f(b) && c==0), each ofa>0, f(b), and c==0, conditioncoverage would require tests that:

• Evaluate a>0 to true and false
• Evaluate f(b) to true and false
• Evaluate c==0 to true and false

A condition combination refers to a specific set of boolean valuesassigned to individual conditions within a boolean expression. Multiplecondition coverage ensures that all possible condition combinations aretested. In the example above, with three conditions, there would be 2³ =8 possible condition combinations.

Modified condition/decisioncoverage

While multiple condition coverage may not be practical, Modifiedcondition/decision coverage (MC/DC) offers a more cost-effectiveapproach. Introduced in 1992 by DO-178B (latersuperseded by DO-178C), MC/DC became mandatory for Level A software inthe aviation industry. Its popularity has since extended tosafety-critical applications in automotive (ISO 26262) and otherdomains. Notably, SQLite boasts 100% MC/DC coverage link to SQLitetesting page: https://sqlite.org/testing.html#mcdc.

Consider a boolean expression like(A && B) || (C && D). This has fourconditions (A, B, C, and D), each potentially a subexpression likex>0. Tests evaluate condition combinations (ABCD) andtheir corresponding outcomes.

Multiple flavors of MC/DC exist, with Unique-Cause MC/DC representingthe strongest variant. When demonstrating the independence of A in theboolean expression (A && B) || (C && D),Unique-Cause MC/DC requires two tests with different outcomes and:

• A is false in one test and true in the other.
• B, C and D values remain identical.

The two tests form an independence pair for A. Acoverage set comprises tests offering such independence pairsfor each condition. However, achieving this set may be impossible in thepresence of strongly coupled conditions.

Coupling examples:

• The two conditions in x==0 && x!=0 arestrongly coupled: changing one automatically changes theother.
• x==0 || x==1 || x==3 exhibits weakly coupledconditions: changing x from 0 to 2 alters only the first condition,while changing it to 1 affects the first two.

Masking MC/DC

Masking involves setting one operand of a boolean operatorto a value that renders the other operand's influence on the outcomeirrelevant. Examples:

• Masking the LHS of && withA && false (outcome is always false, unaffected byA).
• Masking the RHS of && withfalse && B (outcome is always false, unaffected byB).
• Masking the LHS of || with A || true(outcome is always true, unaffected by A).
• Masking the RHS of || with true || B(outcome is always true, unaffected by B).

Masking MC/DC demonstrates condition independence by showingthe condition in question affects the outcome and keeping otherconditions masked. For example, to provde the independence of A in theboolean expression (A && B) || (C && D), Cand D can change values as long as C && D remainsfalse. In this way, each condition allows more independence pairs thanUnique-Cause MC/DC.

In 2001, masking MC/DC has been considered an acceptable method formeeting objective 5 of Table A-7 in DO-178B.

Unique-Cause + Masking MC/DC is weaker than Unique-Cause MC/DC butstronger than Masking MC/DC, allowing masking only for strongly coupledconditions.

Minimum coverage set size

If an expression has N unique conditions, both Unique-Cause MC/DC andUnique-Cause Masking MC/DC require a minimum of N+1 tests. It is notclear whether this is an exact bound. WhenN<=4, it is always possible to get Unique-Cause MC/DC with N+1tests. Masking MC/DC requires a minimum of ceil(2*sqrt(N)).See An Investigation of Three Forms of the Modified ConditionDecision Coverage (MCDC) Criterion for detail.

Binary decision diagram

Binary decision diagram (BDD) is a data structure that is used torepresent a boolean function. Boolean expressions with&& and || compile to reduced orderedBDDs.

There is another coverage metric called object branch coverage, whichdetermines whether each branch is taken at least once and is also nottaken at least once. Object branch coverage does not guarantee MC/DC,but does when the reduced ordered BDD is a tree.

(B && C) || A is a non-tree example thatachieving object branch coverage requires 3 tests, which areinsufficient to guarantee MC/DC. If the expression is rewritten toA || (B && C), then the reduced ordered BDD willbecome a tree, making object branch coverage guarantee MC/DC.

GCC

Efficient Test Coverage Measurement for MC/DC describes acode instrumentation technique to determine masking MC/DC. For a booleanexpression with N conditions, only 2*N bits are needed.

Jørgen Kvalsvik posted the first MC/DC patch to gcov in March 2022and PATCHv9 in December 2023. With this patch, we compile source files usinggcc --coverage -fcondition-coverage and pass--conditions to gcov. The output should look like:

1
2
3
4
5
6
7
8
9
10
11

        3:   17:void fn (int a, int b, int c, int d) {
        3:   18:    if ((a && (b || c)) && d)
conditions covered 3/8
condition  0 not covered (true false)
condition  1 not covered (true)
condition  2 not covered (true)
condition  3 not covered (true)
        1:   19:        x = 1;
        -:   20:    else
        2:   21:        x = 2;
        3:   22:}

Since GCC 3.4, GCC has employed .gcno and.gcda files to store control-flow graph information and arcexecution counts, respectively. This format has undergone enhancementsbut remains structurally consistent. .gcno files containfunction records describeing basic blocks, arcs between them, and lineswithin each basic block. Column information is only available forfunctions. .gcda files store arc execution counts.

gcov identifies basic blocks on a particular line (usually one) andlocates successor basic blocks to infer branches. When -bis specified, gcov prints branch probabilities, though the output may beunclear since .gcno does not encode what true and falsebranches are.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

cat > a.c <<e
int test(int a, int b) {
  if (a > 0 && b > 0)
    return 1;
  return 0;
}

int main() {
  test(0, 1);
  test(1, 0);
  test(1, 1);
}
e
gcc --coverage a.c -o a && ./a
gcov -b a.

The output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

        -:    0:Source:a.c
        -:    0:Graph:a.gcno
        -:    0:Data:a.gcda
        -:    0:Runs:1
function test called 3 returned 100% blocks executed 100%
        3:    1:int test(int a, int b) {
        3:    2:  if (a > 0 && b > 0)
branch  0 taken 67% (fallthrough)
branch  1 taken 33%
branch  2 taken 50% (fallthrough)
branch  3 taken 50%
        1:    3:    return 1;
        2:    4:  return 0;
        -:    5:}
        -:    6:
function main called 1 returned 100% blocks executed 100%
        1:    7:int main() {
        1:    8:  test(0, 1);
call    0 returned 100%
        1:    9:  test(1, 0);
call    0 returned 100%
        1:   10:  test(1, 1);
call    0 returned 100%
        -:   11:}

Clang

Clang offers a sophisticated approach to code coverage called Source-basedCode Coverage. Unlike gcov's line-oriented method, Clang utilizescoverage mapping, a format capable of encoding:

• Nested control structures
• Line/column information
• Macro expansion tracking (ExpansionRegion)

In January 2021, the framework has been enhanced with branchcoverage. This addition:

• Creates a new region for && and ||operators.
• Tracks execution counts for individual conditions.

The primary data structure changes are the additions of the secondcounter (CountedRegion::FalseExecutionCount andCounterMappingRegion::FalseCount) and a newCounterMappingRegion::RegionKind namedBranchRegion.

1
2
3
4
5
6
7

x = x > 0 && y > 0;  // 2 extra counters

if (x > 0 && y > 0)  // 2 extra counters, while 1 suffices
  x = 1;

if (true && y > 0)   // 2 extra counters, while 1 suffices
  x = 1;

The presentation "Branch Coverage: Squeezing more out of LLVMSource-based Code Coverage, 2020" elaborates on the design.

1
2
3
4

clang -fprofile-instr-generate -fcoverage-mapping a.c -o a
./a
llvm-profdata merge -sparse default.profraw -o a.profdata
llvm-cov show a -instr-profile=a.profdata -show-branches=count

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  1|      3|int test(int a, int b) {
  2|      3|  if (a > 0 && b > 0)
------------------
|  Branch (2:7): [True: 2, False: 1]
|  Branch (2:16): [True: 1, False: 1]
------------------
  3|      1|    return 1;
  4|      2|  return 0;
  5|      3|}
  6|       |
  7|      1|int main() {
  8|      1|  test(0, 1);
  9|      1|  test(1, 0);
 10|      1|  test(1, 1);
 11|      1|}

A Rust feature request was since then filed:https://github.com/rust-lang/rust/issues/79649

In December 2023, Clang's Source-based Code Coverage got maskingMC/DC capability.

• -fcoverage-mcdc tells Clang to instrument&& and || expressions to record thecondition combinations and outcomes, and store the reduced ordered BDDsinto the coverage mapping section. The bitmap is stored in the__llvm_prf_bits section in a rawprofile.
• llvm-profdata merge merges bitmaps from multiple rawprofiles and stores the merged bitmap into an indexed profile.
• When passing --show-mcdc to llvm-cov show,llvm-cov reads a profdata file, retrieves the bitmap,computes independence pairs, and print the information.

Clang adopts a distinct approach to Masking MC/DC compared to thepaper "Efficient Test Coverage Measurement for MC/DC". Insteadof complex masking value computation, it uses a "boring algorithm":

• Encodes boolean expressions with N conditions as integers within[0, 2**N).
• When the expression result is determined, sets a bit in a bitmapindexed by the integer.
• Limits condition count to 6 for space optimization.

For example,

1
2

if (a && b || c)
  return 1;

Let's say in one execution path a=c=1 andb=0. the condition combination (0b101) leads to an index of5. The instrumentation locates the relevant word in the bitmap and setthe bit 5.

The approach is described in detail in "MC/DC: Enablingeasy-to-use safety-critical code coverage analysis with LLVM" in2022 LLVM Developers' Meeting.

While this method requires more memory (2**N vs.2*N), it simplifies instrumentation with just one bitwiseOR instruction for each condition, instead of possibly two (bitwise ANDplus bitwise OR). Determining independent pairs involves a brute-forcealgorithm in llvm-cov, which has a high time complexity but acceptabledue to the limited condition count.

References

• An Investigation of Three Forms of the Modified Condition DecisionCoverage (MCDC) Criterion, John Joseph Chilenski, 2011
• Formalization and Comparison of MCDC and Object Branch CoverageCriteria, 2012
• Efficient Test Coverage Measurement for MC/DC, 2013
• Branch Coverage: Squeezing more out of LLVM Source-based CodeCoverage, 2020
• MC/DC: Enabling easy-to-use safety-critical code coverage analysiswith LLVM, 2022