Stream: t-compiler/major changes

Topic: Implement LLVM-compatible source-based cod compiler-team#278


triagebot (Apr 24 2020 at 17:59, on Zulip):

A new proposal has been announced #278. It will be brought up at the next meeting.

Wesley Wiser (Apr 30 2020 at 14:02, on Zulip):

I do have a few questions from a detailed reading of your proposal, the PR and the related issues:

Wesley Wiser (Apr 30 2020 at 14:02, on Zulip):
Wesley Wiser (Apr 30 2020 at 14:03, on Zulip):
Wesley Wiser (Apr 30 2020 at 14:03, on Zulip):
Wesley Wiser (Apr 30 2020 at 14:03, on Zulip):
Rich Kadel (Apr 30 2020 at 14:17, on Zulip):

Wesley Wiser said:

I think it's sufficient, at least initially, to assume the first significant users will integrate the llvm-profdata and llvm-cov tools into their own toolchains. This is what the Fuchsia team will be doing once coverage is available. Downloading and/or compiling the additional tools, and scripting commands with the project-appropriate flags gives each project owner the most flexibility.

For any end-user that is savvy enough to want to integrate coverage analysis into even small projects, the clang example tutorial I referenced in the MCP is fairly straightforward to run, and is easily scriptable.

I can also imagine future efforts, if someone is motivated to do so, to integrated the Rust coverage features into IDEs (VSCode, etc.) and CI tools (Travis, etc.).

Rich Kadel (Apr 30 2020 at 14:55, on Zulip):

Wesley Wiser said:

It's too early to tell what the performance impact is or what kind of optimizations can be done. (This touches a little on your third bullet as well, so I'll say more on that point in a separate response.)

My prototyping, thus far, is focused on injecting coverage counters, computing the associated coverage regions, and running the resulting program to confirm the results match expectations, so I've done feasibility prototyping, but nothing significant enough to assess performance, yet. I certainly care about performance, and I continue to look into low-hanging-fruit opportunities where available. But other optimizations will have to be done in phases, as mentioned in the MCP, once the base capability is known to work.

Also, since coverage injection will almost certainly be opt-in, and only done very occasionally, the bar for "acceptable" performance is not going to be nearly the same as compiling without that instrumentation. I do expect the impact to be linear to the number of existing branches in the source.

