rustc_mir_dataflow/framework/
direction.rs

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