Add support for branch coverage in source-based coverage

[marco-c]

Similarly to what is being done in LLVM and Clang: https://reviews.llvm.org/D84467.

[mati865]

cc @richkadel you might want to include it in #79121

[richkadel]

Actually, at last I checked, this is not in any stable version of LLVM yet. I think it's feasible to stabilize Rust coverage in rustc, based on the current feature of LLVM InstrProf, without depending on proposed future LLVM features. So, IMO, I don't think we should add this to the tracking issue, as a dependency. In fact, until this capability is stabilized in LLVM, and available in a version of LLVM that's supported by rustc, I think it makes sense to keep this as a stand-alone feature request / enhancement.

Let me know if any of my assumptions are incorrect.

[richkadel]

Cc @tmandry

[mati865]

I have no idea how adding features like that works, I thought it will be available right away in LLVM 12 around March.

[tmandry]

Neat. This would certainly improve the way we present coverage for these things, and might make it possible to be more intuitive about how we handle closing braces.

Just to throw it out there, since I'm thinking about async/await right now: This does offer an intriguing possibility of measuring drops at await points. It's possible for buggy code to assume it will never get canceled at an await point, when in fact that's part of the contract. It would be nice if we could highlight this in coverage results. Though explicitly testing cancelation at every await point sounds daunting...

It should be there in the next major version of LLVM, whenever that is.

[matthargett]

Looks like this feature was released in LLVM 12.0.0:
https://releases.llvm.org/12.0.0/docs/CoverageMappingFormat.html

14.0.0 was released 2022 March. Similar to the approved suggestion in other issues, where it was decided that an LLVM 11 feature could be used once LLVM 13 was released, could the requirement for code coverage working now be LLVM 12?

I see the original umbrella tracking issue for standardized Rust coverage options still has a few issues open, but it otherwise looks stable and settled.

[richkadel]

I should have posted this comment a while ago. (It was discussed when upgrading the coverage mapping format to version 6, in PR #91207).

Before anyone puts much effort into implementing LLVM "branch coverage", I recommend writing a test program that demonstrates where the existing Rust coverage region report would be improved with branch coverage. It's possible that branch coverage adds no value.

Rusts existing coverage regions include counters for both sides of a branch condition, even when implied. For example, an if with no else still generates a coverage region and reported counter for both true and false results. The code region for the false branch is typically shown in a coverage region report as a count one character beyond the if block's closing brace. Something like:

63    if some_condition {
42        statements();
63    }
       ^21

So from this you can already tell that some_condition was true 42 times and false 21 times.

(I think Clang's coverage may not have reported the implied else counts this way, so branch coverage may have closed a gap in Clang's reporting.)

Adding branch coverage support to Rust may or may not be worth the effort, but if someone wants to implement it, I'm happy to provide some guidance or answer questions.

[Swatinem]

I think the main benefit of branch coverage, and what I as a potential user of it would like to see, is that it will point directly to the source region corresponding to the branching condition.

Implementation (MIR) wise, all the counters are there. https://rustc-dev-guide.rust-lang.org/llvm-coverage-instrumentation.html is very detailed about how this all works. And in theory, implementing branch coverage would consist of introducing new counters that just "reference" existing counters for the true/false branch.

But to repeat, I think this is rather a tooling and DX thing. Having a "zero-width" marker after the closing brace that happens to have 0 hits does not mean anything to developers. They want to see clearly that some_condition was never false.
The way the counter is being reported is unintuitive and does not provide as much value to developers as clearly flagging the branching condition would.

[winksaville]

Before anyone puts much effort into implementing LLVM "branch coverage", I recommend writing a test program that demonstrates where the existing Rust coverage region report would be improved with branch coverage. It's possible that branch coverage adds no value.

Here is a possible example, I created exper-code-coverage, where I was comparing cargo-tarpaulin and cargo-llvm-cov crates. I created short_circuit_and() and if_short_circuit_and() with identical tests and if I run cargo llvm-cov I get 100% coverage, as expected:

wink@3900x 22-08-15T00:05:12.879Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/if_short_circuit_and.rs 
     1  pub fn if_short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      if a < b {
     3          c < d
     4      } else {
     5          false
     6      }
     7  }
     8
     9  #[cfg(test)]
    10  mod tests {
    11      use super::*;
    12
    13      // llvm-cov 100% if all are enabled.
    14
    15      // llvm-cov 85.71% if only this is enabled.
    16      #[test]
    17      pub fn test_short_circuit_and_first_false() {
    18          assert_eq!(if_short_circuit_and(20, 10, 30, 40), false);
    19      }
    20
    21      // llvm-cov 85.71% if only this is enabled
    22      #[test]
    23      pub fn test_short_circuit_and_both_true() {
    24          assert_eq!(if_short_circuit_and(10, 20, 30, 40), true);
    25      }
    26  }
