| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
This rewires SCC annotations to have them be a separate,
visitor-type data structure. It was broken out of #130227,
which needed them to be able to remove unused annotations
after computation without recomputing the SCCs themselves.
As a drive-by it also removes some redundant code from
the hot loop in SCC construction for a performance improvement.
|
|
|
|
|
|
This assumes that the set of valid node IDs is exactly `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.
|
|
|
|
|
|
The previous commit updated `rustfmt.toml` appropriately. This commit is
the outcome of running `x fmt --all` with the new formatting options.
|
|
|
|
|
|
This shaves off ca 6% of the cycles in `start_walk_from()` in my
experiments.
|
|
This version shaves off ca 2% of the cycles in my experiments
and makes the control flow easier to follow for me and hopefully
others, including the compiler.
Someone gave me a working profiler and by God I'm using it.
|
|
Note that this changes no executing code. The change is 100% in documentation.
|
|
|
|
|
|
|
|
This patch has been extracted from #123720. It specifically enhances
`Sccs` to allow tracking arbitrary commutative properties of SCCs, including
- reachable values (max/min)
- SCC-internal values (max/min)
This helps with among other things universe computation: we can now identify
SCC universes as a straightforward "find max/min" operation during SCC construction.
It's also more or less zero-cost; don't use the new features, don't pay for them.
This commit also vastly extends the documentation of the SCCs module, which I had a very hard time following.
|
|
|
|
`use` is a nicer way of doing things.
|
|
Now with RPITIT instead of GAT!
|
|
|
|
Now with GAT!
|
|
|
|
|
|
|
|
All the same reasons as for `[T]`: more general, less pointer chasing, and `&mut IndexSlice` emphasizes that it doesn't change *length*.
|
|
|
|
|
|
Convert all the crates that have had their diagnostic migration
completed (except save_analysis because that will be deleted soon and
apfloat because of the licensing problem).
|
|
|
|
|
|
There's a conversation in the tracking issue about possibly unaccepting `in_band_lifetimes`, but it's used heavily in the compiler, and thus there'd need to be a bunch of PRs like this if that were to happen.
So here's one to see how much of an impact it has.
(Oh, and I removed `nll` while I was here too, since it didn't seem needed. Let me know if I should put that back.)
|
|
|
|
|
|
|
|
This allows constructing the sccc for large that visit many nodes before
finding a single cycle of sccc, for example lists. When used to find
dependencies in borrow checking the list case is what occurs in very
long functions.
|
|
The basic conversion is a straightforward conversion of the linear
recursion to a loop forwards and backwards propagation of the result.
But this uses an optimization to avoid the need for extra space that
would otherwise be necessary to store the stack of unfinished states as
the function is not tail recursive.
Observe that only non-root-nodes in cycles have a recursive call and
that every such call overwrites their own node state. Thus we reuse the
node state itself as temporary storage for the stack of unfinished
states by inverting the links to a chain back to the previous state
update. When we hit the root or end of the full explored chain we
propagate the node state update backwards by following the chain until
a node with a link to itself.
|
|
|
|
|
