Implement LLVM-compatible source-based code coverage

[richkadel]

What is this issue?

This is a major change proposal, which means a proposal to make a notable change to the compiler -- one that either alters the architecture of some component, affects a lot of people, or makes a small but noticeable public change (e.g., adding a compiler flag). You can read more about the MCP process on https://forge.rust-lang.org/.

This issue is not meant to be used for technical discussion. There is a Zulip stream for that. Use this issue to leave procedural comments, such as volunteering to review, indicating that you second the proposal (or third, etc), or raising a concern that you would like to be addressed.

MCP Checklist

• Fill out and file this issue. The @rust-lang/wg-prioritization group will add this to the triage meeting agenda so folks see it.
• Create a Zulip topic in the stream #t-compiler/major changes with the name XXX compiler-team#NNN, where XXX is the title of this issue and NNN is whatever issue number gets assigned. Discuss the MCP in there, and feel free to update the proposal as needed.
• Find a reviewer, and add their name to this comment (see the section below).
• Find a second, someone who is knowledgeable of the area and approves of the design, and have them leave a comment on the issue.
• Announce this proposal at the triage meeting (ping @rust-lang/wg-prioritization to have them add it to the agenda). All edits should be done before you do this.
• After one week, assuming no unresolved concerns, the MCP is accepted! (We sometimes skip this week period if it seems unnecessary.) Add the mcp-accepted label and close the issue; we can link to it for future reference.

TL;DR

Implement LLVM-compatible source-based code coverage for Rust.

Links and Details

Core Requirements

1. Instrument Rust crates by injecting additional runtime code to:

   • Count each executed branch of code ("coverage region"); for example, function blocks, loop iterations, if and else blocks, and match arms.
   • Report the counter totals (typically at program exit) in LLVM "raw profile format", compatible with the llvm-profdata tool.
     • NOTE: The raw profile format is not standardized, and can vary depending on the LLVM compiler version. Therefore, the Rust implementation must use LLVM Intrinsics to count and report coverage. The llvm-profdata tool is used to interpret the LLVM raw profile data from a given LLVM version.

2. Generate a coverage map in LLVM Code Coverage Mapping Format that uniquely identifies counted coverage regions (source code spans) corresponding to the injected runtime counters.

With these requirements satisfied, LLVM coverage analysis tools, and some LLVM-supported GCC coverage analysis tools (as supported by existing compatibility features in LLVM tooling), should support coverage analysis of Rust program source code.

IMPORTANT: The LLVM coverage tooling can potentially support Profile Guided Optimization (PGO). Rust already has an option for compiling with PGO (rustc -Cprofile-generate=/tmp/pgo-data). This MCP is focused on source-based code coverage. Every effort will be made to accommodate future support for additional PGO extensions, potentially enabled by coverage instrumentation, but this MCP emphasizes a design optimized for source-based code coverage only.

Approach and Notional Design

The following sections describe a high level design, and a stepwise approach to assess and implement LLVM code coverage for Rust. (Some of these steps are already in progress, including prototype implementation code.) This plan is open to change as a result of improved understanding of the rustc and LLVM architectures, and insights from reviewers.

Identify Rust Code Patterns for Code Regions and Counters

One of the primary use cases for source-based code coverage is to visually highlight the code regions executed by a program, separated by branch decision points. Regardless of how the code is instrumented, the final result must be verified against the source code, for all branch types supported by the Rust syntax, to ensure the coverage regions (start and end character positions in a source file) are consistent with the programmer's interpretation of the Rust code structure.

An analysis of the Rust Abstract Syntax Tree (AST) and its AST node types will help establish a baseline for validating the instrumentation. (This does not imply the instrumentation must be done in the AST.)

1. Review all AST node types relevant to Coverage analysis (such as Item::Fn, Expr, Stmt, and Block; defined in src/librustc_ast/ast.rs) and create sample Rust programs with contrived examples of Rust language patterns that create conditional branching. Here is a snippet from one such analysis. The comments on the left roughly sketch a graphical representation of the branching. The colors were added only to this snippet, to further illustrate the separate coverage regions.