wink@3900x 22-08-15T00:05:19.936Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/short_circuit_and.rs 
     1  pub fn short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      a < b && c < d
     3  }
     4
     5  #[cfg(test)]
     6  mod tests {
     7      use super::*;
     8
     9      // llvm-cov 100% if all are enabled.
    10
    11      // llvm-cov 83.33% if only this is enabled
    12      #[test]
    13      pub fn test_short_circuit_and_first_false() {
    14          assert_eq!(short_circuit_and(20, 10, 30, 40), false);
    15      }
    16
    17      // llvm-cov 100% if only this is enabled
    18      #[test]
    19      pub fn test_short_circuit_and_both_true() {
    20          assert_eq!(short_circuit_and(10, 20, 30, 40), true);
    21      }
    22  }
wink@3900x 22-08-15T00:05:24.119Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo llvm-cov
   Compiling exper-code-coverage v0.2.0 (/home/wink/prgs/rust/myrepos/exper-code-coverage)
    Finished test [unoptimized + debuginfo] target(s) in 0.68s
     Running unittests src/lib.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-f4d7ca3a8a720d31)

running 4 tests
test if_short_circuit_and::tests::test_short_circuit_and_both_true ... ok
test short_circuit_and::tests::test_short_circuit_and_both_true ... ok
test if_short_circuit_and::tests::test_short_circuit_and_first_false ... ok
test short_circuit_and::tests::test_short_circuit_and_first_false ... ok

test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/main.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-c502fcb0cc109ca3)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/cli.rs (target/llvm-cov-target/debug/deps/cli-55e882f44094d43e)

running 1 test
test test_no_params ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Filename                      Regions    Missed Regions     Cover   Functions  Missed Functions  Executed       Lines      Missed Lines     Cover    Branches   Missed Branches     Cover
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
if_short_circuit_and.rs            10                 0   100.00%           5                 0   100.00%          13                 0   100.00%           0                 0         -
lib.rs                              1                 0   100.00%           1                 0   100.00%           1                 0   100.00%           0                 0         -
main.rs                             2                 0   100.00%           2                 0   100.00%           4                 0   100.00%           0                 0         -
short_circuit_and.rs                9                 0   100.00%           5                 0   100.00%          11                 0   100.00%           0                 0         -
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TOTAL                              22                 0   100.00%          13                 0   100.00%          29                 0   100.00%           0                 0         -

If I only include the first test, test_short_circuit_and_first_false() I don't get 100% coverage for either if_short_circuit_and.rs or short_circuit_and.rs, which is also as expected:

wink@3900x 22-08-15T00:08:33.760Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/if_short_circuit_and.rs 
     1  pub fn if_short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      if a < b {
     3          c < d
     4      } else {
     5          false
     6      }
     7  }
     8
     9  #[cfg(test)]
    10  mod tests {
    11      use super::*;
    12
    13      // llvm-cov 100% if all are enabled.
    14
    15      // llvm-cov 85.71% if only this is enabled.
    16      #[test]
    17      pub fn test_short_circuit_and_first_false() {
    18          assert_eq!(if_short_circuit_and(20, 10, 30, 40), false);
    19      }
    20
    21      //// llvm-cov 85.71% if only this is enabled
    22      //#[test]
    23      //pub fn test_short_circuit_and_both_true() {
    24      //    assert_eq!(if_short_circuit_and(10, 20, 30, 40), true);
    25      //}
    26  }
wink@3900x 22-08-15T00:08:35.296Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/short_circuit_and.rs 
     1  pub fn short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      a < b && c < d
     3  }
     4
     5  #[cfg(test)]
     6  mod tests {
     7      use super::*;
     8
     9      // llvm-cov 100% if all are enabled.
    10
    11      // llvm-cov 83.33% if only this is enabled
    12      #[test]
    13      pub fn test_short_circuit_and_first_false() {
    14          assert_eq!(short_circuit_and(20, 10, 30, 40), false);
    15      }
    16
    17      //// llvm-cov 100% if only this is enabled
    18      //#[test]
    19      //pub fn test_short_circuit_and_both_true() {
    20      //    assert_eq!(short_circuit_and(10, 20, 30, 40), true);
    21      //}
    22  }
wink@3900x 22-08-15T00:08:37.294Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo llvm-cov
   Compiling exper-code-coverage v0.2.0 (/home/wink/prgs/rust/myrepos/exper-code-coverage)
    Finished test [unoptimized + debuginfo] target(s) in 0.67s
     Running unittests src/lib.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-f4d7ca3a8a720d31)

running 2 tests
test short_circuit_and::tests::test_short_circuit_and_first_false ... ok
test if_short_circuit_and::tests::test_short_circuit_and_first_false ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/main.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-c502fcb0cc109ca3)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/cli.rs (target/llvm-cov-target/debug/deps/cli-55e882f44094d43e)

