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).

[pnkfelix]

@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!)

(I do think the "second" is meant to come from the compiler team. The intent there, if I remember correctly, is to ensure that we have at least one person on the compiler team who is more than merely lukewarm about a proposed feature.)

[richkadel]

Thanks for the clarification @pnkfelix ! I removed the check.

Can you recommend someone to be a "second" (if not yourself)?

[richkadel]

@wesleywiser - Thanks so much for ❤️-ing the MCP!

Would you be willing to confirm the MCP is worthwhile pursuing, and allow me to count you as the "second" (checkbox 4 at the top)?

Thanks for considering!

[wesleywiser]

Hi @richkadel!

I'm really excited to see this proposal move forward! I've used code coverage tools in other languages before and the value you can get from high-quality implementations is really quite large. However, I'm not very familiar with the frontend part of rustc so I don't feel qualified to second this proposal.

My bad for not reading the *bold text* at the top of the issue

If you don't mind, I do have a few questions from a detailed reading of your proposal, the PR and the related issues:

• Since the llvm-profdata tool is tied to the LLVM version, how do we expect users to obtain that tool? Will they be required to build our LLVM fork or will the tool be available via rustup? I think, as this is an unstable compiler flag, pretty much any answer is fine but we should have some plan for stabilizing this flag.

• Introducing so many calls to the __incr_cov function will create a lot of additional control flow edges (and a lot more MIR). It seems like this could lead to a lot of additional work done during compile time. Does clang take a similar approach? What impact does that typically have on their compilation time? How is the compilation performance of the existing prototype you have? Do you have any thoughts about whether this hits an "acceptable" bar for compiler performance?

• Like many others on the PR and linked issues, my initial thought was that this would be a MIR pass. Having used poor quality tools in the past, I certainly agree with @bob-wilson's points regarding the quality of the code coverage reporting being critical to this feature. Still, my gut says that this should be done at least at the HIR level. I think I'm worried that by basing this pass on the AST, it will break much more frequently as the AST is changed than if it was based on a lower-level construct like the HIR. Do you have thoughts about what could be done to minimize regressions in the code coverage due to changes in the AST, for example, when adding new syntax?

• It sounds like you implemented two prototypes, one based on MIR transforms and one on the AST approach. Did you find issues regarding the quality of code coverage information generated from the MIR pass that the AST approach fixed? Or was the primary issue the implementation complexity that you mentioned above?

Thanks @Mark-Simulacrum for the message.

@richkadel I've copied my questions to the Zulip thread 🙂

[Mark-Simulacrum]

Just as a note, it would be amazing to take the detailed technical discussion to the Zulip stream, and only post high level summaries here. The intent is to minimize traffic on this repository, so that compiler team members can reasonably subscribe without following the details of any given proposal, and then read the backscroll in Zulip as needed. Also, feel free to create dedicated topics in Zulip in the major changes stream, the primary one is just the starting point :)

[richkadel]

Hi @spastorino - Can you please clarify why you removed the to-announce label? This MCP is supposed to be announced at the triage meeting today.

[richkadel]

