rustc_mir_dataflow/framework/
direction.rs

1use std::ops::RangeInclusive;
2
3use rustc_middle::mir::{
4    self, BasicBlock, CallReturnPlaces, Location, SwitchTargetValue, TerminatorEdges,
5};
6
7use super::visitor::ResultsVisitor;
8use super::{Analysis, Effect, EffectIndex};
9
10pub trait Direction {
11    const IS_FORWARD: bool;
12    const IS_BACKWARD: bool = !Self::IS_FORWARD;
13
14    /// Called by `iterate_to_fixpoint` during initial analysis computation.
15    fn apply_effects_in_block<'mir, 'tcx, A>(
16        analysis: &mut A,
17        body: &mir::Body<'tcx>,
18        state: &mut A::Domain,
19        block: BasicBlock,
20        block_data: &'mir mir::BasicBlockData<'tcx>,
21        propagate: impl FnMut(BasicBlock, &A::Domain),
22    ) where
23        A: Analysis<'tcx>;
24
25    /// Called by `ResultsCursor` to recompute the domain value for a location
26    /// in a basic block. Applies all effects between the given `EffectIndex`s.
27    ///
28    /// `effects.start()` must precede or equal `effects.end()` in this direction.
29    fn apply_effects_in_range<'tcx, A>(
30        analysis: &mut A,
31        state: &mut A::Domain,
32        block: BasicBlock,
33        block_data: &mir::BasicBlockData<'tcx>,
34        effects: RangeInclusive<EffectIndex>,
35    ) where
36        A: Analysis<'tcx>;
37
38    /// Called by `ResultsVisitor` to recompute the analysis domain values for
39    /// all locations in a basic block (starting from `entry_state` and to
40    /// visit them with `vis`.
41    fn visit_results_in_block<'mir, 'tcx, A>(
42        state: &mut A::Domain,
43        block: BasicBlock,
44        block_data: &'mir mir::BasicBlockData<'tcx>,
45        analysis: &mut A,
46        vis: &mut impl ResultsVisitor<'tcx, A>,
47    ) where
48        A: Analysis<'tcx>;
49}
50
51/// Dataflow that runs from the exit of a block (terminator), to its entry (the first statement).
52pub struct Backward;
53
54impl Direction for Backward {
55    const IS_FORWARD: bool = false;
56
57    fn apply_effects_in_block<'mir, 'tcx, A>(
58        analysis: &mut A,
59        body: &mir::Body<'tcx>,
60        state: &mut A::Domain,
61        block: BasicBlock,
62        block_data: &'mir mir::BasicBlockData<'tcx>,
63        mut propagate: impl FnMut(BasicBlock, &A::Domain),
64    ) where
65        A: Analysis<'tcx>,
66    {
67        let terminator = block_data.terminator();
68        let location = Location { block, statement_index: block_data.statements.len() };
69        analysis.apply_early_terminator_effect(state, terminator, location);
70        analysis.apply_primary_terminator_effect(state, terminator, location);
71        for (statement_index, statement) in block_data.statements.iter().enumerate().rev() {
72            let location = Location { block, statement_index };
73            analysis.apply_early_statement_effect(state, statement, location);
74            analysis.apply_primary_statement_effect(state, statement, location);
75        }
76
77        let exit_state = state;
78        for pred in body.basic_blocks.predecessors()[block].iter().copied() {
79            match body[pred].terminator().kind {
80                // Apply terminator-specific edge effects.
81                mir::TerminatorKind::Call { destination, target: Some(dest), .. }
82                    if dest == block =>
83                {
84                    let mut tmp = exit_state.clone();
85                    analysis.apply_call_return_effect(
86                        &mut tmp,
87                        pred,
88                        CallReturnPlaces::Call(destination),
89                    );
90                    propagate(pred, &tmp);
91                }
92
93                mir::TerminatorKind::InlineAsm { ref targets, ref operands, .. }
94                    if targets.contains(&block) =>
95                {
96                    let mut tmp = exit_state.clone();
97                    analysis.apply_call_return_effect(
98                        &mut tmp,
99                        pred,
100                        CallReturnPlaces::InlineAsm(operands),
101                    );
102                    propagate(pred, &tmp);
103                }
104
105                mir::TerminatorKind::Yield { resume, resume_arg, .. } if resume == block => {
106                    let mut tmp = exit_state.clone();
107                    analysis.apply_call_return_effect(
108                        &mut tmp,
109                        resume,
110                        CallReturnPlaces::Yield(resume_arg),
111                    );
112                    propagate(pred, &tmp);
113                }
114
115                mir::TerminatorKind::SwitchInt { targets: _, ref discr } => {
116                    if let Some(mut data) = analysis.get_switch_int_data(block, discr) {
117                        let mut tmp = analysis.bottom_value(body);
118                        for &value in &body.basic_blocks.switch_sources()[&(block, pred)] {
119                            tmp.clone_from(exit_state);
120                            analysis.apply_switch_int_edge_effect(&mut data, &mut tmp, value);
121                            propagate(pred, &tmp);
122                        }
123                    } else {
124                        propagate(pred, exit_state)
125                    }
126                }
127
128                _ => propagate(pred, exit_state),
129            }
130        }
131    }
132
133    fn apply_effects_in_range<'tcx, A>(
134        analysis: &mut A,
135        state: &mut A::Domain,
136        block: BasicBlock,
137        block_data: &mir::BasicBlockData<'tcx>,
138        effects: RangeInclusive<EffectIndex>,
139    ) where
140        A: Analysis<'tcx>,
141    {
142        let (from, to) = (*effects.start(), *effects.end());
143        let terminator_index = block_data.statements.len();
144
145        assert!(from.statement_index <= terminator_index);
146        assert!(!to.precedes_in_backward_order(from));
147
148        // Handle the statement (or terminator) at `from`.
149
150        let next_effect = match from.effect {
151            // If we need to apply the terminator effect in all or in part, do so now.
152            _ if from.statement_index == terminator_index => {
153                let location = Location { block, statement_index: from.statement_index };
154                let terminator = block_data.terminator();
155
156                if from.effect == Effect::Early {
157                    analysis.apply_early_terminator_effect(state, terminator, location);
158                    if to == Effect::Early.at_index(terminator_index) {
159                        return;
160                    }
161                }
162
163                analysis.apply_primary_terminator_effect(state, terminator, location);
164                if to == Effect::Primary.at_index(terminator_index) {
165                    return;
166                }
167
168                // If `from.statement_index` is `0`, we will have hit one of the earlier comparisons
169                // with `to`.
170                from.statement_index - 1
171            }
172
173            Effect::Primary => {
174                let location = Location { block, statement_index: from.statement_index };
175                let statement = &block_data.statements[from.statement_index];
176
177                analysis.apply_primary_statement_effect(state, statement, location);
178                if to == Effect::Primary.at_index(from.statement_index) {
179                    return;
180                }
181
182                from.statement_index - 1
183            }
184
185            Effect::Early => from.statement_index,
186        };
187
188        // Handle all statements between `first_unapplied_idx` and `to.statement_index`.
189
190        for statement_index in (to.statement_index..next_effect).rev().map(|i| i + 1) {
191            let location = Location { block, statement_index };
192            let statement = &block_data.statements[statement_index];
193            analysis.apply_early_statement_effect(state, statement, location);
194            analysis.apply_primary_statement_effect(state, statement, location);
195        }
196
197        // Handle the statement at `to`.
198
199        let location = Location { block, statement_index: to.statement_index };
200        let statement = &block_data.statements[to.statement_index];
201        analysis.apply_early_statement_effect(state, statement, location);
202
203        if to.effect == Effect::Early {
204            return;
205        }
206
207        analysis.apply_primary_statement_effect(state, statement, location);
208    }
209
210    fn visit_results_in_block<'mir, 'tcx, A>(
211        state: &mut A::Domain,
212        block: BasicBlock,
213        block_data: &'mir mir::BasicBlockData<'tcx>,
214        analysis: &mut A,
215        vis: &mut impl ResultsVisitor<'tcx, A>,
216    ) where
217        A: Analysis<'tcx>,
218    {
219        vis.visit_block_end(state);
220
221        let loc = Location { block, statement_index: block_data.statements.len() };
222        let term = block_data.terminator();
223        analysis.apply_early_terminator_effect(state, term, loc);
224        vis.visit_after_early_terminator_effect(analysis, state, term, loc);
225        analysis.apply_primary_terminator_effect(state, term, loc);
226        vis.visit_after_primary_terminator_effect(analysis, state, term, loc);
227
228        for (statement_index, stmt) in block_data.statements.iter().enumerate().rev() {
229            let loc = Location { block, statement_index };
230            analysis.apply_early_statement_effect(state, stmt, loc);
231            vis.visit_after_early_statement_effect(analysis, state, stmt, loc);
232            analysis.apply_primary_statement_effect(state, stmt, loc);
233            vis.visit_after_primary_statement_effect(analysis, state, stmt, loc);
234        }
235
236        vis.visit_block_start(state);
237    }
238}
239
240/// Dataflow that runs from the entry of a block (the first statement), to its exit (terminator).
241pub struct Forward;
242
243impl Direction for Forward {
244    const IS_FORWARD: bool = true;
245
246    fn apply_effects_in_block<'mir, 'tcx, A>(
247        analysis: &mut A,
248        body: &mir::Body<'tcx>,
249        state: &mut A::Domain,
250        block: BasicBlock,
251        block_data: &'mir mir::BasicBlockData<'tcx>,
252        mut propagate: impl FnMut(BasicBlock, &A::Domain),
253    ) where
254        A: Analysis<'tcx>,
255    {
256        for (statement_index, statement) in block_data.statements.iter().enumerate() {
257            let location = Location { block, statement_index };
258            analysis.apply_early_statement_effect(state, statement, location);
259            analysis.apply_primary_statement_effect(state, statement, location);
260        }
261        let terminator = block_data.terminator();
262        let location = Location { block, statement_index: block_data.statements.len() };
263        analysis.apply_early_terminator_effect(state, terminator, location);
264        let edges = analysis.apply_primary_terminator_effect(state, terminator, location);
265
266        let exit_state = state;
267        match edges {
268            TerminatorEdges::None => {}
269            TerminatorEdges::Single(target) => propagate(target, exit_state),
270            TerminatorEdges::Double(target, unwind) => {
271                propagate(target, exit_state);
272                propagate(unwind, exit_state);
273            }
274            TerminatorEdges::AssignOnReturn { return_, cleanup, place } => {
275                // This must be done *first*, otherwise the unwind path will see the assignments.
276                if let Some(cleanup) = cleanup {
277                    propagate(cleanup, exit_state);
278                }
279
280                if !return_.is_empty() {
281                    analysis.apply_call_return_effect(exit_state, block, place);
282                    for &target in return_ {
283                        propagate(target, exit_state);
284                    }
285                }
286            }
287            TerminatorEdges::SwitchInt { targets, discr } => {
288                if let Some(mut data) = analysis.get_switch_int_data(block, discr) {
289                    let mut tmp = analysis.bottom_value(body);
290                    for (value, target) in targets.iter() {
291                        tmp.clone_from(exit_state);
292                        let value = SwitchTargetValue::Normal(value);
293                        analysis.apply_switch_int_edge_effect(&mut data, &mut tmp, value);
294                        propagate(target, &tmp);
295                    }
296
297                    // Once we get to the final, "otherwise" branch, there is no need to preserve
298                    // `exit_state`, so pass it directly to `apply_switch_int_edge_effect` to save
299                    // a clone of the dataflow state.
300                    let otherwise = targets.otherwise();
301                    analysis.apply_switch_int_edge_effect(
302                        &mut data,
303                        exit_state,
304                        SwitchTargetValue::Otherwise,
305                    );
306                    propagate(otherwise, exit_state);
307                } else {
308                    for target in targets.all_targets() {
309                        propagate(*target, exit_state);
310                    }
311                }
312            }
313        }
314    }
315
316    fn apply_effects_in_range<'tcx, A>(
317        analysis: &mut A,
318        state: &mut A::Domain,
319        block: BasicBlock,
320        block_data: &mir::BasicBlockData<'tcx>,
321        effects: RangeInclusive<EffectIndex>,
322    ) where
323        A: Analysis<'tcx>,
324    {
325        let (from, to) = (*effects.start(), *effects.end());
326        let terminator_index = block_data.statements.len();
327
328        assert!(to.statement_index <= terminator_index);
329        assert!(!to.precedes_in_forward_order(from));
330
331        // If we have applied the before affect of the statement or terminator at `from` but not its
332        // after effect, do so now and start the loop below from the next statement.
333
334        let first_unapplied_index = match from.effect {
335            Effect::Early => from.statement_index,
336
337            Effect::Primary if from.statement_index == terminator_index => {
338                debug_assert_eq!(from, to);
339
340                let location = Location { block, statement_index: terminator_index };
341                let terminator = block_data.terminator();
342                analysis.apply_primary_terminator_effect(state, terminator, location);
343                return;
344            }
345
346            Effect::Primary => {
347                let location = Location { block, statement_index: from.statement_index };
348                let statement = &block_data.statements[from.statement_index];
349                analysis.apply_primary_statement_effect(state, statement, location);
350
351                // If we only needed to apply the after effect of the statement at `idx`, we are
352                // done.
353                if from == to {
354                    return;
355                }
356
357                from.statement_index + 1
358            }
359        };
360
361        // Handle all statements between `from` and `to` whose effects must be applied in full.
362
363        for statement_index in first_unapplied_index..to.statement_index {
364            let location = Location { block, statement_index };
365            let statement = &block_data.statements[statement_index];
366            analysis.apply_early_statement_effect(state, statement, location);
367            analysis.apply_primary_statement_effect(state, statement, location);
368        }
369
370        // Handle the statement or terminator at `to`.
371
372        let location = Location { block, statement_index: to.statement_index };
373        if to.statement_index == terminator_index {
374            let terminator = block_data.terminator();
375            analysis.apply_early_terminator_effect(state, terminator, location);
376
377            if to.effect == Effect::Primary {
378                analysis.apply_primary_terminator_effect(state, terminator, location);
379            }
380        } else {
381            let statement = &block_data.statements[to.statement_index];
382            analysis.apply_early_statement_effect(state, statement, location);
383
384            if to.effect == Effect::Primary {
385                analysis.apply_primary_statement_effect(state, statement, location);
386            }
387        }
388    }
389
390    fn visit_results_in_block<'mir, 'tcx, A>(
391        state: &mut A::Domain,
392        block: BasicBlock,
393        block_data: &'mir mir::BasicBlockData<'tcx>,
394        analysis: &mut A,
395        vis: &mut impl ResultsVisitor<'tcx, A>,
396    ) where
397        A: Analysis<'tcx>,
398    {
399        vis.visit_block_start(state);
400
401        for (statement_index, stmt) in block_data.statements.iter().enumerate() {
402            let loc = Location { block, statement_index };
403            analysis.apply_early_statement_effect(state, stmt, loc);
404            vis.visit_after_early_statement_effect(analysis, state, stmt, loc);
405            analysis.apply_primary_statement_effect(state, stmt, loc);
406            vis.visit_after_primary_statement_effect(analysis, state, stmt, loc);
407        }
408
409        let loc = Location { block, statement_index: block_data.statements.len() };
410        let term = block_data.terminator();
411        analysis.apply_early_terminator_effect(state, term, loc);
412        vis.visit_after_early_terminator_effect(analysis, state, term, loc);
413        analysis.apply_primary_terminator_effect(state, term, loc);
414        vis.visit_after_primary_terminator_effect(analysis, state, term, loc);
415
416        vis.visit_block_end(state);
417    }
418}