running 1 test
test test_no_params ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Filename                      Regions    Missed Regions     Cover   Functions  Missed Functions  Executed       Lines      Missed Lines     Cover    Branches   Missed Branches     Cover
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
if_short_circuit_and.rs             7                 1    85.71%           3                 0   100.00%           9                 1    88.89%           0                 0         -
lib.rs                              1                 0   100.00%           1                 0   100.00%           1                 0   100.00%           0                 0         -
main.rs                             2                 0   100.00%           2                 0   100.00%           4                 0   100.00%           0                 0         -
short_circuit_and.rs                6                 1    83.33%           3                 0   100.00%           7                 0   100.00%           0                 0         -
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TOTAL                              16                 2    87.50%           9                 0   100.00%          21                 1    95.24%           0                 0         -

But, if I only include the last test I get less than 100% for if_short_circuit_and.rs, but 100% coverage for short_circuit_and.rs, this is not expected:

wink@3900x 22-08-15T00:10:59.494Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/if_short_circuit_and.rs 
     1  pub fn if_short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      if a < b {
     3          c < d
     4      } else {
     5          false
     6      }
     7  }
     8
     9  #[cfg(test)]
    10  mod tests {
    11      use super::*;
    12
    13      // llvm-cov 100% if all are enabled.
    14
    15      // llvm-cov 85.71% if only this is enabled.
    16      //#[test]
    17      //pub fn test_short_circuit_and_first_false() {
    18      //    assert_eq!(if_short_circuit_and(20, 10, 30, 40), false);
    19      //}
    20
    21      // llvm-cov 85.71% if only this is enabled
    22      #[test]
    23      pub fn test_short_circuit_and_both_true() {
    24          assert_eq!(if_short_circuit_and(10, 20, 30, 40), true);
    25      }
    26  }
wink@3900x 22-08-15T00:11:00.865Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n src/short_circuit_and.rs 
     1  pub fn short_circuit_and(a: i32, b: i32, c: i32, d: i32) -> bool {
     2      a < b && c < d
     3  }
     4
     5  #[cfg(test)]
     6  mod tests {
     7      use super::*;
     8
     9      // llvm-cov 100% if all are enabled.
    10
    11      //// llvm-cov 83.33% if only this is enabled
    12      //#[test]
    13      //pub fn test_short_circuit_and_first_false() {
    14      //    assert_eq!(short_circuit_and(20, 10, 30, 40), false);
    15      //}
    16
    17      // llvm-cov 100% if only this is enabled
    18      #[test]
    19      pub fn test_short_circuit_and_both_true() {
    20          assert_eq!(short_circuit_and(10, 20, 30, 40), true);
    21      }
    22  }
wink@3900x 22-08-15T00:11:02.440Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo llvm-cov
   Compiling exper-code-coverage v0.2.0 (/home/wink/prgs/rust/myrepos/exper-code-coverage)
    Finished test [unoptimized + debuginfo] target(s) in 0.68s
     Running unittests src/lib.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-f4d7ca3a8a720d31)

running 2 tests
test if_short_circuit_and::tests::test_short_circuit_and_both_true ... ok
test short_circuit_and::tests::test_short_circuit_and_both_true ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/main.rs (target/llvm-cov-target/debug/deps/exper_code_coverage-c502fcb0cc109ca3)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running tests/cli.rs (target/llvm-cov-target/debug/deps/cli-55e882f44094d43e)

running 1 test
test test_no_params ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Filename                      Regions    Missed Regions     Cover   Functions  Missed Functions  Executed       Lines      Missed Lines     Cover    Branches   Missed Branches     Cover
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
if_short_circuit_and.rs             7                 1    85.71%           3                 0   100.00%           9                 1    88.89%           0                 0         -
lib.rs                              1                 0   100.00%           1                 0   100.00%           1                 0   100.00%           0                 0         -
main.rs                             2                 0   100.00%           2                 0   100.00%           4                 0   100.00%           0                 0         -
short_circuit_and.rs                6                 0   100.00%           3                 0   100.00%           7                 0   100.00%           0                 0         -
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TOTAL                              16                 1    93.75%           9                 0   100.00%          21                 1    95.24%           0                 0         -

[winksaville]

I've now dug a little deeper and used cargo asm to look at the generated code. It seems build in debug mode the code for if_short_circuit_and() and short_circuit_and() are basically the same code. And in release mode they are actually the same code, see details below.

Based on this I conclude that this example provides an indication that "branch coverage" should be an improvement.

Details

Here is the asm code for if_short_circuit_and():

wink@3900x 22-08-15T19:52:28.139Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo asm --build-type debug --asm-style=att exper_code_coverage::if_short_circuit_and::if_short_circuit_and
exper_code_coverage::if_short_circuit_and::if_short_circuit_and (src/if_short_circuit_and.rs:1):
 subq    $28, %rsp
 movl    %edx, (%rsp)
 movl    %ecx, 4(%rsp)
 movl    %edi, 12(%rsp)
 movl    %esi, 16(%rsp)
 movl    %edx, 20(%rsp)
 movl    %ecx, 24(%rsp)
 cmpl    %esi, %edi
 jl      .LBB0_2
 movb    $0, 11(%rsp)
 jmp     .LBB0_3
