rustc_middle/mir/
basic_blocks.rs

1use std::sync::OnceLock;
2
3use rustc_data_structures::graph;
4use rustc_data_structures::graph::dominators::{Dominators, dominators};
5use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
6use rustc_index::{IndexSlice, IndexVec};
7use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
8use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
9use smallvec::SmallVec;
10
11use crate::mir::traversal::Postorder;
12use crate::mir::{BasicBlock, BasicBlockData, START_BLOCK};
13
14#[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable, TypeFoldable, TypeVisitable)]
15pub struct BasicBlocks<'tcx> {
16    basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
17    cache: Cache,
18}
19
20// Typically 95%+ of basic blocks have 4 or fewer predecessors.
21type Predecessors = IndexVec<BasicBlock, SmallVec<[BasicBlock; 4]>>;
22
23#[derive(Debug, Clone, Copy)]
24pub enum SwitchTargetValue {
25    // A normal switch value.
26    Normal(u128),
27    // The final "otherwise" fallback value.
28    Otherwise,
29}
30
31#[derive(Clone, Default, Debug)]
32struct Cache {
33    predecessors: OnceLock<Predecessors>,
34    reverse_postorder: OnceLock<Vec<BasicBlock>>,
35    dominators: OnceLock<Dominators<BasicBlock>>,
36}
37
38impl<'tcx> BasicBlocks<'tcx> {
39    #[inline]
40    pub fn new(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>) -> Self {
41        BasicBlocks { basic_blocks, cache: Cache::default() }
42    }
43
44    pub fn dominators(&self) -> &Dominators<BasicBlock> {
45        self.cache.dominators.get_or_init(|| dominators(self))
46    }
47
48    /// Returns predecessors for each basic block.
49    #[inline]
50    pub fn predecessors(&self) -> &Predecessors {
51        self.cache.predecessors.get_or_init(|| {
52            let mut preds = IndexVec::from_elem(SmallVec::new(), &self.basic_blocks);
53            for (bb, data) in self.basic_blocks.iter_enumerated() {
54                if let Some(term) = &data.terminator {
55                    for succ in term.successors() {
56                        preds[succ].push(bb);
57                    }
58                }
59            }
60            preds
61        })
62    }
63
64    /// Returns basic blocks in a reverse postorder.
65    ///
66    /// See [`traversal::reverse_postorder`]'s docs to learn what is preorder traversal.
67    ///
68    /// [`traversal::reverse_postorder`]: crate::mir::traversal::reverse_postorder
69    #[inline]
70    pub fn reverse_postorder(&self) -> &[BasicBlock] {
71        self.cache.reverse_postorder.get_or_init(|| {
72            let mut rpo: Vec<_> = Postorder::new(&self.basic_blocks, START_BLOCK, None).collect();
73            rpo.reverse();
74            rpo
75        })
76    }
77
78    /// Returns mutable reference to basic blocks. Invalidates CFG cache.
79    #[inline]
80    pub fn as_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
81        self.invalidate_cfg_cache();
82        &mut self.basic_blocks
83    }
84
85    /// Get mutable access to basic blocks without invalidating the CFG cache.
86    ///
87    /// By calling this method instead of e.g. [`BasicBlocks::as_mut`] you promise not to change
88    /// the CFG. This means that
89    ///
90    ///  1) The number of basic blocks remains unchanged
91    ///  2) The set of successors of each terminator remains unchanged.
92    ///  3) For each `TerminatorKind::SwitchInt`, the `targets` remains the same and the terminator
93    ///     kind is not changed.
94    ///
95    /// If any of these conditions cannot be upheld, you should call [`BasicBlocks::invalidate_cfg_cache`].
96    #[inline]
97    pub fn as_mut_preserves_cfg(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
98        &mut self.basic_blocks
99    }
100
101    /// Invalidates cached information about the CFG.
102    ///
103    /// You will only ever need this if you have also called [`BasicBlocks::as_mut_preserves_cfg`].
104    /// All other methods that allow you to mutate the basic blocks also call this method
105    /// themselves, thereby avoiding any risk of accidentally cache invalidation.
106    pub fn invalidate_cfg_cache(&mut self) {
107        self.cache = Cache::default();
108    }
109}
110
111impl<'tcx> std::ops::Deref for BasicBlocks<'tcx> {
112    type Target = IndexSlice<BasicBlock, BasicBlockData<'tcx>>;
113
114    #[inline]
115    fn deref(&self) -> &IndexSlice<BasicBlock, BasicBlockData<'tcx>> {
116        &self.basic_blocks
117    }
118}
119
120impl<'tcx> graph::DirectedGraph for BasicBlocks<'tcx> {
121    type Node = BasicBlock;
122
123    #[inline]
124    fn num_nodes(&self) -> usize {
125        self.basic_blocks.len()
126    }
127}
128
129impl<'tcx> graph::StartNode for BasicBlocks<'tcx> {
130    #[inline]
131    fn start_node(&self) -> Self::Node {
132        START_BLOCK
133    }
134}
135
136impl<'tcx> graph::Successors for BasicBlocks<'tcx> {
137    #[inline]
138    fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
139        self.basic_blocks[node].terminator().successors()
140    }
141}
142
143impl<'tcx> graph::Predecessors for BasicBlocks<'tcx> {
144    #[inline]
145    fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
146        self.predecessors()[node].iter().copied()
147    }
148}
149
150// Done here instead of in `structural_impls.rs` because `Cache` is private, as is `basic_blocks`.
151TrivialTypeTraversalImpls! { Cache }
152
153impl<S: Encoder> Encodable<S> for Cache {
154    #[inline]
155    fn encode(&self, _s: &mut S) {}
156}
157
158impl<D: Decoder> Decodable<D> for Cache {
159    #[inline]
160    fn decode(_: &mut D) -> Self {
161        Default::default()
162    }
163}
164
165impl<CTX> HashStable<CTX> for Cache {
166    #[inline]
167    fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {}
168}
rustc_middle/mir/basic_blocks.rs

rustc_middle/mir/
basic_blocks.rs
