rustc_mir_dataflow/framework/
direction.rs

1use rustc_middle::mir::{self, BasicBlock, Location, TerminatorEdges};
2use rustc_span::bug;
3
4use super::visitor::ResultsVisitor;
5use super::{Analysis, Effect, EffectIndex, SwitchTargetIndex};
6
7pub trait Direction {
8    const IS_FORWARD: bool;
9    const IS_BACKWARD: bool = !Self::IS_FORWARD;
10
11    /// Returns the first statement index for this direction. (0 when going forward and
12    /// `statements.len()` when going backward.)
13    fn first_index(block_data: &mir::BasicBlockData<'_>) -> EffectIndex;
14
15    /// Returns the next index for this direction.
16    fn next_index(idx: EffectIndex) -> EffectIndex;
17
18    /// Called by `iterate_to_fixpoint` during initial analysis computation.
19    fn apply_effects_in_block<'mir, 'tcx, A>(
20        analysis: &A,
21        body: &mir::Body<'tcx>,
22        state: &mut A::Domain,
23        block: BasicBlock,
24        block_data: &'mir mir::BasicBlockData<'tcx>,
25        propagate: impl FnMut(BasicBlock, &A::Domain),
26    ) where
27        A: Analysis<'tcx>;
28
29    /// Called by `ResultsVisitor` to recompute the analysis domain values for
30    /// all locations in a basic block (starting from `entry_state` and to
31    /// visit them with `vis`.
32    fn visit_results_in_block<'mir, 'tcx, A>(
33        analysis: &A,
34        state: &mut A::Domain,
35        block: BasicBlock,
36        block_data: &'mir mir::BasicBlockData<'tcx>,
37        vis: &mut impl ResultsVisitor<'tcx, A>,
38    ) where
39        A: Analysis<'tcx>;
40}
41
42/// Dataflow that runs from the exit of a block (terminator), to its entry (the first statement).
43pub struct Backward;
44
45impl Direction for Backward {
46    const IS_FORWARD: bool = false;
47
48    fn first_index(block_data: &mir::BasicBlockData<'_>) -> EffectIndex {
49        Effect::Early.at_index(block_data.statements.len())
50    }
51
52    /// Returns the next index for this direction.
53    fn next_index(idx: EffectIndex) -> EffectIndex {
54        match idx.effect {
55            Effect::Early => Effect::Primary.at_index(idx.statement_index),
56            Effect::Primary => Effect::Early.at_index(idx.statement_index - 1),
57        }
58    }
59
60    fn apply_effects_in_block<'mir, 'tcx, A>(
61        analysis: &A,
62        body: &mir::Body<'tcx>,
63        state: &mut A::Domain,
64        block: BasicBlock,
65        block_data: &'mir mir::BasicBlockData<'tcx>,
66        mut propagate: impl FnMut(BasicBlock, &A::Domain),
67    ) where
68        A: Analysis<'tcx>,
69    {
70        let terminator = block_data.terminator();
71        let location = Location { block, statement_index: block_data.statements.len() };
72        analysis.apply_early_terminator_effect(state, terminator, location);
73        analysis.apply_primary_terminator_effect(state, terminator, location);
74        for (statement_index, statement) in block_data.statements.iter().enumerate().rev() {
75            let location = Location { block, statement_index };
76            analysis.apply_early_statement_effect(state, statement, location);
77            analysis.apply_primary_statement_effect(state, statement, location);
78        }
79
80        let exit_state = state;
81        for pred in body.basic_blocks.predecessors()[block].iter().copied() {
82            match body[pred].terminator().edges() {
83                // Apply terminator-specific edge effects.
84                TerminatorEdges::AssignOnReturn { return_, place, .. }
85                    if return_.contains(&block) =>
86                {
87                    let mut tmp = exit_state.clone();
88                    analysis.apply_call_return_effect(&mut tmp, pred, place);
89                    propagate(pred, &tmp);
90                }
91
92                TerminatorEdges::SwitchInt { targets, discr } => {
93                    if let Some(_data) = analysis.get_switch_int_data(pred, targets, discr) {
94                        ::rustc_span::macros::bug_impl(None,
    format_args!("SwitchInt edge effects are unsupported in backward dataflow analyses"),
    Location::caller());bug!(
95                            "SwitchInt edge effects are unsupported in backward dataflow analyses"
96                        );
97                    } else {
98                        propagate(pred, exit_state)
99                    }
100                }
101
102                _ => propagate(pred, exit_state),
103            }
104        }
105    }
106
107    fn visit_results_in_block<'mir, 'tcx, A>(
108        analysis: &A,
109        state: &mut A::Domain,
110        block: BasicBlock,
111        block_data: &'mir mir::BasicBlockData<'tcx>,
112        vis: &mut impl ResultsVisitor<'tcx, A>,
113    ) where
114        A: Analysis<'tcx>,
115    {
116        let loc = Location { block, statement_index: block_data.statements.len() };
117        let term = block_data.terminator();
118        analysis.apply_early_terminator_effect(state, term, loc);
119        vis.visit_after_early_terminator_effect(state, term, loc);
120        analysis.apply_primary_terminator_effect(state, term, loc);
121        vis.visit_after_primary_terminator_effect(state, term, loc);
122
123        for (statement_index, stmt) in block_data.statements.iter().enumerate().rev() {
124            let loc = Location { block, statement_index };
125            analysis.apply_early_statement_effect(state, stmt, loc);
126            vis.visit_after_early_statement_effect(state, stmt, loc);
127            analysis.apply_primary_statement_effect(state, stmt, loc);
128            vis.visit_after_primary_statement_effect(state, stmt, loc);
129        }
130
131        vis.visit_block_exit(state, block);
132    }
133}
134
135/// Dataflow that runs from the entry of a block (the first statement), to its exit (terminator).
136pub struct Forward;
137
138impl Direction for Forward {
139    const IS_FORWARD: bool = true;
140
141    fn first_index(_block_data: &mir::BasicBlockData<'_>) -> EffectIndex {
142        Effect::Early.at_index(0)
143    }
144
145    /// Returns the next index for this direction.
146    fn next_index(idx: EffectIndex) -> EffectIndex {
147        match idx.effect {
148            Effect::Early => Effect::Primary.at_index(idx.statement_index),
149            Effect::Primary => Effect::Early.at_index(idx.statement_index + 1),
150        }
151    }
152
153    fn apply_effects_in_block<'mir, 'tcx, A>(
154        analysis: &A,
155        body: &mir::Body<'tcx>,
156        state: &mut A::Domain,
157        block: BasicBlock,
158        block_data: &'mir mir::BasicBlockData<'tcx>,
159        mut propagate: impl FnMut(BasicBlock, &A::Domain),
160    ) where
161        A: Analysis<'tcx>,
162    {
163        for (statement_index, statement) in block_data.statements.iter().enumerate() {
164            let location = Location { block, statement_index };
165            analysis.apply_early_statement_effect(state, statement, location);
166            analysis.apply_primary_statement_effect(state, statement, location);
167        }
168        let terminator = block_data.terminator();
169        let location = Location { block, statement_index: block_data.statements.len() };
170        analysis.apply_early_terminator_effect(state, terminator, location);
171        // Edges are obtained *before* calling `apply_primary_terminator_effect`.
172        let edges = analysis.get_terminator_edges(state, terminator, location);
173        analysis.apply_primary_terminator_effect(state, terminator, location);
174
175        let exit_state = state;
176        match edges {
177            TerminatorEdges::None => {}
178            TerminatorEdges::Single(target) => propagate(target, exit_state),
179            TerminatorEdges::Double(target, unwind) => {
180                propagate(target, exit_state);
181                propagate(unwind, exit_state);
182            }
183            TerminatorEdges::AssignOnReturn { return_, cleanup, place } => {
184                // This must be done *first*, otherwise the unwind path will see the assignments.
185                if let Some(cleanup) = cleanup {
186                    propagate(cleanup, exit_state);
187                }
188
189                if !return_.is_empty() {
190                    analysis.apply_call_return_effect(exit_state, block, place);
191                    for target in return_ {
192                        propagate(target, exit_state);
193                    }
194                }
195            }
196            TerminatorEdges::SwitchInt { targets, discr } => {
197                if let Some(data) = analysis.get_switch_int_data(block, targets, discr) {
198                    let mut tmp = analysis.bottom_value(body);
199                    for (i, (_value, target)) in targets.iter().enumerate() {
200                        tmp.clone_from(exit_state);
201                        let target_idx = SwitchTargetIndex::Normal(i);
202                        analysis.apply_switch_int_edge_effect(&mut tmp, &data, target_idx);
203                        propagate(target, &tmp);
204                    }
205
206                    // Once we get to the final, "otherwise" branch, there is no need to preserve
207                    // `exit_state`, so pass it directly to `apply_switch_int_edge_effect` to save
208                    // a clone of the dataflow state.
209                    analysis.apply_switch_int_edge_effect(
210                        exit_state,
211                        &data,
212                        SwitchTargetIndex::Otherwise,
213                    );
214                    propagate(targets.otherwise(), exit_state);
215                } else {
216                    for target in targets.all_targets() {
217                        propagate(*target, exit_state);
218                    }
219                }
220            }
221        }
222    }
223
224    fn visit_results_in_block<'mir, 'tcx, A>(
225        analysis: &A,
226        state: &mut A::Domain,
227        block: BasicBlock,
228        block_data: &'mir mir::BasicBlockData<'tcx>,
229        vis: &mut impl ResultsVisitor<'tcx, A>,
230    ) where
231        A: Analysis<'tcx>,
232    {
233        for (statement_index, stmt) in block_data.statements.iter().enumerate() {
234            let loc = Location { block, statement_index };
235            analysis.apply_early_statement_effect(state, stmt, loc);
236            vis.visit_after_early_statement_effect(state, stmt, loc);
237            analysis.apply_primary_statement_effect(state, stmt, loc);
238            vis.visit_after_primary_statement_effect(state, stmt, loc);
239        }
240
241        let loc = Location { block, statement_index: block_data.statements.len() };
242        let term = block_data.terminator();
243        analysis.apply_early_terminator_effect(state, term, loc);
244        vis.visit_after_early_terminator_effect(state, term, loc);
245        analysis.apply_primary_terminator_effect(state, term, loc);
246        vis.visit_after_primary_terminator_effect(state, term, loc);
247
248        vis.visit_block_exit(state, block);
249    }
250}
rustc_mir_dataflow/framework/direction.rs

rustc_mir_dataflow/framework/
direction.rs