.LBB0_2:
 movl    (%rsp), %eax
 movl    4(%rsp), %ecx
 cmpl    %ecx, %eax
 setl    %al
 andb    $1, %al
 movb    %al, 11(%rsp)
.LBB0_3:
 movb    11(%rsp), %al
 andb    $1, %al
 movzbl  %al, %eax
 addq    $28, %rsp
 retq

And here it is for short_circuit_and():

wink@3900x 22-08-15T19:52:32.960Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo asm --build-type debug --asm-style=att exper_code_coverage::short_circuit_and::short_circuit_and
exper_code_coverage::short_circuit_and::short_circuit_and (src/short_circuit_and.rs:1):
 subq    $28, %rsp
 movl    %edx, (%rsp)
 movl    %ecx, 4(%rsp)
 movl    %edi, 12(%rsp)
 movl    %esi, 16(%rsp)
 movl    %edx, 20(%rsp)
 movl    %ecx, 24(%rsp)
 cmpl    %esi, %edi
 jl      .LBB1_2
 movb    $0, 11(%rsp)
 jmp     .LBB1_3
.LBB1_2:
 movl    (%rsp), %eax
 movl    4(%rsp), %ecx
 cmpl    %ecx, %eax
 setl    %al
 andb    $1, %al
 movb    %al, 11(%rsp)
.LBB1_3:
 movb    11(%rsp), %al
 andb    $1, %al
 movzbl  %al, %eax
 addq    $28, %rsp
 retq

I piped these to .s files and the only differences are the labels:

wink@3900x 22-08-15T19:53:58.046Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ diff *.s
1c1
< exper_code_coverage::if_short_circuit_and::if_short_circuit_and (src/if_short_circuit_and.rs:1):
---
> exper_code_coverage::short_circuit_and::short_circuit_and (src/short_circuit_and.rs:1):
10c10
<  jl      .LBB0_2
---
>  jl      .LBB1_2
12,13c12,13
<  jmp     .LBB0_3
< .LBB0_2:
---
>  jmp     .LBB1_3
> .LBB1_2:
20c20
< .LBB0_3:
---
> .LBB1_3:

I then created the release version and if_short_circuit_and() is not mentioned as being generated, we only see short_circuit_and():

wink@3900x 22-08-15T20:01:27.012Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo clean
wink@3900x 22-08-15T20:01:29.623Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cargo asm --build-type release --asm-style=att
core::ops::function::FnOnce::call_once{{vtable.shim}}
core::ptr::drop_in_place<std::rt::lang_start<()>::{{closure}}>
exper_code_coverage::main
exper_code_coverage::short_circuit_and::short_circuit_and
std::rt::lang_start
std::rt::lang_start::{{closure}}
std::sys_common::backtrace::__rust_begin_short_backtrace

Wondering what happened to it, I looked at the generated code and there are two .s files and short_circuit_and() is in target/release/deps/exper_code_coverage-865a6210cdb565bc.s. Looking at that code we find that at line 21 if_short_circuit_and is "set" to short_circuit_and. So the code if_short_circuit_and() has been optimized away:

$ fd --glob '*.s' target
target/release/deps/exper_code_coverage-865a6210cdb565bc.s
target/release/deps/exper_code_coverage-c551574da956536f.s
wink@3900x 22-08-15T20:02:02.209Z:~/prgs/rust/myrepos/exper-code-coverage (main)
$ cat -n target/release/deps/exper_code_coverage-865a6210cdb565bc.s
     1          .text
     2          .file   "exper_code_coverage.210b8923-cgu.0"
     3          .section        .text._ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E,"ax",@progbits
     4          .globl  _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E
     5          .p2align        4, 0x90
     6          .type   _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E,@function
     7  _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E:
     8          .cfi_startproc
     9          cmpl    %esi, %edi
    10          setl    %sil
    11          cmpl    %ecx, %edx
    12          setl    %al
    13          andb    %sil, %al
    14          retq
    15  .Lfunc_end0:
    16          .size   _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E, .Lfunc_end0-_ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E
    17          .cfi_endproc
    18
    19          .globl  _ZN19exper_code_coverage20if_short_circuit_and20if_short_circuit_and17h996a8c765e790e2dE
    20          .type   _ZN19exper_code_coverage20if_short_circuit_and20if_short_circuit_and17h996a8c765e790e2dE,@function
    21  .set _ZN19exper_code_coverage20if_short_circuit_and20if_short_circuit_and17h996a8c765e790e2dE, _ZN19exper_code_coverage17short_circuit_and17short_circuit_and17h626fd720e3a99931E
    22          .section        ".note.GNU-stack","",@progbits