@Mark-Simulacrum - Thanks for highlighting that technical discussion goes to the zulip stream for this MCP (https://rust-lang.zulipchat.com/#narrow/stream/233931-t-compiler.2Fmajor-changes/topic/Implement.20LLVM-compatible.20source-based.20cod.20compiler-team.23278)

@wesleywiser - I'll paste each of your question/comments there and respond to them. Thanks!

[richkadel]

Hi @spastorino - Can you please clarify why you removed the to-announce label? This MCP is supposed to be announced at the triage meeting today.

Answering my own question:

It looks like this MCP was announced in today's weekly meeting (woohoo!):

https://rust-lang.zulipchat.com/#narrow/stream/131828-t-compiler/topic/weekly.20meeting.202020-04-30.20.2354818/near/195842729

I assume this starts the "1-week" clock, and await the "mcp-accepted" label.

Thankyou @wesleywiser for raising the need for the "second".

Process note (FYI @nikomatsakis ): I had hoped one outcome of the meeting and announcement would have been to resolve the issue of a need for a "second". (Should the compiler team have any obligation to follow up on requests for a reviewer or second?)

I would assume there is at least one person on the compiler team that is (to quote @pnkfelix ) "more than merely lukewarm" about enabling code coverage in Rust.

Please let me know if there is anything else that I should do to help wrap this up.

Thanks!
Rich

[tmandry]

There was some good feedback on the design in the Zulip topic. I think we should incorporate it and try to clear up any major concerns as best we can before diving in. In particular, I think we should have general agreement on (roughly) what stage the instrumentation pass should go in. (That said, experimental implementation work focused on answering this question would be productive and useful.)

I'm saying all this with the assumption that we do want source-level coverage support in rustc, given an agreeable design and implementation. This is based on a lot of the discussion in rust-lang/rust#34701 and especially our prior experience trying to implement coverage tooling using the current GCOV-based support. Though I realize now that there aren't a lot of current compiler team members that were involved in these discussions.

For anyone on t-compiler following along, do you already agree with this general statement, or are you unsure / lacking context? (Does anyone disagree?) The MCP can be doing more to explain the motivation, but it'd be nice to have an idea of where people stand right now.

[pnkfelix]

Hi @spastorino - Can you please clarify why you removed the to-announce label? This MCP is supposed to be announced at the triage meeting today.

Answering my own question:

It looks like this MCP was announced in today's weekly meeting (woohoo!):

https://rust-lang.zulipchat.com/#narrow/stream/131828-t-compiler/topic/weekly.20meeting.202020-04-30.20.2354818/near/195842729

I assume this starts the "1-week" clock, and await the "mcp-accepted" label.

Thankyou @wesleywiser for raising the need for the "second".

Just to be clear: Without a "second", I don't think the 1-week clock has started yet.

(Otherwise, you could get into a situation where people may not be looking carefully at this since the people might assume, in the absence of a "second", that there isn't enough support for the MCP to move forward, and therefore its not worth taking the time to raise formal concerns.)

[richkadel]

@pnkfelix @wesleywiser @bjorn3 @tmandry @WG-mir-opt

tl;dr - I've updated the MCP to prioritize the approach recommended by (eddyb) in the Zulip thread. Please identify a member of your team who is willing to "second" the MCP, or let me know what I need to do to gain your approval. Thanks!

I just want to make sure you are aware that I just updated the MCP to reflect the conversations in the Zulip thread and a strong recommendation to implement coverage as a MIR pass, which I am now attempting.

I also trimmed out some of the discussion that was too focused on the initial prototype, not necessarily related to the now preferred approach.

@tmandry gave me a quick overview of the MIR implementation and the CFG.

I now have some idea how to implement a MIR->MIR pass, and I see the benefits.

As you know, there has been some skepticism of the viability of the MIR->MIR approach, for various reasons, but I'm optimistic it can be done, and the updated MCP now reflects this is the recommended approach.

If for some reason the MIR->MIR implementation doesn't work well, I have fallback approaches that I know will work, based on my initial prototyping.

Thanks!
Rich

[wesleywiser]

@rustbot second

The updated proposal looks to be inline with how I would expect to see this implemented. As a MIR pass, it also seems to me that this feature will be fairly isolated and not significantly impact the rest of the compiler.

[richkadel]

FYI: As of PR rust-lang/rust#78267, LLVM InstrProf-based code coverage is "feature complete"! (I believe this last PR will be in the Rust nightly distribution channel tomorrow, Nov 7.) It has been tested on a few large crate implementations, but will need more real world testing. Please cc me on any bug reports.

Usage is now documented in The Rust Unstable Book.

[bob-wilson]

That's great news! Thank you for your work on this, Rich

[marco-c]

I've implemented support for source-based code coverage in grcov, and used it to collect coverage for grcov itself.
The coverage looks definitely better, with one caveat: there's a file (src/llvm_tools.rs) which seems to be totally uncovered with source-based coverage, but was covered (and I know it is) with gcov-based coverage.
First report with source-based coverage: https://codecov.io/gh/mozilla/grcov/tree/c676f52dc887a3b0b78f3cc623f86373ca276c5b/src.
Last report without source-based coverage: https://codecov.io/gh/mozilla/grcov/tree/5e67e4e750e556ee03c6b6d5e7db79fe4a81c322/src.
(you need to sign in in order to see the files)

@richkadel want me to file an issue with STRs?

[richkadel]

Thanks for testing Marco!

It will be helpful to have a separate issue with reproducible example. Definitely sounds unexpected so it will be good to track this down.

[marco-c]

Ok, I've filed rust-lang/rust#79456.