This is similar to the existing `union`, except that bits in the RHS are
negated before being incorporated into the LHS.

Currently only `DenseBitSet` is supported. Supporting other bitset types is
possible, but non-trivial, and currently isn't needed.

Rollup merge of rust-lang#135481 - Zalathar:node-flow, r=oli-obk

coverage: Completely overhaul counter assignment, using node-flow graphs

The existing code for choosing where to put physical counter-increments gets the job done, but is very ad-hoc and hard to modify without introducing tricky regressions.

This PR replaces all of that with a more principled approach, based on the algorithm described in "Optimal measurement points for program frequency counts" (Knuth & Stevenson, 1973).

---

We start by ensuring that our graph has “balanced flow”, i.e. each node's flow (execution count) is equal to the sum of all its in-edge flows, and equal to the sum of all its out-edge flows. That isn't naturally true of control-flow graphs, so we introduce a wrapper type `BalancedFlowGraph` to fix that by introducing synthetic nodes and edges as needed.

Once our graph has balanced flow, the next step is to create another view of that graph in which each node's successors have all been merged into one “supernode”. Consequently, each node's out-edges can be coalesced into a single out-edge to one of those supernodes. Because of the balanced-flow property, the flow of that coalesced edge is equal to the flow of the original node.

Having expressed all of our node flows as edge flows, we can then analyze node flows using techniques for analyzing edge flows. We incrementally build a spanning tree over the merged supernodes, such that each new edge in the spanning tree represents a node whose flow can be computed from that of other nodes.

When this is done, we end up with a list of “counter terms” for each node, describing which nodes need physical counters, and how the remaining nodes can have their flow calculated by adding and subtracting those physical counters.

---

The re-blessed coverage tests show that this results in modest or major improvements for our test programs. Some tests need fewer physical counters, some tests need fewer expression nodes for the same number of physical counters, and some tests show striking reductions in both.

…ler-errors

coverage: Clean up a few things after the counters overhaul

Follow-up to rust-lang#135481. No functional change; this is mostly just deleting or moving code.

…ler-errors

coverage: Clean up a few things after the counters overhaul

Follow-up to rust-lang#135481. No functional change; this is mostly just deleting or moving code.

Rollup merge of rust-lang#135680 - Zalathar:counters-cleanup, r=compiler-errors

coverage: Clean up a few things after the counters overhaul

Follow-up to rust-lang#135481. No functional change; this is mostly just deleting or moving code.

coverage: Prepare for upcoming changes to counter creation

This is a collection of smaller changes to coverage instrumentation code that have been extracted from a larger PR that I'm still working on, in order to hopefully make review easier.

Each individual change should hopefully be mostly self-explanatory. One of the big goals of the upcoming PR will be to defer certain parts of counter-creation until codegen, via the query system, so that ends up being a recurring theme in these changes. Several of the changes are follow-ups to rust-lang#135481.

There should be no observable change in compiler output.

coverage: Prepare for upcoming changes to counter creation

This is a collection of smaller changes to coverage instrumentation code that have been extracted from a larger PR that I'm still working on, in order to hopefully make review easier.

Each individual change should hopefully be mostly self-explanatory. One of the big goals of the upcoming PR will be to defer certain parts of counter-creation until codegen, via the query system, so that ends up being a recurring theme in these changes. Several of the changes are follow-ups to rust-lang#135481.

There should be no observable change in compiler output.

Rollup merge of rust-lang#135873 - Zalathar:be-prepared, r=oli-obk

coverage: Prepare for upcoming changes to counter creation

This is a collection of smaller changes to coverage instrumentation code that have been extracted from a larger PR that I'm still working on, in order to hopefully make review easier.

Each individual change should hopefully be mostly self-explanatory. One of the big goals of the upcoming PR will be to defer certain parts of counter-creation until codegen, via the query system, so that ends up being a recurring theme in these changes. Several of the changes are follow-ups to rust-lang#135481.

There should be no observable change in compiler output.

Incorporate `iter_nodes` into `graph::DirectedGraph`

This helper method iterates over all node IDs in the dense range `0..num_nodes`.

In practice, we have a lot of graph-algorithm code that already assumes that nodes are densely numbered, by using `num_nodes` to allocate per-node indexed data structures. So I don't think this is actually a substantial change to the de-facto semantics of `graph::DirectedGraph`.

---

Resolves a FIXME from rust-lang#135481.

Rollup merge of rust-lang#136082 - Zalathar:iter-nodes, r=oli-obk

Incorporate `iter_nodes` into `graph::DirectedGraph`

This helper method iterates over all node IDs in the dense range `0..num_nodes`.

In practice, we have a lot of graph-algorithm code that already assumes that nodes are densely numbered, by using `num_nodes` to allocate per-node indexed data structures. So I don't think this is actually a substantial change to the de-facto semantics of `graph::DirectedGraph`.

---

Resolves a FIXME from rust-lang#135481.

coverage: Defer part of counter-creation until codegen

Follow-up to rust-lang#135481 and rust-lang#135873.

One of the pleasant properties of the new counter-assignment algorithm is that we can stop partway through the process, store the intermediate state in MIR, and then resume the rest of the algorithm during codegen. This lets it take into account which parts of the control-flow graph were eliminated by MIR opts, resulting in fewer physical counters and simpler counter expressions.

Those improvements end up completely obsoleting much larger chunks of code that were previously responsible for cleaning up the coverage metadata after MIR opts, while also doing a more thorough cleanup job.

(That change also unlocks some further simplifications that I've kept out of this PR to limit its scope.)

coverage: Defer part of counter-creation until codegen

Follow-up to rust-lang#135481 and rust-lang#135873.

One of the pleasant properties of the new counter-assignment algorithm is that we can stop partway through the process, store the intermediate state in MIR, and then resume the rest of the algorithm during codegen. This lets it take into account which parts of the control-flow graph were eliminated by MIR opts, resulting in fewer physical counters and simpler counter expressions.

Those improvements end up completely obsoleting much larger chunks of code that were previously responsible for cleaning up the coverage metadata after MIR opts, while also doing a more thorough cleanup job.

(That change also unlocks some further simplifications that I've kept out of this PR to limit its scope.)

coverage: Defer part of counter-creation until codegen

Follow-up to rust-lang#135481 and rust-lang#135873.

One of the pleasant properties of the new counter-assignment algorithm is that we can stop partway through the process, store the intermediate state in MIR, and then resume the rest of the algorithm during codegen. This lets it take into account which parts of the control-flow graph were eliminated by MIR opts, resulting in fewer physical counters and simpler counter expressions.

Those improvements end up completely obsoleting much larger chunks of code that were previously responsible for cleaning up the coverage metadata after MIR opts, while also doing a more thorough cleanup job.

(That change also unlocks some further simplifications that I've kept out of this PR to limit its scope.)

Rollup merge of rust-lang#136053 - Zalathar:defer-counters, r=saethlin

coverage: Defer part of counter-creation until codegen

Follow-up to rust-lang#135481 and rust-lang#135873.

One of the pleasant properties of the new counter-assignment algorithm is that we can stop partway through the process, store the intermediate state in MIR, and then resume the rest of the algorithm during codegen. This lets it take into account which parts of the control-flow graph were eliminated by MIR opts, resulting in fewer physical counters and simpler counter expressions.

Those improvements end up completely obsoleting much larger chunks of code that were previously responsible for cleaning up the coverage metadata after MIR opts, while also doing a more thorough cleanup job.

(That change also unlocks some further simplifications that I've kept out of this PR to limit its scope.)