[Zalathar]

A few months ago I looked into working on this, but I found it a bit tricky to fit branch coverage handling into the existing code, which is why I focused my attention on refactoring the existing coverage code instead.

When my current work on rust-lang/compiler-team#645 eventually gets approved and merged, hopefully that will make it a bit easier to incorporate things like branch regions.

[Zalathar]

One of the questions that will need to be answered when implementing this is whether branch coverage regions should be identified using heuristics during MIR analysis (which is how existing coverage regions are identified), or identified during HIR-to-MIR lowering (with access to precise information about original syntax forms like if/&&/||).

Identifying branches during HIR-to-MIR lowering should give more accurate results, and should be more straightforward and maintainable in the long run. But it would also require additional up-front effort to figure out how to add partial coverage analysis during lowering, transmit its conclusions through to the MIR analysis, and have that analysis take them into account.

[Zalathar]

As #116046 gets closer to being a reality, I've been thinking more about possible implementation strategies for branch coverage.

From the time I've spent looking at the existing coverage code, I strongly suspect that it's not possible to reach an acceptable implementation of branch coverage through MIR analysis alone. Trying to reverse-engineer if/then/else arms from MIR SwitchInt nodes is going to be hacky at best, and is made much harder by the possibility of micro-optimizations introduced during the AST-HIR-THIR-MIR lowering process (e.g. #111752).

So the approach I'm currently thinking about (but haven't yet tested) is as follows:

• Introduce something like StatementKind::BranchMarker { id: coverage::BranchId, arm: bool }
• During THIR-MIR lowering, when lowering an If expression, generate a fresh BranchId and then inject branch markers into the then and else arms, with the source span of the if condition
• In the InstrumentCoverage MIR pass, detect matching pairs of branch markers (along with their enclosing BCBs), and create a branch mapping with the source span of the condition, and appropriate BCB counters for the true/false arms
• Branch markers become meaningless after instrumentation; we can leave them as-is (and have codegen ignore them as no-ops), or possibly replace them with their BCB's counter/expression statement (to avoid having to shift over the whole statement list when prepending)

[Swatinem]

I agree that introducing branch markers during (T)HIR lowering gives us the most control over what exact expressions are being considered, and their precise source spans.

[Jugst3r]

Hello @Zalathar,
We were interesting on working on branch coverage, with the end-goal of integrating MC/DC coverage in the Rust compiler, for which support has recently been merged into LLVM. Branch coverage looks like a good starting point for us to garner expertise in the coverage implementation in the Rust compiler. MC/DC coverage will also require information that branch coverage needs as well (such as, what is a decision, which is what you mentionned in your above message).

I saw that you recently pushed a lot of refactorings, to prepare the integration of branch coverage in the compiler I suppose? Do you have a time frame in mind? Do you already have patches regarding branch coverage? We would obviously be interested in collaborating

[evodius96]

Thanks for the information and the link to the MR. We will be checking this out and use it as a basis to look into MC/DC. We will make sure to have the limitations you mentionned in mind