2. Confirm coverage regions and instrumentation points using an experimental counter function (such as __incr_cov() below) to validate an approach for each syntax test case. Note that counts for some coverage regions can be computed, using LLVM's Counter Expressions.

/// Experimental only. Actual generated code will inject the `llvm.instrprof.increment()`
/// intrinsic directly, without a separate wrapper function.
pub fn __incr_cov<T>(/*counter args,...*/ result: T) -> T {
    __internal_llvm_intrinsic_increment_placeholder(/*counter args,...*/);
    result
}

Identify Coverage Regions, and Inject Placeholder Counters

1. Inject calls to increment coverage counters by injecting a call to llvm-instrprof-increment. There are differing opinions as to where coverage regions should be identified, and where to inject the counters (as discussed in the original Issue, the initial Pull Request, and the Zulip thread associated with this MCP).

   • An experienced compiler team member has recommended performing coverage region identification and instrumentation directly on the MIR, in a "MIR->MIR" pass. Some benefits of this approach include: (a) coverage support should not be affected by changes to the Rust language syntax; (b) instrumentation might be simpler if coverage regions can be accurately identified based on MIR data alone, which has far fewer variants compared to AST constructs; and (c) compiler performance should be faster than other approaches, since the coverage code is injected at or near the final compiler pass. Given the strong recommendation, and the benefits, the MIR->MIR approach is the current plan, but must still be proven.
   • If the MIR->MIR approach is not viable, fallback options include: (a) implementing a rustc_ast::mut_visit::MutVisitor after AST expansion (before resolver.resolve_crate()) to walk the AST and inject the counter statements (this has already been implemented in a functional, but limited prototype), (b) injecting additional instrumentation nodes while lowering the AST to HIR (some prototyping has been done here, and the existing pattern with expr_drop_temps() for injecting a placeholder, to be converted to generated IR code at a latter stage, is worth considering in this case); (c) or injecting coverage during "HIR->MIR" conversion (discussed but not yet attempted).

2. Save a map from each injected counter to the source code start and end character representing the coverage region (represented by the existing rustc type, Span).

3. Implement an experimental rustc command line option to enable code coverage by crate.

Add llvm-instrprof-increment Support to Existing Rust Compiler Runtime

1. Implement the changes required to introduce the llvm-instrprof-increment call for coverage counters. (It may be possible to inject the intrinsic in the MIR without explicitly defining as an extern function.) If required:

   • Add pub fn instrprof_increment to the extern “rust-intrinsic” section in libcore.
   • Add support for instrprof_increment to codegen_intrinsic_call() in librustc_codegen_llvm/intrinsic.rs.

2. Update any other required build configuration dependencies, flags, documentation, and tests, as demonstrated by similar examples.

Update llvm-instrprof-increment temporary arguments

1. Locate the best stage for replacing all temporary arguments to llvm-instrprof-increment with the corrected values.

2. Identify and/or insert each instrumented function's mangled function name by global/static pointer. Use the librustc_symbol_mangling library to compute the mangled function name, as needed). This process must take place after monomorphization of generic types, so the mangled function name can be generated for each monomorphized version of the function. (Note that, by taking this proposed approach, coverage will be counted separately for each reified permutation of type parameters, even though the end result may be the sum of these counts. This seems to align well with the existing “v0” implementation of function name mangling, and instrumenting each type variant separately may have other benefits for source code coverage analysis and profiling.)

3. Update the num_counters argument with the total number of injected counters per function.

4. Generate the hash argument (from the MIR, HIR, or AST, to be determined) that identifies whether a function has changed enough to invalidate a past coverage analysis. Also called the "function's structural hash", this is a hash value that can be used by the consumer of the profile data to detect changes to the instrumented source. (Comments and whitespace should be excluded of course, but other criteria can be included or excluded. Clang, for instance, bases its hash on the overall control flow.)

Generate the Coverage Map

