rustc_mir_dataflow/framework/
direction.rs

1use rustc_middle::bug;
2use rustc_middle::mir::{self, BasicBlock, Location, TerminatorEdges};
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_middle::util::bug::bug_fmt(format_args!("SwitchInt edge effects are unsupported in backward dataflow analyses"));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}
132
133/// Dataflow that runs from the entry of a block (the first statement), to its exit (terminator).
134pub struct Forward;
135
136impl Direction for Forward {
137    const IS_FORWARD: bool = true;
138
139    fn first_index(_block_data: &mir::BasicBlockData<'_>) -> EffectIndex {
140        Effect::Early.at_index(0)
141    }
142
143    /// Returns the next index for this direction.
144    fn next_index(idx: EffectIndex) -> EffectIndex {
145        match idx.effect {
146            Effect::Early => Effect::Primary.at_index(idx.statement_index),
147            Effect::Primary => Effect::Early.at_index(idx.statement_index + 1),
148        }
149    }
150
151    fn apply_effects_in_block<'mir, 'tcx, A>(
152        analysis: &A,
153        body: &mir::Body<'tcx>,
154        state: &mut A::Domain,
155        block: BasicBlock,
156        block_data: &'mir mir::BasicBlockData<'tcx>,
157        mut propagate: impl FnMut(BasicBlock, &A::Domain),
158    ) where
159        A: Analysis<'tcx>,
160    {
161        for (statement_index, statement) in block_data.statements.iter().enumerate() {
162            let location = Location { block, statement_index };
163            analysis.apply_early_statement_effect(state, statement, location);
164            analysis.apply_primary_statement_effect(state, statement, location);
165        }
166        let terminator = block_data.terminator();
167        let location = Location { block, statement_index: block_data.statements.len() };
168        analysis.apply_early_terminator_effect(state, terminator, location);
169        // Edges are obtained *before* calling `apply_primary_terminator_effect`.
170        let edges = analysis.get_terminator_edges(state, terminator, location);
171        analysis.apply_primary_terminator_effect(state, terminator, location);
172
173        let exit_state = state;
174        match edges {
175            TerminatorEdges::None => {}
176            TerminatorEdges::Single(target) => propagate(target, exit_state),
177            TerminatorEdges::Double(target, unwind) => {
178                propagate(target, exit_state);
179                propagate(unwind, exit_state);
180            }
181            TerminatorEdges::AssignOnReturn { return_, cleanup, place } => {
182                // This must be done *first*, otherwise the unwind path will see the assignments.
183                if let Some(cleanup) = cleanup {
184                    propagate(cleanup, exit_state);
185                }
186
187                if !return_.is_empty() {
188                    analysis.apply_call_return_effect(exit_state, block, place);
189                    for target in return_ {
190                        propagate(target, exit_state);
191                    }
192                }
193            }
194            TerminatorEdges::SwitchInt { targets, discr } => {
195                if let Some(data) = analysis.get_switch_int_data(block, targets, discr) {
196                    let mut tmp = analysis.bottom_value(body);
197                    for (i, (_value, target)) in targets.iter().enumerate() {
198                        tmp.clone_from(exit_state);
199                        let target_idx = SwitchTargetIndex::Normal(i);
200                        analysis.apply_switch_int_edge_effect(&mut tmp, &data, target_idx);
201                        propagate(target, &tmp);
202                    }
203
204                    // Once we get to the final, "otherwise" branch, there is no need to preserve
205                    // `exit_state`, so pass it directly to `apply_switch_int_edge_effect` to save
206                    // a clone of the dataflow state.
207                    analysis.apply_switch_int_edge_effect(
208                        exit_state,
209                        &data,
210                        SwitchTargetIndex::Otherwise,
211                    );
212                    propagate(targets.otherwise(), exit_state);
213                } else {
214                    for target in targets.all_targets() {
215                        propagate(*target, exit_state);
216                    }
217                }
218            }
219        }
220    }
221
222    fn visit_results_in_block<'mir, 'tcx, A>(
223        analysis: &A,
224        state: &mut A::Domain,
225        block: BasicBlock,
226        block_data: &'mir mir::BasicBlockData<'tcx>,
227        vis: &mut impl ResultsVisitor<'tcx, A>,
228    ) where
229        A: Analysis<'tcx>,
230    {
231        for (statement_index, stmt) in block_data.statements.iter().enumerate() {
232            let loc = Location { block, statement_index };
233            analysis.apply_early_statement_effect(state, stmt, loc);
234            vis.visit_after_early_statement_effect(state, stmt, loc);
235            analysis.apply_primary_statement_effect(state, stmt, loc);
236            vis.visit_after_primary_statement_effect(state, stmt, loc);
237        }
238
239        let loc = Location { block, statement_index: block_data.statements.len() };
240        let term = block_data.terminator();
241        analysis.apply_early_terminator_effect(state, term, loc);
242        vis.visit_after_early_terminator_effect(state, term, loc);
243        analysis.apply_primary_terminator_effect(state, term, loc);
244        vis.visit_after_primary_terminator_effect(state, term, loc);
245    }
246}
rustc_mir_dataflow/framework/direction.rs

rustc_mir_dataflow/framework/
direction.rs