@Jugst3r I upstreamed MC/DC support (and branch coverage) into Clang/LLVM and would love to be in the loop on this (and it's already being extended and improved). I'm not an expert on Rust, but I definitely want to follow what y'all are doing. That's great to hear there is interest in MC/DC. Please let me know if you have any questions.

[Jugst3r]

Sure @evodius96, we will definitely let you know of how our experiments go. I have tracked the LLVM work and I am aware of some of the improvements (notably the one lifting the 6 condition limits for MC/DC), but only discovered yesterday about the nice work @Zalathar did.

To give you more context, I mainly have expertise on coverage (as I work on a tool that does coverage for Ada and C/C++ code that supports up to the MC/DC level and that is called gnatcoverage), but very little on the Rust compiler. The MC/DC implementation in GNATcoverage is robust, and has been used for many years by the customers. I can give input regarding the implementation of MC/DC in GNATcoverage if you need any by the way

Imo, we also have better support when it comes to coverage reporting and source code obligations inside macro expansion in comparison to clang, but it would probably be more appropriate to discuss elsewhere.

[Ax9DTW]

@Jugst3r @evodius96
We've been making some progress on adding MC/DC to rustc based on @Zalathar's branch coverage PR. Currently we are working on an approach where we've been able to emit the MC/DC intrinsics during codegen by identifying decisions and conditions from THIR, similar to the approach found in the clang frontend.

We'd be happy to collaborate and share more details and help in accelerating the effort for bringing MC/DC to Rust.

[Jugst3r]

Hi @Ax9DTW. I would be happy to have a look at it. Do you have a draft PR or a repository for the implementation?

IIUC, the primary difference between MC/DC coverage and branch coverage is the ability to identify decision as a whole. It is interesting as branch coverage needs to identify decisions, to make branch regions, but it does not need to preserve the whole decision valuation, which you need for MC/DC. So I suppose that requires some more metadata information to be added, similar to the branch markers that @Zalathar implemented?

[Zalathar]

Branch coverage instrumentation has landed in #122322, and should be available in the next nightly.

It can be enabled by including both -Cinstrument-coverage and -Zcoverage-options=branch in your compiler flags.

You might also need to run llvm-cov with --show-branches=count to have it actually show branch information inline with your code.

The current implementation supports conditions in if and while expressions, in match guards, and inside && and || expressions. There is currently no branch instrumentation for if let or for individual match arms.

[ZhuUx]

@Ax9DTW @Jugst3r
I have drafted an implementation for mcdc at #123409. Any suggestions are welcome.

For now it only checks if statements (if in hir, including while), I'm not very professional on mcdc. Is it necessary to apply it to all logical expressions?

[Jugst3r]

@Ax9DTW @Jugst3r I have drafted an implementation for mcdc at #123409. Any suggestions are welcome.

For now it only checks if statements (if in hir, including while), I'm not very professional on mcdc. Is it necessary to apply it to all logical expressions?

@ZhuUx Thanks for sharing! For your information, I work with @RenjiSann at AdaCore so I was aware of your work. For your information, GNATcoverage that is used in certification contexts applies MC/DC to all complex boolean logical expressions in additional to boolean expressions that are controlling of a control flow structure. By complex, I mean logical boolean expressions with a binary and / or operator.

[ZhuUx]

Found something confusing about the behavior of branch coverage to plain logical expression.

Here is the code

#![feature(coverage_attribute)]

fn bar(a: bool, b: bool) {
    let x = a || b;
    println!("evaluated {}", x);
}

#[coverage(off)]
fn main() {
    bar(true, false);
    bar(false, false);
}

The current implementation reports coverage of a but not of b. This is because b is assigned to x directly (thus do not call then_else_break) when mir builder touches rhs of a || b.
Is it expected?

[Zalathar]

The current implementation reports coverage of a but not of b. This is because b is assigned to x directly (thus do not call then_else_break) when mir builder touches rhs of a || b.
Is it expected?

Yes, this is the expected behaviour for branch coverage.

In this example, a is a branch condition, because its value determines whether b is evaluated or not.

But b is not a branch condition, because it is just evaluated to a value, and doesn't directly participate in any control-flow decisions.

[Lambdaris]

But b is not a branch condition, because it is just evaluated to a value, and doesn't directly participate in any control-flow decisions.

This might lead to something a bit weird.
Say

fn direct(a: bool, b: bool) {
    if a || b {
        println!("pass");
    }
}

fn indirect(a: bool, b: bool) {
    let v = a || b;
    if v {
        println!("pass");
    }
}

fn main() {
    direct(true, false);
    direct(false, false);

    indirect(true, false);
    indirect(false, false);
}

Current implementation reports 100% branch coverage for indirect but not for direct.
Someone might type the indirect style code to escape coverage gate checks.

Clang adopts the way where both a and b are taken as branches in let v = a || b. @evodius96 Is there any considerations?

[nitnelave]

It seems to me that direct should be entirely covered, for the same reason that indirect is: b was both evaluated and not, and the if was both taken and not.

[Jugst3r]

I think that both should be considered as branches, or at least considered as conditions in MC/DC. IIUC MC/DC is implemented on top of branch coverage, so if we consider them as conditions in MC/DC terminology but not as branches, it will introduce a divergence between the implementation of branch coverage vs MC/DC coverage which is not desirable in my opinion

[RenjiSann]

It seems to me that direct should be entirely covered, for the same reason that indirect is: b was both evaluated and not, and the if was both taken and not.

b was not evaluated to false, meaning that in the Control Flow Graph, we never take the branch where b is false.
That's why we don't get 100% branch coverage on the expression.

Regarding the behavior in the indirect case, I think even though b is not a "branch" in terms of MIR/CFG/assembly, considering it as one may be the more useful alternative. My guess is that people are more interested in considering the whole expression like if a || b { true } else { false } , rather than a kind of syntactic sugar for if a { b } else { false }.

Furthermore, MCDC coverage, which is based on branch coverage, is defined by certification standards, and their stance on this subject is that a || b shall be considered as a 2-operand expression, no matter if the context is a control flow structure or a variable assignation.

Finally, I add that when replicating this with C++ and Clang, indirect and direct both have the same behavior (like @Lambdaris said) : a and b are both considered branches, and b is not covered. So if we want to be consistent with clang (which I think we should for this case), we may consider b as a branch and not as an assigned value.

[Zalathar]

Remember that branch coverage isn't just a building-block for MC/DC, and it isn't only for people writing certified software.

I agree that tracking whether b takes both possible values is a useful behaviour that ideally should be available somewhere. (Perhaps as part of MC/DC, or perhaps as a separate option on top of branch coverage, or perhaps something else.)

But I'm not convinced that it should simply occur by default when branch coverage is enabled.

[Zalathar]

I'm surprised to hear that clang treats a || b as two branches. I assume that in doing so, it inserts a synthetic control-flow branch on b so that the underlying counters are updated appropriately?

[evodius96]

I'm surprised to hear that clang treats a || b as two branches. I assume that in doing so, it inserts a synthetic control-flow branch on b so that the underlying counters are updated appropriately?

Effectively, this is true for clang -- the goal was to provide a consistent metric for all conditions in an expression in the source code, though technically you're correct that condition b in this case would not result in a branch. This also aligns to what I've seen other vendors show (e.g. LDRA, LCOV).

(Actually for clang, a synthetic control-flow branch is inserted for the last condition on all boolean expressions in order to ensure a final count, even though this is obviously not necessary, given that, for example, in an if-stmt, we can instead use the counter measuring the then block. I anticipated that this can be better optimized in a later clang patch.

[eirnym]

I don't see contradiction in the expression a || b how counting work/doesn't work as I see this simple expression in a more complex implementation (imaginary, as I don't know actual internals of rust and clang to advise or anything):

• When a or b are constants, we know the result on compile time. Thus there would be no branching => no real coverage. Example: a || true
• When a AND b are variables it's faster to calculate the result rather than doing if-branching. Example: let c = a || b;
• When a is an expression and b is a variable as we know a value of a at the end of calculation as variable value (could be stored in a register) we can return to a case when both a and b are variables, instead of branching. Example: let c = (t == 0) || b
• Otherwise branching is required. Example: let c = (t == 0) || (d == 5).

Based on this, I take line "in boolean expression second argument won't be calculated if first is true" with a grain of salt as a mind shortcut.

Thus, I don't expect counting to work the same way in every single situation, as situations are actually different even visually they're the same.

PS: braces added for clarity.

[ZhuUx]

The instrument behavior for branches containing | patterns may worth to discuss. It makes a difference on branch coverage as well as mcdc.

The question is: how to determine false branches in pattern Opt::A | Opt::B ? This pattern can be tested in a single basic block with terminator in the form of switchInt(move _dis) -> [0: bb2, 1: bb3, otherwise: bb1] with current rustc. Suppose bb2 is the branch for matching Opt::A, bb3 is for matching Opt::B and bb1 is for matching neither.

1. The first view is that take it as is(Opt::A) || is(Opt::B). Thus the false branch of is(Opt::A) should contain the true branch of is(Opt::B). That says, the false count of Opt::A shall be sum of execution number of bb3 and bb1, while false count of Opt::B is just the execution number of bb1.

The first opinion might be intuitive. However, one can argue that there is a key difference between or patterns and boolean or expressions: when we write a || b, a and b can both are right, while only at most one of matching A and B can be true in pattern A | B. As a result, we can say A | B is equivalent to B | A but undoubtedly b || a is not same as a || b. This view shows its contradiction on generating different reports for expressions meaning exactly the same.

2. As an opposition, the second proposal assigns Opt::A and Opt::B symmetric positions: false count of Opt::A is execution number of bb3 plus that of bb1, while false count of Opt::B is sum of execution number of bb2 and bb1. By this way we can keep consistency with commutativity and associativity of or patterns (what a pity this is not an abelian group due to the lack of an identity element 😔) but users may feel confused at first sight. Besides, if we adopt this view we also need to discuss how to determine the false next of Opt::A and Opt::B in mcdc.
3. The third proposal modifies the second a bit: false count of Opt::A and Opt::B both only count execution number of bb1, thus matching Opt::A does not mean false of Opt::B and vice versa. Someone might like this because in this way test case foo(Opt::A) gives result Opt::A: true count 1, false count 0; Opt::B: true count 0, false count 0 where Opt::B is irrelevant.

For now I have implemented the first proposal at #124278 but tend to the second in mcdc. And normal branch coverage may need to consider this too so I present it here to collect some advice or other views.

[Zalathar]

For branch coverage (or at least the basic level of branch coverage), my current thinking is that Opt::A | Opt::B should have one combined true branch, and one combined false branch, with no way to count the occurrences of A vs B.

Of course, that wouldn't be appropriate for MC/DC coverage (or a more detailed level of branch coverage), where users would probably need more detail in order to satisfy their testing/documentation requirements.

I vaguely remember hearing that someone had been doing some work on defining precisely what MC/DC should mean in the context of Rust (with things like pattern-matching and or-patterns), but I don't have any of the details at hand.

[pietroalbini]

@ZhuUx: However, one can argue that there is a key difference between or patterns and boolean or expressions: when we write a || b, a and b can both are right, while only at most one of matching A and B can be true in pattern A | B. As a result, we can say A | B is equivalent to B | A but undoubtedly b || a is not same as a || b. This view shows its contradiction on generating different reports for expressions meaning exactly the same.

I agree here, we shouldn't treat or patterns like short-circuiting boolean expressions. The way I'd see them is like two separate decisions to reach the same branch.

@ZhuUx: For now I have implemented the first proposal at #124278 but tend to the second in mcdc. And normal branch coverage may need to consider this too so I present it here to collect some advice or other views.

@Zalathar: For branch coverage (or at least the basic level of branch coverage), my current thinking is that Opt::A | Opt::B should have one combined true branch, and one combined false branch, with no way to count the occurrences of A vs B.

I think for branch coverage @Zalathar's approach is the best, while for MC/DC I'd go with @ZhuUx's second proposal.

@Zalathar: I vaguely remember hearing that someone had been doing some work on defining precisely what MC/DC should mean in the context of Rust (with things like pattern-matching and or-patterns), but I don't have any of the details at hand.

We (Ferrous Systems) wrote that paper with DLR. It's still not published (we're submitting it to an academic conference), but if you need a copy of the pre-print for the implementation of branch or MC/DC coverage reach out at [email protected] and I'll happily send you a copy!

[ZhuUx]

@evodius96
Would have a question need to be verified. Does the assignment of condition id shall keep with some order?
Found that for code like

fn foo(a: bool, b: bool) {
    if a && b {
        // ...
    }
}

fn main() {
    foo(true, false)
}

If the condition id of a is 2 while the id of b is 1, llvm panics with Assertion !TestVectors[Idx].empty() && "Test Vector doesn't exist." failed.
It is not problem for normal two way branch. Only for pattern matching in rust we get such assignment due to the special evaluating order (very likely not to be same with boolean expressions). I guess the condition specified with id 1 must be the first condition to be evaluated? Or are there any other constrictions?

[evodius96]

@evodius96 Would have a question need to be verified. Does the assignment of condition id shall keep with some order?

For MC/DC, the order doesn't matter, but the order has to be consistent such that once a node gets an ID, it doesn't change. During llvm-cov visualization, where the conditions are counted according to their left-to-right ordinal position, a mapping is maintained to track a condition's ordinal position and the ID it has.

In clang, the ID is assigned by the node visitor during a recursive AST walk (See struct MCDCCoverageBuilder in CoverageMappingGen.cpp). Here, an ID is simply an ID and doesn't represent a meaningful order. This is the ID that gets encoded into the branch region (allowing llvm-cov to reconstruct the control flow and thereby the possible test vectors), and it's also used during instrumentation as the condition index into the condition bitmap, indicating conditions that evaluate to TRUE. This is used to calculate the indices of all actual executed test vectors.

The TestVectors[Idx] you see in the assertion is a vector of all possible TestVectors. As you can surmise, the assertion fails if llvm-cov sees an executed test vector that doesn't match one of the possible test vectors it knows. So either the global bitmap (indicated executed test vectors) is wrong (most likely), which points to a bug in instrumentation, or the calculated set of possible test vectors is wrong, indicating a bug in the branch region encoding used for MC/DC.

[ZhuUx]

The TestVectors[Idx] you see in the assertion is a vector of all possible TestVectors. As you can surmise, the assertion fails if llvm-cov sees an executed test vector that doesn't match one of the possible test vectors it knows.

Ah Exactly that's what happened if the id of entry condition is not 1. Assertions fail at different locations between llvm 18 and 19.
In llvm 18, the function MCDCRecordProcessor::buildTestVector (in CoverageMapping.cpp) looks like:

  void buildTestVector(MCDCRecord::TestVector &TV, unsigned ID = 1) {
    shouldCopyOffTestVectorForTruePath(TV, ID);
    shouldCopyOffTestVectorForFalsePath(TV, ID);

    // Reset back to DontCare.
    TV[ID - 1] = MCDCRecord::MCDC_DontCare;
  }

It constructs all possible test vectors and is called first at processMCDCRecord() with default ID. Thus once the id of a was 2 and the id of b was 1, this function checked b at start and found that it has no next (on such occasion mapping of a was {id: 2, true_next: 1, false_next: 0}, and that of b was {id: 1, true_next: 0, false_next: 0}). As a result, only [T, -] and [F, -] for [b, a] are recorded in TestVectors, though the executed vector may be [F, T].

As for llvm 19, llvm-cov would panic at assert(Nodes[0].InCount == 0) in mcdc::TVIdxBuilder::TVIdxBuilder. This again because Node[0], which represents entry (or top) node in the decision tree and shall not have any "parent" nodes, comes from the condition with ID 1 and is successor of Node[1] in the example function.

Hence there is an implicit rule suggested by implementation that the entry condition of decision should be fixed with condition id 1. I think this is relatively fair so we (or any other compilers implementing mcdc based on llvm) would better respect it. At least it is not difficult for rust to find a way to regulate the condition id assignment of pattern matching.