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 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 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 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
52pub 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 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 let next_effect = match from.effect {
149 _ 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 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 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 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
238pub 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 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 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 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 from == to {
352 return;
353 }
354
355 from.statement_index + 1
356 }
357 };
358
359 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 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}