about summary refs log tree commit diff
path: root/compiler/rustc_data_structures/src/graph
AgeCommit message (Collapse)AuthorLines
2024-05-08Remove `extern crate tracing`.Nicholas Nethercote-0/+3
`use` is a nicer way of doing things.
2024-04-18Add tests for predecessor-aware `VecGraph` modeMaybe Waffle-0/+33
2024-04-15Add `graph::depth_first_search_as_undirected`Maybe Waffle-0/+26
2024-04-15Make `graph::DepthFirstSearch` accept `G` by valueMaybe Waffle-13/+13
It's required for the next commit. Note that you can still have `G = &H`, since there are implementations of all the graph traits for references.
2024-04-15Add an opt-in to store incoming edges in `VecGraph` + some docsMaybe Waffle-56/+192
2024-04-15Rollup merge of #123934 - WaffleLapkin:graph-mini-refactor, r=fmease许杰友 Jieyou Xu (Joe)-126/+59
`rustc_data_structures::graph` mini refactor Who doesn't love to breathe dust from the ancient times?
2024-04-15Use RPITIT for `Successors` and `Predecessors` traitsMaybe Waffle-30/+8
Now with RPITIT instead of GAT!
2024-04-14Make `depth_first_search` into a standalone functionMaybe Waffle-5/+10
Does not necessarily change much, but we never overwrite it, so I see no reason for it to be in the `Successors` trait. (+we already have a similar `is_cyclic`)
2024-04-14Document `ControlFlowGraph`Maybe Waffle-4/+2
2024-04-14Rename `WithNumEdges` => `NumEdges` and `WithStartNode` => `StartNode`Maybe Waffle-16/+16
2024-04-14Merge `{With,Graph}{Successors,Predecessors}` into `{Successors,Predecessors}`Maybe Waffle-88/+53
Now with GAT!
2024-04-14Merge `WithNumNodes` into DirectedGraphMaybe Waffle-40/+27
2024-04-03rustc_index: Add a `ZERO` constant to index typesVadim Petrochenkov-4/+4
It is commonly used.
2023-12-31Inline dominator check.Camille GILLOT-0/+1
2023-12-10remove redundant importssurechen-1/+0
detects redundant imports that can be eliminated. for #117772 : In order to facilitate review and modification, split the checking code and removing redundant imports code into two PR.
2023-11-28Avoid an unnecessary `by_ref`.Nicholas Nethercote-1/+1
2023-11-22Replace `no_ord_impl` with `orderable`.Nicholas Nethercote-0/+1
Similar to the previous commit, this replaces `newtype_index`'s opt-out `no_ord_impl` attribute with the opt-in `orderable` attribute.
2023-10-10Remove unused dominator iteratorTomasz Miąsko-26/+1
2023-10-05Optimize dominators for small path graphsTomasz Miąsko-10/+65
Generalizes the small dominators approach from #107449.
2023-10-05Remove redundant Dominators::start_node fieldTomasz Miąsko-3/+2
2023-10-05Test immediate dominators using public APITomasz Miąsko-24/+21
2023-09-18coverage: Simplify sorting of coverage spans extracted from MIRZalathar-3/+3
Switching to `Ordering::then_with` makes control-flow less complicated, and there is no need to use `partial_cmp` here.
2023-08-28don't use SnapshotVec in Graph implementation, as it looks unused; use Vec ↵klensy-19/+4
instead
2023-07-12Re-format let-else per rustfmt updateMark Rousskov-3/+1
2023-05-24Auto merge of #111673 - cjgillot:dominator-preprocess, r=cjgillot,tmiaskobors-10/+85
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`
2023-05-18Revert spurious changes.Camille GILLOT-9/+9
2023-05-17Merge DominatorTree and Dominators.Camille GILLOT-36/+30
2023-05-17Typo.Camille GILLOT-1/+1
2023-05-17Remove outdated comment.Camille GILLOT-2/+0
2023-05-17Preprocess dominator tree to answer queries in O(1)Tomasz Miąsko-22/+105
2023-05-15Process current bucket instead of parent's bucket when starting loop for ↵Camille GILLOT-8/+35
dominators.
2023-05-14Start node has no immediate dominatorTomasz Miąsko-14/+22
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.
2023-04-24Split `{Idx, IndexVec, IndexSlice}` into their own modulesMaybe Waffle-5/+6
2023-04-09Fix some clippy::complexityNilstrieb-8/+2
2023-04-02Use `&IndexSlice` instead of `&IndexVec` where possibleScott McMurray-12/+12
All the same reasons as for `[T]`: more general, less pointer chasing, and `&mut IndexSlice` emphasizes that it doesn't change *length*.
2023-03-21Add `-Z time-passes-format` to allow specifying a JSON output for `-Z ↵John Kåre Alsaker-6/+6
time-passes`
2023-02-21address reviewb-naber-4/+20
2023-02-19sccs infob-naber-5/+5
2023-01-24Improve efficiency of has_back_edge(...)Bryan Garza-0/+7
2023-01-23Add comment on cause of panic in dominators algorithmBryan Garza-1/+41
2023-01-23Rollup merge of #107153 - tmiasko:dominates, r=oli-obkYuki Okushi-1/+1
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.
2023-01-21Consistently use dominates instead of is_dominated_byTomasz Miąsko-1/+1
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.
2023-01-21Auto merge of #106976 - tmiasko:borrowck-lazy-dominators, r=cjgillotbors-4/+0
Lazy dominator tree construction in borrowck Motivated by the observation that sometimes constructed dominator tree was never queried.
2023-01-20Auto merge of #106090 - WaffleLapkin:dereffffffffff, r=Nilstriebbors-4/+4
Remove some `ref` patterns from the compiler Previous PR: https://github.com/rust-lang/rust/pull/105368 r? `@Nilstrieb`
2023-01-19Rollup merge of #107037 - tmiasko:rank, r=oli-obkGuillaume Gomez-1/+1
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.
2023-01-18Fix Dominators::rank_partial_cmp to match documentationTomasz Miąsko-1/+1
The only use site is also updated accordingly and there is no change in end-to-end behaviour.
2023-01-17Stop using `BREAK` & `CONTINUE` in compilerScott McMurray-4/+4
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.
2023-01-17Lazy dominator tree construction in borrowckTomasz Miąsko-4/+0
Motivated by the observation that sometimes constructed dominator tree was never queried.
2023-01-17Rollup merge of #104505 - WaffleLapkin:no-double-spaces-in-comments, r=jackh726Matthias Krüger-1/+1
Remove double spaces after dots in comments Most of the comments do not have double spaces, so I assume these are typos.
2023-01-17Remove double spaces after dots in commentsMaybe Waffle-1/+1
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-23 09:01:16 +0000