| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Switching to `Ordering::then_with` makes control-flow less complicated, and
there is no need to use `partial_cmp` here.
|
|
instead
|
|
|
|
Preprocess and cache dominator tree
Preprocessing dominators has a very strong effect for https://github.com/rust-lang/rust/pull/111344.
That pass checks that assignments dominate their uses repeatedly. Using the unprocessed dominator tree caused a quadratic runtime (number of bbs x depth of the dominator tree).
This PR also caches the dominator tree and the pre-processed dominators in the MIR cfg cache.
Rebase of https://github.com/rust-lang/rust/pull/107157
cc `@tmiasko`
|
|
|
|
|
|
|
|
|
|
|
|
dominators.
|
|
Change the immediate_dominator return type to Option, and use None to
indicate that node has no immediate dominator.
Also fix the issue where the start node would be returned as its own
immediate dominator.
|
|
|
|
|
|
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.
|