Bob Wilson can speak more authoritatively to the clang approach (ref: https://clang.llvm.org/doxygen/CoverageMappingGen_8cpp_source.html) but my take is that clang is processing the AST and injecting the counters from there. I don't think clang has a direct analogy to the Rust HIR representation, but the clang coverage pass might be considered as happening at a level similar to the AST->HIR lowering pass in rustc_ast_lowering. Both walk the AST in a similar way.

tmandry (Apr 30 2020 at 15:14, on Zulip):

A problem with drawing an analogy to clang is that clang's AST isn't really an AST (it has a lot more HIR-like information hanging off it)

tmandry (Apr 30 2020 at 15:15, on Zulip):

clang also has no MIR equivalent that I know of

Wesley Wiser (Apr 30 2020 at 15:35, on Zulip):

Rich Kadel said:

Wesley Wiser said:

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

I think it's sufficient, at least initially, to assume the first significant users will integrate the llvm-profdata and llvm-cov tools into their own toolchains. This is what the Fuchsia team will be doing once coverage is available. Downloading and/or compiling the additional tools, and scripting commands with the project-appropriate flags gives each project owner the most flexibility.

For any end-user that is savvy enough to want to integrate coverage analysis into even small projects, the clang example tutorial I referenced in the MCP is fairly straightforward to run, and is easily scriptable.

I can also imagine future efforts, if someone is motivated to do so, to integrated the Rust coverage features into IDEs (VSCode, etc.) and CI tools (Travis, etc.).

Sounds great! Thanks

Wesley Wiser (Apr 30 2020 at 15:40, on Zulip):

Compiler performance impact

That makes sense. I agree the threshold is probably significantly higher given that this opt-in for people who want the feature and it should have absolutely no impact otherwise.

I would caution about optimizations on AST/HIR in the future, AFAIK, we have none of those currently or any plans to implement them. Doing any optimizations in rustc was pretty heavily gated on the MIR effort because it just wasn't practical before that point.

Rich Kadel (Apr 30 2020 at 15:41, on Zulip):

Wesley Wiser said:

Yes! I discussed three alternatives in the MCP, and I'm open to influence here. You make a good point about the stability of the AST vs. HIR, an I'm open to influence here. I do see value in an HIR-level approach.

My chief concern is that I need to understand the representation well enough to accurately identify the coverage regions within the original source code, and accurately inject the right counter instructions in the right places. At least with the AST, it's obvious.

I'm already investigating how I can do this within the HIR, and I'd like to do it there if I can ramp up quickly enough, but I also have working code built on the AST. It may or may not be a reasonable cost-benefit tradeoff, for the initial implementation, but if not, it shouldn't be hard to move the coverage-injected nodes to the HIR in a follow-on optimization pass. (The question, then, would be, once there's a proven implementation, would someone then say they can bypass the HIR altogether and just migrate coverage injection directly to a MIR pass? And if that's the case, then spending time trying to move working AST code to HIR might be a waste of time anyway ;-) ...

All this said, I'm not ignoring the feedback here and I am investigating those alternatives.

Wesley Wiser (Apr 30 2020 at 15:44, on Zulip):

Yeah, I didn't mean to imply that you were ignoring the feedback. The entire value proposition of this feature is that it closely matches the end-user's mental model of the language semantics, not an underlying thing like MIR. So I fully agree with you and @Bob Wilson there!

Rich Kadel (Apr 30 2020 at 15:44, on Zulip):

Wesley Wiser said:

I would caution about optimizations on AST/HIR in the future, AFAIK, we have none of those currently or any plans to implement them. Doing any optimizations in rustc was pretty heavily gated on the MIR effort because it just wasn't practical before that point.

Understood. I think my use of the word optimization here refers only to optimizing the implementation of coverage injection, for example, moving coverage injection from earlier passes to later passes, or even simple things like improving how the hash argument is computed.

Wesley Wiser (Apr 30 2020 at 15:44, on Zulip):

I'm just wanting to try to find a way to have our cake and it too. :slight_smile:

simulacrum (Apr 30 2020 at 15:47, on Zulip):

one question I also had -- to what extent do we expect this to be stable? I presume if e.g. rustc 1.50 decided to refactor how things internally were represented and that meant that coverage for some things vanished (e.g. end brace of a for loop or some such) people wouldn't be too concerned?

tmandry (Apr 30 2020 at 15:51, on Zulip):

The effect of that would be degraded behavior, but not breaking anything per se

tmandry (Apr 30 2020 at 15:52, on Zulip):

That's one argument I can see in favor of doing it in a later stage like MIR; fewer edge cases to worry about or that can break.

tmandry (Apr 30 2020 at 15:54, on Zulip):

Another argument is that it might make it easier to use performance counter info directly in MIR optimizations one day, though I'm not 100% clear on exactly how that would work.

simulacrum (Apr 30 2020 at 15:57, on Zulip):

we could e.g. annotate likely/unlikely branches based on perf counters ourselves, though it's probably better to leave that to llvm I imagine

simulacrum (Apr 30 2020 at 15:57, on Zulip):

maybe with e.g. cranelift which doesn't have native support for pgo though that would make more sense

Rich Kadel (Apr 30 2020 at 16:01, on Zulip):

Wesley Wiser said:

To be more clear, I did start an early prototype by injecting coverage in rustc_ast_lowering functions, but as I started working out how to ensure proper coverage for the less simple cases (like lazy booleans, for example), I felt I had more control and visibility by implementing coverage by walking the AST before any HIR code transformations. (Still considering the HIR though, as discussed in my earlier reply.)

I did not code up any prototype on the MIR directly but I used -Zunpretty=mir to get a look at the difference between the uninstrumented MIR and an instrumented MIR (after I had injected counter code), and from that I decided the MIR might be a bridge too far, for me, from a complexity standpoint.

Amanieu (Apr 30 2020 at 16:08, on Zulip):

I recently implemented code coverage support for embedded Rust based on the existing -Zprofile GCOV profiling support: https://github.com/Amanieu/minicov/

It basically works by using a custom implementation of the profiling runtime which simply serializes the counters and metadata to a Vec<u8>. This data can then be sent back to the dev system and "replayed", which creates the .gcda files as if the program was run locally.

Would such an approach also be possible for new profiling system considering the constraints of embedded systems (#[no_std] and no libc but you can use liballoc)? It seems to me that the new profiling system would produce much more accurate profiling information than the existing GCOV-based system which is injected in an LLVM pass.

tmandry (Apr 30 2020 at 16:11, on Zulip):

@Amanieu Possibly, but the actual implementation of maintaining the counters is all in LLVM

Rich Kadel (Apr 30 2020 at 16:27, on Zulip):

On a related note (to the discussion with Wesley on AST vs HIR), I'd like to look into the possible benefits of mirroring what is done in expr_drop_temps...() in rustc_ast_lowering/expr.rs. It appears to inject a custom HIR node hir::ExprKind::DropTemps(expr) that (according to the docs):

    /// ... has the same effect as wrapping `expr` in
    /// `{ let _t = $expr; _t }` but should provide better compile-time performance.

This is very reminiscent of the unwrapped implementation of my notional inlined __incr_cov() implementation. (Aside: I am not comfortable that the inlining will work as expected so my plan is to implement the functionality unwrapped, without introducing an intermediate function call.) So assuming the following match is part of a coverage region that needs a counter:

    match some_expr { ...

Injecting the LLVM intrinsic counter function would look something like:

    match { let _t = some_expr; llvm_instrprof_increment(...); _t } {

I'm interested to get feedback from someone familiar with the DropTemps implementation and ultimate code injection if a similar strategy can be used for the coverage counter injection, and if that would also give us some "better compile time performance".

tmandry (Apr 30 2020 at 16:31, on Zulip):

Rich Kadel said:

I did not code up any prototype on the MIR directly but I used -Zunpretty=mir to get a look at the difference between the uninstrumented MIR and an instrumented MIR (after I had injected counter code), and from that I decided the MIR might be a bridge too far, for me, from a complexity standpoint.

So a benefit of MIR is that every possible branch is encoded directly in the representation (it's a basic block), and that includes things not obvious from the AST, like panic/unwind branches. The question in my mind is whether there's a tradeoff between instrumenting this "invisible code" and having full fidelity on covering the source code. I think full fidelity on the source is most important, but having coverage on all generated code is important too for PGO.

MIR's SourceInfo maps every statement and terminator back to the source code from which it came, and directly after HIR -> MIR construction I would expect that to be quite high fidelity. @eddyb also seems to think this is the way to go.

eddyb (Apr 30 2020 at 16:32, on Zulip):

@Rich Kadel so the decision was based on what you would've had to add in MIR, i.e. the calls? not anything about what information MIR had for you to be able to decide where to instrument?

eddyb (Apr 30 2020 at 16:33, on Zulip):

because this is something that confused me

eddyb (Apr 30 2020 at 16:33, on Zulip):

@Rich Kadel anything you inject early-on will produce messy MIR - that doesn't mean that doing it at the MIR level would require all of that mess

eddyb (Apr 30 2020 at 16:33, on Zulip):

in fact, it's probably much better to try to avoid it in the first place

eddyb (Apr 30 2020 at 16:34, on Zulip):

for example, if you introduce a new MIR statement, you can avoid calls altogether

tmandry (Apr 30 2020 at 16:34, on Zulip):

I think @Bob Wilson (hopefully that's the right person) had looked into this before and decided not to do it in MIR, but I'm not sure what their reasoning was.

eddyb (Apr 30 2020 at 16:34, on Zulip):

MIR calls are terminators because they may unwind

eddyb (Apr 30 2020 at 16:34, on Zulip):

@tmandry oh okay. still, this confusion/question applies to anyone who doesn't want to do something on/with/etc. MIR

Rich Kadel (Apr 30 2020 at 16:34, on Zulip):

eddyb said:

Rich Kadel anything you inject early-on will produce messy MIR - that doesn't mean that doing it at the MIR level would require all of that mess

Yes, I do understand that.

eddyb (Apr 30 2020 at 16:36, on Zulip):

okay reading more of the backlog, DropTemps is basically a noop for almost everything except one part of the compiler

Rich Kadel (Apr 30 2020 at 16:37, on Zulip):

But I look at the MIR and see a bunch of new let statements with auto generated names, etc. etc. and it's just hard to trace back to how to ensure that generating code at that level will give me the result I expect when looking at the source. It's mostly my lack of being able to grok the MIR.

eddyb (Apr 30 2020 at 16:38, on Zulip):

if you want to go that route (DropTemps-like) you could add a "post-instrument" expression, that evaluates the original expression and then immediately afterwards does the instrumentation

tmandry (Apr 30 2020 at 16:39, on Zulip):

/me dreams about a vscode extension or something that lets you mouse over a MIR statement and see the SourceInfo associated with it as a highlight in your editor

eddyb (Apr 30 2020 at 16:39, on Zulip):

@Rich Kadel okay but shouldn't that (groking MIR) be a necessary step before you decide how to implement this?

eddyb (Apr 30 2020 at 16:41, on Zulip):

it's also unclear to me, from the match example, what it is achieved, since there's no way to record which arm matched

Rich Kadel (Apr 30 2020 at 16:41, on Zulip):

I don't see that as a significant requirement. (I agree I have to understand how it works at some level, but not necessarily how it remaps the control flow.) A Rust programmer doesn't have to grok MIR to write Rust.

eddyb (Apr 30 2020 at 16:41, on Zulip):

I mean for implementing this feature, not using it

Rich Kadel (Apr 30 2020 at 16:42, on Zulip):

eddyb said:

it's also unclear to me, from the match example, what it is achieved, since there's no way to record which arm matched

The example is not counting the arms. Its counting the code leading up to the execution of the pattern match, including any code inside the match expression (with the possibility that an insanely complex match expression could include an early return).

tmandry (Apr 30 2020 at 16:43, on Zulip):

eddyb said:

Rich Kadel okay but shouldn't that (groking MIR) be a necessary step before you decide how to implement this?

Meta-point: I mean, that's part of what a design review is for. Taking a stab at a design based on limited information is perfectly acceptable, but knowing all the relevant details before adopting a final design is (also) a good idea.

eddyb (Apr 30 2020 at 16:43, on Zulip):

@Rich Kadel okay, what's the granularity then? expressions nest arbitrarily, do you want to instrument at every point in the expression tree? or is it coarser than that?

eddyb (Apr 30 2020 at 16:44, on Zulip):

having spent time looking into this before, I don't see how you can efficiently instrument code without using a control-flow graph

Rich Kadel (Apr 30 2020 at 16:44, on Zulip):

eddyb said:

Rich Kadel okay, what's the granularity then? expressions nest arbitrarily, do you want to instrument at every point in the expression tree? or is it coarser than that?

Every coded branch.

eddyb (Apr 30 2020 at 16:45, on Zulip):

so you want to find all of the control-flow edges in the AST?

bjorn3 (Apr 30 2020 at 16:47, on Zulip):

If you instrument right before every MIR SwitchInt, Call, Drop and Assert terminator, you will get every possible branch. If you want to ignore unwinds, you only need to instrument SwitchInt.

eddyb (Apr 30 2020 at 16:47, on Zulip):

we used to have code that did that. we've recently removed it after a successful transition to MIR borrowck

eddyb (Apr 30 2020 at 16:49, on Zulip):

@Rich Kadel okay let me ask a more useful question: say you know all the points that are relevant to control-flow: how do you represent all of the code in between, for coverage purposes?

eddyb (Apr 30 2020 at 16:50, on Zulip):

based on the answer to this, the solution may even be implementable all the way down in codegen, even after MIR optimizations have run

eddyb (Apr 30 2020 at 16:50, on Zulip):

with the pre-existing information (which mainly exists for debuginfo)

eddyb (Apr 30 2020 at 16:52, on Zulip):

IIRC, the LLVM format is more fine-grained than lines, and uses some sort of (nested?) range system, but it's been two years since I've looked at it

Rich Kadel (Apr 30 2020 at 16:52, on Zulip):

eddyb said:

I mean for implementing this feature, not using it

That's what I mean too. But I think you are arguing for injecting coverage without caring about what the input source looked like, with the (probably reasonable) assumption that using a downstream representation will be "more efficient" (as you put it), and that's fair. You are much more experienced with this than I am.

All I can say is, I believe I can identify coverage regions and inject coverage counters based on AST nodes without needing to know much more than what Rust source looks like.

I certainly don't want to argue with you over details you are much more familiar with than I am. Just trying to be practical, given my current knowledge.

eddyb (Apr 30 2020 at 16:54, on Zulip):

I'm arguing for something that we'd want to maintain long-term, without loss of precision

eddyb (Apr 30 2020 at 16:55, on Zulip):

and I want to understand what parts of source code you care about, that the MIR doesn't already represent accurately

eddyb (Apr 30 2020 at 16:55, on Zulip):

after all, our debuginfo is emitted from MIR, and in a lossy way. that is, MIR has more information than DWARF can encode

eddyb (Apr 30 2020 at 16:57, on Zulip):

@Rich Kadel anyway to the best of my knowledge there is no advantage to doing the injection at any point before HIR -> MIR

Rich Kadel (Apr 30 2020 at 16:57, on Zulip):

eddyb said:

Rich Kadel okay let me ask a more useful question: say you know all the points that are relevant to control-flow: how do you represent all of the code in between, for coverage purposes?

I can try an example

Rich Kadel (Apr 30 2020 at 16:58, on Zulip):

eddyb said:

Rich Kadel anyway to the best of my knowledge there is no advantage to doing the injection at any point before HIR -> MIR

What do you mean by "advantage", just so I'm clear?

tmandry (Apr 30 2020 at 16:58, on Zulip):

eddyb said:

and I want to understand what parts of source code you care about, that the MIR doesn't already represent accurately

I think this is the point that's unclear right now. We don't know if there's any loss of fidelity in the MIR representation, and it would take some work to find out. The most important thing is full fidelity, so from that standpoint I can see why AST or HIR feel safest. But your earlier point about this producing messy MIR with a lot of unwind branches is well taken (by me).. that will impact compiler performance quite a lot.

eddyb (Apr 30 2020 at 16:58, on Zulip):

not only will it impact performance, it risks impacting semantics

eddyb (Apr 30 2020 at 16:59, on Zulip):

which is far scarier than code coverage not being 100% accurate

Rich Kadel (Apr 30 2020 at 16:59, on Zulip):

eddyb said:

not only will it impact performance, it risks impacting semantics

I don't believe the injection I have in mind will impact semantics at all, btw

eddyb (Apr 30 2020 at 17:00, on Zulip):

you're changing the HIR which goes into type-checking, there are enough subtleties that it's hard to say just from looking at it

eddyb (Apr 30 2020 at 17:00, on Zulip):

the only thing I am aware of that is almost guaranteed to not impact semantics is adding non-let statements

eddyb (Apr 30 2020 at 17:01, on Zulip):

in that it translates to adding a sub-CFG of MIR that doesn't change the CFG around it

eddyb (Apr 30 2020 at 17:01, on Zulip):

well, a statement that doesn't mention any local variables, that is

eddyb (Apr 30 2020 at 17:02, on Zulip):

it's equivalent to having a new built-in MIR statement, and can't influence typeck of the code around it either

eddyb (Apr 30 2020 at 17:02, on Zulip):

anyway, AST -> HIR is "lossy except for diagnostics", in that we actually preserve enough information, despite desugaring the structure, to know what kind of AST shape some HIR came from

Rich Kadel (Apr 30 2020 at 17:03, on Zulip):

@eddyb you type too fast and I don't have time to respond :-)

eddyb (Apr 30 2020 at 17:04, on Zulip):

time is money :P

eddyb (Apr 30 2020 at 17:04, on Zulip):

so while you can inject in AST -> HIR, you can also do it as HIR -> HIR (except for HIR transformations not existing), which means you can do it in HIR -> MIR

eddyb (Apr 30 2020 at 17:05, on Zulip):

doing it as late as possible using the same information source means there is less friction/interference with other parts of the compiler

Rich Kadel (Apr 30 2020 at 17:06, on Zulip):

I get that and am on board generally speaking.

eddyb (Apr 30 2020 at 17:06, on Zulip):

then the only question about MIR specifically is whether MIR -> MIR is lossier compared to HIR -> MIR

eddyb (Apr 30 2020 at 17:07, on Zulip):

but if it starts off in HIR -> MIR then it's much easier to move later to MIR -> MIR, even if there are reasons to believe we can't do it in MIR -> MIR from the start, or just because we don't want to bother

eddyb (Apr 30 2020 at 17:08, on Zulip):

and to avoid constructing true calls, you can add a new StatementKind

eggyal (Apr 30 2020 at 17:08, on Zulip):

Perhaps I can add something useful here. I was working on this very issue back towards the end of last year, but events rather swamped over me and I've not been able to return to it. I'm delighted to see @Rich Kadel picking it up and taking it forward. On the issue of when to instrument, I had preferred instrumenting the MIR for all the reasons that are being articulated here now—but...

eggyal (Apr 30 2020 at 17:11, on Zulip):

The LLVM instrumentation leans toward having calculated regions wherever possible, and only making instrumentation calls where the count cannot be imputed from other counters. I found it impossible to reliably formulate the necessary flow graph from the MIR, and saw this as something far easier to construct with the HIR.

eddyb (Apr 30 2020 at 17:11, on Zulip):

(note that HIR -> MIR is not MIR instrumentation, but HIR instrumentation, just emitting the instrumentation calls in MIR instead of trying to fit them into HIR)

eddyb (Apr 30 2020 at 17:12, on Zulip):

@eggyal hmm I would've used linear sequences of basic blocks that are connected byCall terminators, but that's just an optimization over using basic blocks

eggyal (Apr 30 2020 at 17:13, on Zulip):

@eddyb But that doesn't help you decide when a linear sequence has no other entry points?

eddyb (Apr 30 2020 at 17:13, on Zulip):

unless you mean considering each basic block's counter a variable in a system of equations and trying to reduce the base number of variables

eddyb (Apr 30 2020 at 17:14, on Zulip):

@eggyal what do you mean, that's just a property of the CFG

eddyb (Apr 30 2020 at 17:15, on Zulip):

you either compute that by doing a full traversal or just use the predecessors cache if you want

eddyb (Apr 30 2020 at 17:19, on Zulip):

if you do a full traversal you can just record the number of ingoing edges (i.e. predecessors) of each basic block and then you only treat it as not needing its own counter if it has exactly one ingoing edge that's e.g. not conditional

eddyb (Apr 30 2020 at 17:20, on Zulip):

you can do all sorts of things on a CFG

eddyb (Apr 30 2020 at 17:20, on Zulip):

what I'd rather be worried about with MIR -> MIR is whether code affected by counters is describable given the MIR

eggyal (Apr 30 2020 at 17:20, on Zulip):

Hm. I don't recall seeing a predecessors cache—so that may well have made a big difference! I also struggled mapping some blocks back to source code regions, though that was early on in my exploration and I can't immediately recall what the issues were. Reading back over the comments at the time, I also see @**Bob Wilson**'s comment

Consider "if let condition" followed by a blank line vs. "match condition" followed by a blank line. What execution count should be displayed for that blank line? For the "if", Clang shows the "then" count. The corresponding behavior for the "match" (or a match lowered from "if let") would be to show the count for the first arm of the match. That just seems wrong to me.

These sorts of gap regions are difficult to identify and locate from the MIR.

Bob Wilson (Apr 30 2020 at 17:21, on Zulip):

Wow, there's a lot of discussion here today and I've only got a few minutes this morning to respond. I can follow up later with more detailed responses.

eddyb (Apr 30 2020 at 17:21, on Zulip):

@eggyal okay yeah this is the interesting parts to me (mapping the source code)

eddyb (Apr 30 2020 at 17:21, on Zulip):

@Bob Wilson sorry, I tried to stay out of it but @tmandry pinged me

eddyb (Apr 30 2020 at 17:22, on Zulip):

@Bob Wilson I can clear up something right away: this is unnecessary: "side table mapping AST nodes to counters, lower that through HIR, and then insert the intrinsic calls during the HIR-to-MIR lowering"

eddyb (Apr 30 2020 at 17:22, on Zulip):

the HIR contains enough information that you don't need to know the AST it came from

eddyb (Apr 30 2020 at 17:23, on Zulip):

this mostly exists for diagnostics, which need to be accurate even when the actual constructs were desugared

eddyb (Apr 30 2020 at 17:24, on Zulip):

also, rustc's Spans record a macro backtrace, and HIR desugaring is also encoded in that, so you can probably do a bunch more things that not even heavy diagnostics logic does yet :P

eddyb (Apr 30 2020 at 17:26, on Zulip):

@eggyal I don't understand the quoted example. is the blank line inside the condition expression part of the syntax or after the {?

eddyb (Apr 30 2020 at 17:27, on Zulip):

are we talking about a blank line that's outside of a match arm but inside the {...} that enclose the match arms?

Bob Wilson (Apr 30 2020 at 17:28, on Zulip):

eddyb said:

the HIR contains enough information that you don't need to know the AST it came from

I'm not that familiar with it, but I'm not convinced. The coverage map generated from the AST needs to refer to counter indices. The counter indices are associated with different AST nodes and the details on how to inject the instrumentation may depend on the type of the AST node. How can you get that counter index from HIR and what kind of node it came from (e.g., a "match" lowered from an AST "if" should probably be instrumented differently than a source-level "match")?

eddyb (Apr 30 2020 at 17:28, on Zulip):

keep in mind you have this problem all the way throughout the AST -> HIR -> MIR pipeline

eddyb (Apr 30 2020 at 17:28, on Zulip):

@Bob Wilson isn't rustc's job to invent those counters?

eddyb (Apr 30 2020 at 17:29, on Zulip):

why would AST and HIR be different? other than the desugaring, which I just pointed out you can observe that it happened

eddyb (Apr 30 2020 at 17:29, on Zulip):

you can tell apart if-let from match on HIR

eddyb (Apr 30 2020 at 17:29, on Zulip):

again, mostly for diagnostics reasons

eddyb (Apr 30 2020 at 17:30, on Zulip):

anyway I agree that figuring out the coverage map is the most important part of this

eddyb (Apr 30 2020 at 17:33, on Zulip):

HIR/MIR has no(conditional branches that aren't visible in the source with two notable exceptions I guess: the pattern-matching on Iterator::next's result in for loop, and the pattern-matching ? does. but MIR can tell they came from a desugaring, last I checked

eddyb (Apr 30 2020 at 17:33, on Zulip):

HIR -> MIR introduces some checks for e.g. array indexing and checked arithmetic, but those use the Assert terminator, not conditional control-flow

tmandry (Apr 30 2020 at 17:35, on Zulip):

Naively to me, it does seem like you can instrument every branch regardless of what the source looked like (modulo optimizing away unnecessary counters like @eggyal was talking about), and care about what the source looked like only when building a map between counters and source code. If means multiple "hidden" branches map back to the exact same code, that's okay; that additional information could still be useful for optimization purposes.

eddyb (Apr 30 2020 at 17:35, on Zulip):

also, rather than gaps, I'd be more concerned about overlaps

eddyb (Apr 30 2020 at 17:36, on Zulip):

how do you build a coverage map out of an expression tree where each expression has a range in the source?

eddyb (Apr 30 2020 at 17:37, on Zulip):

what's the algorithm? how does it behave when the naive assumption that the ranges are trivially nested, breaks down?

eddyb (Apr 30 2020 at 17:37, on Zulip):

how do you handle all of the ways in which macro expansion can create spans?

eggyal (Apr 30 2020 at 17:38, on Zulip):

eddyb said:

what's the algorithm? how does it behave when the naive assumption that the ranges are trivially nested, breaks down?

It's worth reading http://llvm.org/docs/CoverageMappingFormat.html#mapping-region

eddyb (Apr 30 2020 at 17:38, on Zulip):

and I have, two years ago :)

eddyb (Apr 30 2020 at 17:38, on Zulip):

my question is how do you produce that from Rust ASTs

eddyb (Apr 30 2020 at 17:40, on Zulip):

the best way to handle gaps, IMO, is to consider anything that's not a sub-range, as always executing if the parent expression executes. this means that various bits of syntax, punctuation, etc., are automatically included, and the only parts that can vary dynamically are exactly what's not guaranteed to also execute

eddyb (Apr 30 2020 at 17:41, on Zulip):

AFAIK the format allows this and many other approaches, but you still have to pick a way to turn expression spans into that format

Rich Kadel (Apr 30 2020 at 17:43, on Zulip):

My feeling is the discussion on where to include whitespace, comments, and punctuation are very minor issues and maybe not worth too much discussion at this stage of the proposal.

eddyb (Apr 30 2020 at 17:43, on Zulip):

the nice thing about a sufficiently capable algorithm is that it will likely be correct when throwing MIR spans at it willy nilly

eddyb (Apr 30 2020 at 17:43, on Zulip):

@Rich Kadel a correct implementation wrt those is likely going to be most of the effort

eddyb (Apr 30 2020 at 17:44, on Zulip):

anyway when I agreed to offer @tmandry my emails from two years ago I didn't agree to repeat the whole experience again

eddyb (Apr 30 2020 at 17:45, on Zulip):

my main piece of advice is that there shouldn't be any loss of information between the AST observed by AST -> HIR and the HIR observed by HIR -> MIR and injecting in the latter is less likely to be a problem long-term

eddyb (Apr 30 2020 at 17:47, on Zulip):

HIR -> MIR vs MIR -> MIR is a more advanced matter of syntactically shallow vs semantic approaches, and what the actual goals are

Rich Kadel (Apr 30 2020 at 17:47, on Zulip):

eddyb said:

anyway when I agreed to offer tmandry my emails from two years ago I didn't agree to repeat the whole experience again

Apologies if I've cause some churn here. Was not aware of these emails, but I can get them from @tmandry

Thanks for the great feedback.

eddyb (Apr 30 2020 at 17:47, on Zulip):

ah I thought tmandry already discussed it

eddyb (Apr 30 2020 at 17:48, on Zulip):

anyway I will try to stay out of the way of this. I cannot be 100% objective due to the stuff from a couple years ago

eddyb (Apr 30 2020 at 17:48, on Zulip):

most of the information is in what I said above and those emails, although they might be outdated by now

eddyb (Apr 30 2020 at 17:49, on Zulip):

@bjorn3, @Wesley Wiser and the rest of @WG-mir-opt should be able to help

eddyb (Apr 30 2020 at 17:49, on Zulip):

with either HIR -> MIR or MIR -> MIR

eddyb (Apr 30 2020 at 17:49, on Zulip):

good luck, have fun, stay safe, etc.

Rich Kadel (Apr 30 2020 at 17:52, on Zulip):

Thank you! You as well.

tmandry (Apr 30 2020 at 19:11, on Zulip):

Sorry, I got sidetracked and wasn't able to share the emails right away. It's done now

Bob Wilson (Apr 30 2020 at 21:22, on Zulip):

It sounds like there is some history about this topic that I'm not aware of.... Anyway, I generally agree with @eddyb, but I still think building the coverage map from ASTs would be more maintainable, since doing it from HIR would need to be updated to account for any changes in the desugaring over time. If you produce the coverage map from the AST, it shouldn't be hard to pass it through HIR -- it's mostly self-contained except for the mapping to counter numbers, and I think that mapping could be translated to describe the HIR without much difficulty. Inserting instrumentation during HIR->MIR lowering would also be my recommendation. @Rich Kadel, you don't really need to understand MIR very well to do that, since the analysis of the control flow would be done earlier.

Bob Wilson (May 05 2020 at 00:01, on Zulip):

@Rich Kadel You wrote in the GitHub PR and issue that you're now planning to implement this as a MIR -> MIR pass based on feedback here. From what I see here, the clear feedback is that the instrumentation should be inserted in MIR, but there was at least as many recommendations to do that in HIR -> MIR lowering, with the coverage map computed from the AST or HIR. What led you to settle on MIR -> MIR? Specifically, how do you intend to build the coverage map from MIR? I saw a few comments suggesting that is should be doable, but it still sounds difficult to me.

Rich Kadel (May 05 2020 at 00:11, on Zulip):

@Bob Wilson I did a walkthrough of the MIR with @tmandry on Friday and I can see in the CFG and data structures how the MIR branches should map back to the AST nodes; and from there, I expect to be able to map back to the coverage regions. This still has to be proven of course, but MIR->MIR was cleary @eddyb 's preferred approach, and based on his experience, and @tmandry 's recommendations (which I believe were influenced by the discussion in this thread), it's worth prioritizing an attempt at MIR->MIR. If I run into any unexpected complications, I'll document them and can discuss the pros and cons of alternatives from there.

Rich Kadel (May 05 2020 at 00:23, on Zulip):

eddyb said:

bjorn3, Wesley Wiser and the rest of @WG-mir-opt should be able to help

@WG-mir-opt Please take a look at my revisions to the Rust coverage MCP submission. (I tried to tag this group by @mention but github does not allow me to; hence this ping.) Thanks!

Wesley Wiser (May 05 2020 at 13:59, on Zulip):

Thanks for the ping @Rich Kadel! I'm going to spend some time this evening going over the revised proposal and the rest of the thread here.

triagebot (May 06 2020 at 15:36, on Zulip):

@T-compiler: Proposal #278 has been seconded, and will be approved in 10 days if no objections are raised.

Rich Kadel (May 21 2020 at 20:28, on Zulip):

@T-compiler: Proposal #278 was accepted/approved, with note from @nikomatsakis on May 21. Thanks!

Rich Kadel (Aug 12 2020 at 18:23, on Zulip):

@T-compiler - I'd like to give the broader compiler team an opportunity to take a look at and potentially weigh in on a suggested change to how I represent coverage counter metadata injected into MIR.

I currently encode metadata as Rust intrinsic functions and args (Operands), most of which inform the codegen process (e.g., to generate the coverage map data section), but not always generating an actual LLVM intrinsic call.

The use of existing MIR Call Terminators and arguments allows me to implement the coverage instrumentation purely through MIR manipulation, but it's a bit "hacky" using "fake" function calls, and encoding and decoding Operands just to pass data from the MIR phase to the codegen phase. (This was a known tradeoff of the current approach.)

I recently noticed that the current approach also results in some less than optimal LLVM IR output, adding some unnecessary BasicBlocks and branches, and worse, moving those blocks around so the LLVM IR is not as sequential as it would be otherwise (making it less "readable", for those that care to read it).

I see an opportunity to not only improve the LLVM IR generation, but also significantly improve some of the MIR and codegen aspects of this implementation.

I suggest changing the implementation from using "Call" terminators to
using a custom Statement. This would have several benefits:

  1. One problem with using a Call Terminator is a Terminator requires its own
    BasicBlock, but as it turns out, LLVM's instrprof.increment intrinsic is converted
    into a set of inline statements that don't actually perform a function call and don't
    need to unwind or branch. However, the existence of the BasicBlock in the Rust MIR CFG
    results the generation of an additional BasicBlock label, and an unnecessary branch,
    from the statement just after the increment statements to the label for the next
    block, even though the first statement of the next block is sequentionally next
    anyway. Here's an LLVM IR snippet to demonstrate this. The example function has no
    statements:

No instrumentation:

     {
       start:
       ret void
     }

Current instrumentation with required new block:

     {
       start:
       %pgocount = load i64, i64* getelementptr inbounds ([1 x i64],  [1 x i64]* @__profc_testfunc, i64 0, i64 0)
       %0 = add i64 %pgocount, 1
       store i64 %0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc_testfunc, i64 0, i64 0)
       br label %bb1          ; unnecessary

       bb1:                   ; unnecessary
       ret void
     }

Expected instrumentation, possible with custom coverage Statement

     {
       start:
       %pgocount = load i64, i64* getelementptr inbounds ([1 x i64],  [1 x i64]* @__profc_testfunc, i64 0, i64 0)
       %0 = add i64 %pgocount, 1
       store i64 %0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc_testfunc, i64 0, i64 0)
       ret void
     }
  1. Also, to inject the new BasicBlock requires adding the block to the end of the vector
    of BasicBlocks, and then, since the new block has to be inserted BEFORE another block,
    the "next" BasicBlockData has to be swapped with the new intrinsic Call terminator
    BasicBlockData, which results in LLVM IR that jumps around more than it would
    otherwise. (What was the first block in a Function moves to the last block in the
    function, and shows up last in LLVM IR, with a branch to that last block after
    incrementing the intrinsic. A custom Statement would avoid all of this.

  2. A custom statement should allow us to embed metadata in the new Statement variant(s)
    without requiring me to encode them as Operands, for which the translations can be
    somewhat obscure. Currently, the Operand types require very specific Type
    metadata that was really hard to get right, just to make the intrinsics look like
    normal Rust function calls, even though they are never actually used that way.

  3. The filename str generates an Allocation for the string content, and even though
    this const operand is _only_ used pre-codegen, this unused alloc still gets injected
    into LLVM IR. This entire issue can be avoided with a custom Statement.

  4. The temporary objects and corresponding StorageLive and StorageDead Statements,
    required by the Call as a return result (though empty), can be removed.

  5. All of the essentially "fake" coverage intrinsic function declarations, and the
    associated "lang items" can be removed.

  6. The special handling of these calls during code generation can be migrated to more
    isolated and coverage-specific handlers of the coverage Statement(s), which would
    make the rest of the intrinsic codegen handling less confusing.

All of these changes will probably result in a simpler and smaller overall
implementation.

(Attn to primary reviewers: @Wesley Wiser @tmandry )

tmandry (Aug 12 2020 at 18:37, on Zulip):

Given that the eventual goal is to add an intrinsic to every branch, I think adding another StatementKind makes sense given the likely performance impact and the complexity of the IR that we'd get otherwise.

tmandry (Aug 12 2020 at 18:39, on Zulip):

That said, there of course is a cost of adding a new case to everything that consumes MIR

tmandry (Aug 12 2020 at 18:43, on Zulip):

I wonder if other intrinsics would also benefit from being modeled as statements

Rich Kadel (Aug 12 2020 at 19:29, on Zulip):

Maybe. I'm not sure they would all have similar benefits, but other intrinsics in rustc_codegen_ssa::mir::block that don't get passed to codegen_intrinsic_call() include transmute, drop_in_place, caller_location, and (I think) simd_shuffle, assert_inhabited, assert_zero_valid, and assert_uninit_valid. These all handle codegen a bit differently, and I don't see a lot of similarity to how coverage injection is done.

Rich Kadel (Aug 12 2020 at 19:31, on Zulip):

IMO I think it would be hard to come up with a one-size-fits-all solution. If we can limit this discussion to the original topic, I think it will be easier to get through; and if there's agreement to move forward, it could be a model for other intrinsics to follow in the future.

Rich Kadel (Aug 13 2020 at 23:11, on Zulip):

@Wesley Wiser I noted your thumbs-up, and I'm not seeing any objections to the suggested approach. Unless you think we should wait longer, I may start working on this tomorrow. Let me know if you disagree. Thanks!

Wesley Wiser (Aug 14 2020 at 01:20, on Zulip):

No objections here. I do wonder though if adding new MIR StatementKinds needs to go through an MCP.

I can see a few ways we could go:

Rich Kadel (Aug 14 2020 at 01:34, on Zulip):

I'm leaning toward the first option, but since there are essentially three variants of coverage intrinsics right now (increment, expression, and unreachable) I think I would implement it as a StatementKind variant with sub-variants anyway. If (perhaps deciding during code review) we decide it makes sense to make this more general purpose, we can add more sub-variants for any of those other intrinsics that make sense.

Rich Kadel (Aug 14 2020 at 01:35, on Zulip):

That would limit the impact of adding new subvariants to a much smaller code footprint, compared with adding more StatementKinds

Rich Kadel (Aug 14 2020 at 01:43, on Zulip):

As for going through another MCP, obviously I can't make that call, but I don't see why this would not be considered just a design decision under the existing, approved MCP. There wasn't anything in the MCP that contradicts this approach. (We even considered it in the beginning. At least, I remember Tyler suggesting using a Statement instead of inserting a block, so he gets the credit for that good idea ;-)

Perhaps let's see what the PR looks like, and if it feels "major", consider either looping in others for review, or consider an MCP if there are broader impacts we don't forsee.

Wesley Wiser (Aug 14 2020 at 20:39, on Zulip):

I'm fine with starting the work now and seeing what it looks like. There are large number of consumers of MIR in the compiler ecosystem so adding new types of statements might be disruptive enough that it requires it's own MCP. I will reach out to some folks and see what they think. If that is the case, having a PR with the suggested design would probably make it go faster so that would still be helpful.

Rich Kadel (Aug 15 2020 at 21:45, on Zulip):

The PR is complete and ready for review: https://github.com/rust-lang/rust/pull/75563

Rich Kadel (Aug 16 2020 at 05:02, on Zulip):

I'm really happy with the results, but in terms of the rustc implementation code itself (significantly reduced SLOC and complexity), and much smaller impact on the generated MIR and LLVM IR. See for example the cleaner mir-opt diff, vs. the prior implementation. And the unwanted alloc in the LLVM IR (for the non-codegenned filename string operand) is taken care of now too.

Rich Kadel (Aug 17 2020 at 16:59, on Zulip):

I realized a couple of additional advantages (in addition to the original 7 advantages I expected):

* Diff-based tests of both MIR and LLVM are much less brittle because the lines changed have a direct relationship with the enabled coverage instrumentation feature. This will make a huge difference when I add more tests to cover different branching scenarios (if-else, match, lazy boolean, loops) because unlike the prior implementation, I don't have to move entire blocks around.
* Since I'm not limited to primitive data types supported by Operand, I was able to take advantage of semantically-enforced newtype_index! types throughout the implementation, from injection to codegen to the coverage map generation. The implementation has better consistency across the board, and should be much more maintainable.

Rich Kadel (Aug 17 2020 at 23:22, on Zulip):

Wesley Wiser said:

...
I can see a few ways we could go:

The PR currently calls it StatementKind::Coverage and has one variant value of type Coverage.

If we want to make this a little more generic, I'd like to suggest: StatementKind::Injected, taking an InjectedKind enum value. Coverage can then be a kind of Injected statement.

The semantics of an "Injected" statement would be, the statement is injected during compilation (it does not exist at the source level), meaning it can be ignored or removed without affecting the semantics of the original source code.

I think it's reasonable to expect an Injected statement does not return a value, and does not unwind.

I haven't looked into whether these semantics support any of the other non-codegenned intrinsics, but the Injected variant could be used with other, future instrumentation features (maybe similar to LLVM sanitizers).

This lines up with the PR feedback from @RalfJ regarding how Miri should handle Coverage.

tmandry (Nov 12 2020 at 02:13, on Zulip):

I put up a PR for a blog post announcing this feature: https://github.com/rust-lang/blog.rust-lang.org/pull/725

flip1995 (Nov 12 2020 at 08:27, on Zulip):

FYI: Clippy code coverage

flip1995 (Nov 12 2020 at 08:28, on Zulip):

One question: Is it possible to exlude deps when creating or showing the coverage report?

tmandry (Nov 12 2020 at 20:33, on Zulip):

@flip1995 I think you can compile the deps without -Zinstrument-coverage, though it might require cargo support

tmandry (Nov 12 2020 at 20:34, on Zulip):

@Rich Kadel do you know how that would interact with e.g. generic functions from other crates that are monomorphized when compiling with -Zinstrument-coverage?

Andrew Chin (Nov 13 2020 at 19:31, on Zulip):

Hi all -- i'm having trouble finding the llvm-cov binary. according to the docs, it should be next to llvm-profdata, but i'm not finding it

Andrew Chin (Nov 13 2020 at 19:33, on Zulip):

ooh, i see. i need #78947. ok, nevermind! sorry for the noise

Thomas McGuire (Nov 17 2020 at 14:07, on Zulip):

I had the same issue about llvm-cov. Maybe it's worth extending https://doc.rust-lang.org/nightly/unstable-book/compiler-flags/source-based-code-coverage.html to mention how to install llvm-cov with rustup, and where to find the binary?

Thomas McGuire (Nov 17 2020 at 14:20, on Zulip):

Also, for anyone else reading this, in the hope it helps: When installing llvm-tools-preview with rustup for nightly, make sure to remove miri first, as it is not contained in the version of today (https://rust-lang.github.io/rustup-components-history/), and rustup will skip versions with missing components (https://github.com/rust-lang/blog.rust-lang.org/pull/725#discussion_r523181457).

Thomas McGuire (Nov 17 2020 at 14:55, on Zulip):

After solving the llvm-cov issue, it seems to work nicely so far. Good job! :thumbs_up:

Arnaud de Bossoreille (Nov 17 2020 at 21:54, on Zulip):

Hi, I am having trouble with the generated prof data, it is not empty but it reports 0% coverage. More details about what I do:

Reading tracefile lcov.txt
Summary coverage rate:
  lines......: 0.0% (0 of 13741 lines)
  functions..: 0.0% (0 of 1122 functions)
  branches...: no data found

I cannot figure out what is my mistake.

Arnaud de Bossoreille (Nov 17 2020 at 22:35, on Zulip):

I managed to go further the doc tests overwrote the raw data after the test executable. I'll try to play with LLVM_PROFILE_FILE.

Last update: May 07 2021 at 06:00UTC