| Age | Commit message (Collapse) | Author | Lines |
|---|
|
All the same reasons as for `[T]`: more general, less pointer chasing, and `&mut IndexSlice` emphasizes that it doesn't change *length*.
|
|
time-passes`
|
|
|
|
|
|
|
|
|
|
Consistently use dominates instead of is_dominated_by
There is a number of APIs that answer dominance queries. Previously they were named either "dominates" or "is_dominated_by". Consistently use the "dominates" form.
No functional changes.
|
|
There is a number of APIs that answer dominance queries. Previously they
were named either "dominates" or "is_dominated_by". Consistently use the
"dominates" form.
No functional changes.
|
|
Lazy dominator tree construction in borrowck
Motivated by the observation that sometimes constructed dominator tree was never queried.
|
|
Remove some `ref` patterns from the compiler
Previous PR: https://github.com/rust-lang/rust/pull/105368
r? `@Nilstrieb`
|
|
Fix Dominators::rank_partial_cmp to match documentation
The only use site is also updated accordingly and there is no change in end-to-end behaviour.
|
|
The only use site is also updated accordingly and there is no change in
end-to-end behaviour.
|
|
Switching them to `Break(())` and `Continue(())` instead.
libs-api would like to remove these constants, so stop using them in compiler to make the removal PR later smaller.
|
|
Motivated by the observation that sometimes constructed dominator tree
was never queried.
|
|
Remove double spaces after dots in comments
Most of the comments do not have double spaces, so I assume these are typos.
|
|
|
|
|
|
Also fixes a bug in dominator computation
|
|
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).
|
|
Remove the `..` from the body, only a few invocations used it and it's
inconsistent with rust syntax.
Use `;` instead of `,` between consts. As the Rust syntax gods inteded.
|
|
|
|
|
|
Some tests took too long and owning_ref is fundamentally flawed,
so don't run these tests or run them with a shorter N. This makes
miri with `-Zmiri-strict-provenance` usable to find UB.
|
|
|
|
|
|
Implement `Ord`, `PartialOrd` for SpanData
|
|
|
|
|
|
|
|
|
|
|
|
This integrates the preorder and postorder traversals into one.
|
|
This largely avoids remapping from and to the 'real' indices, with the exception
of predecessor lookup and the final merge back, and is conceptually better.
|
|
|
|
|
|
As the paper indicates, the unprocessed vertices in the DFS tree and processed
vertices are disjoint, and we can use them in the same space, tracking only the index
of the split.
|
|
This replaces the previous implementation with the simple variant of
Lengauer-Tarjan, which performs better in the general case. Performance on the
keccak benchmark is about equivalent between the two, but we don't see
regressions (and indeed see improvements) on other benchmarks, even on a
partially optimized implementation.
The implementation here follows that of the pseudocode in "Linear-Time
Algorithms for Dominators and Related Problems" thesis by Loukas Georgiadis. The
next few commits will optimize the implementation as suggested in the thesis.
Several related works are cited in the comments within the implementation, as
well.
Implement the simple Lengauer-Tarjan algorithm
This replaces the previous implementation (from #34169), which has not been
optimized since, with the simple variant of Lengauer-Tarjan which performs
better in the general case. A previous attempt -- not kept in commit history --
attempted a replacement with a bitset-based implementation, but this led to
regressions on perf.rust-lang.org benchmarks and equivalent wins for the keccak
benchmark, so was rejected.
The implementation here follows that of the pseudocode in "Linear-Time
Algorithms for Dominators and Related Problems" thesis by Loukas Georgiadis. The
next few commits will optimize the implementation as suggested in the thesis.
Several related works are cited in the comments within the implementation, as
well.
On the keccak benchmark, we were previously spending 15% of our cycles computing
the NCA / intersect function; this function is quite expensive, especially on
modern CPUs, as it chases pointers on every iteration in a tight loop. With this
commit, we spend ~0.05% of our time in dominator computation.
|
|
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.)
|
|
r=petrochenkov"
The PR had some unforseen perf regressions that are not as easy to find.
Revert the PR for now.
This reverts commit 6ae8912a3e7d2c4c775024f58a7ba4b1aedc4073, reversing
changes made to 86d6d2b7389fe1b339402c1798edae8b695fc9ef.
|
|
|
|
|
|
|
|
This expands the API to be more flexible, allowing for more visitation patterns
on graphs. This will be useful to avoid extra datasets (and allocations) in
cases where the expanded DFS API is sufficient.
This also fixes a bug with the previous DFS constructor, which left the start
node not marked as visited (even though it was immediately returned).
|
|
|
|
|
|
|
|
|
|
rustc_lint and rustc_lint_defs weren't switched because they're included
in the compiler book and so can't use intra-doc links.
|
|
Reworks Sccc computation to iteration instead of recursion
Linear graphs, producing as many scc's as nodes, would recurse once for every node when entered from the start of the list. This adds a test that exhausted the stack at least on my machine with error:
```
thread 'graph::scc::tests::test_deep_linear' has overflowed its stack
fatal runtime error: stack overflow
```
This may or may not be connected to #78567. I was only reminded that I started this rework some time ago. It might be plausible as borrow checking a long function with many borrow regions around each other—((((((…))))))— may produce the linear list setup to trigger this stack overflow ? I don't know enough about borrow check to say for sure.
This is best read in two separate commits. The first addresses only `find_state` internally. This is classical union phase from union-find. There's also a common solution of using the parent pointers in the (virtual) linked list to track the backreferences while traversing upwards and then following them backwards in a second path compression phase.
The second is more involved as it rewrites the mutually recursive `walk_node` and `walk_unvisited_node`. Firstly, the caller is required to handle the unvisited case of `walk_node` so a new `start_walk_from` method is added to handle that by walking the unvisited node if necessary. Then `walk_unvisited_node`, where we would previously recurse into in the missing case, is rewritten to construct a manual stack of its frames. The state fields consist of the previous stack slots.
|
|
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.
|
