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 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 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 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
51pub 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 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 let next_effect = match from.effect {
151 _ 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 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 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 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
240pub 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 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 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 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 from == to {
354 return;
355 }
356
357 from.statement_index + 1
358 }
359 };
360
361 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 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}