1. Review the LLVM Code Coverage Mapping Format documentation and example implementations, such as from Clang](https://clang.llvm.org/doxygen/CoverageMappingGen_8cpp_source.html) and Swift.

2. Using the mapping from injected counters to coverage spans, and the additional details for each counter (mangled function name, function hash, num_counters), embed the coverage mapping into the LLVM IR.

3. Unless there are major objections, leverage the LLVM CoverageMappingWriter (C++) to generate and emit the coverage map.

Tests and Documentation

1. Implement Unit and End-to-End Integration Tests, following existing examples.

   • Tests will validate the emitted LLVM IR and coverage map.
   • Validate coverage assumptions, for example, to confirm that no code region can be counted more than once for the same execution.
   • Add benchmarks to rustc-perf to identify and address any hot spots.

2. Update user and developer documentation as needed.

Optimization

Explore opportunities for optimizing the initial implementation of code coverage.

GitHub Artifacts

Relevant issue: #34701 - Implement support for LLVMs code coverage instrumentation
Experimental prototype PR and discussion: #70680 - WIP toward LLVM Code Coverage for Rust

LLVM Source-based Code Coverage

• User Tutorial (C++ example)
• LLVM Coverage Mapping Format
• llvm.instrprof.increment intrinsic - Increments code counters at runtime
• llvm-profdata command - Profile data tool
• llvm-cov command - Emit coverage information

Mentors or Reviewers

• Recommendations and reviews from any Rust compiler team member would be greatly appreciated. Tyler Mandry (tmandry) is a current compiler contributor, and a coworker of mine, and has offered to review and advise on this project.
• Bob Wilson (bob-wilson) has also offered to review and advise (and possibly lend a hand in the implementation). Bob brings experience as a developer of the LLVM source-based code coverage implementation for Clang.
• Additional LLVM and Rust expertise from within the Google Fuchsia team is also available for reviews and guidance.

[richkadel]

@tmandry @bob-wilson

[richkadel]

@tmandry @bob-wilson

Tyler, Bob,

Please review this submitted version of the MCP and note your approval, if I've captured all of your major comments.

Thanks!
Rich

[tmandry]

Looks good to me! I reviewed this before @richkadel posted it and he's incorporated my initial feedback. I'd also like to volunteer as a reviewer for this MCP.

[richkadel]

Zulip topic: https://rust-lang.zulipchat.com/#narrow/stream/233931-t-compiler.2Fmajor-changes/topic/Implement.20LLVM-compatible.20source-based.20cod.20compiler-team.23278

[richkadel]

@pnkfelix - For checklist item 4, does the "second" need to come from the Rust compiler team or is @bob-wilson a reasonable candidate since he has experience implementing LLVM coverage in Clang?

(If compiler team, please recommend someone, if not yourself. Thanks!)

[bob-wilson]

I'm really glad to see this moving forward and I think this plan will work. The end goals sound exactly right to me. The approach is a bit more experimental than I would personally choose to take, but maybe I'm biased to go straight to the approach used in Clang and Swift. I'm not too worried about that, though. As long as it ends up with a good design, some early experimentation can't hurt.

[richkadel]

@rust-lang/wg-prioritization please add this proposal to the triage meeting agenda if there are no pending comments. Thanks!

[richkadel]

@pnkfelix @Centril - The mention "@rust-lang/wg-prioritization" above is not in bold text, like mentioning usernames. I'm not sure this actually "pings" the group (per the checklist instructions). Am I supposed to "ping" in some other way? (I added a comment to the document on MCP process regarding this confusion as well.)

[pnkfelix]

@richkadel thanks for the heads up.

You do not need to worry about whether this proposal will get added to the agenda; the rustbot added the to-announce label to it, and part of the protocol for @rust-lang/wg-prioritization is to add every to-announce issue from this repository to the agenda each week.

[pnkfelix]

(i have not yet resolved why @richkadel 's attempts to reference @rust-lang/wg-prioritization do not end up as proper references to that wg's github identity.)

[richkadel]

FYI, I get a 404 page when I click on the highlighted link to wg-prioritization in your comment. It doesn't appear to be visible to me.

[shepmaster]

attempts to reference

IIRC, you must be a member of a group to at-mention it (to avoid abuse).