]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
1 | //! A framework that can express both [gen-kill] and generic dataflow problems. |
2 | //! | |
ba9703b0 XL |
3 | //! To actually use this framework, you must implement either the `Analysis` or the |
4 | //! `GenKillAnalysis` trait. If your transfer function can be expressed with only gen/kill | |
5 | //! operations, prefer `GenKillAnalysis` since it will run faster while iterating to fixpoint. The | |
6 | //! `impls` module contains several examples of gen/kill dataflow analyses. | |
dfeec247 | 7 | //! |
ba9703b0 XL |
8 | //! Create an `Engine` for your analysis using the `into_engine` method on the `Analysis` trait, |
9 | //! then call `iterate_to_fixpoint`. From there, you can use a `ResultsCursor` to inspect the | |
10 | //! fixpoint solution to your dataflow problem, or implement the `ResultsVisitor` interface and use | |
11 | //! `visit_results`. The following example uses the `ResultsCursor` approach. | |
dfeec247 | 12 | //! |
6a06907d | 13 | //! ```ignore (cross-crate-imports) |
ba9703b0 | 14 | //! use rustc_mir::dataflow::Analysis; // Makes `into_engine` available. |
dfeec247 | 15 | //! |
29967ef6 | 16 | //! fn do_my_analysis(tcx: TyCtxt<'tcx>, body: &mir::Body<'tcx>) { |
ba9703b0 | 17 | //! let analysis = MyAnalysis::new() |
29967ef6 | 18 | //! .into_engine(tcx, body) |
ba9703b0 XL |
19 | //! .iterate_to_fixpoint() |
20 | //! .into_results_cursor(body); | |
dfeec247 | 21 | //! |
ba9703b0 | 22 | //! // Print the dataflow state *after* each statement in the start block. |
dfeec247 XL |
23 | //! for (_, statement_index) in body.block_data[START_BLOCK].statements.iter_enumerated() { |
24 | //! cursor.seek_after(Location { block: START_BLOCK, statement_index }); | |
25 | //! let state = cursor.get(); | |
26 | //! println!("{:?}", state); | |
27 | //! } | |
28 | //! } | |
29 | //! ``` | |
30 | //! | |
31 | //! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems | |
dfeec247 | 32 | |
1b1a35ee | 33 | use std::borrow::BorrowMut; |
f9f354fc | 34 | use std::cmp::Ordering; |
dfeec247 | 35 | |
dfeec247 | 36 | use rustc_index::bit_set::{BitSet, HybridBitSet}; |
f9f354fc | 37 | use rustc_index::vec::Idx; |
ba9703b0 | 38 | use rustc_middle::mir::{self, BasicBlock, Location}; |
1b1a35ee | 39 | use rustc_middle::ty::TyCtxt; |
dfeec247 XL |
40 | |
41 | mod cursor; | |
f9f354fc | 42 | mod direction; |
dfeec247 | 43 | mod engine; |
1b1a35ee | 44 | pub mod fmt; |
94222f64 | 45 | pub mod graphviz; |
1b1a35ee | 46 | pub mod lattice; |
74b04a01 | 47 | mod visitor; |
dfeec247 XL |
48 | |
49 | pub use self::cursor::{ResultsCursor, ResultsRefCursor}; | |
f9f354fc XL |
50 | pub use self::direction::{Backward, Direction, Forward}; |
51 | pub use self::engine::{Engine, Results}; | |
1b1a35ee | 52 | pub use self::lattice::{JoinSemiLattice, MeetSemiLattice}; |
74b04a01 XL |
53 | pub use self::visitor::{visit_results, ResultsVisitor}; |
54 | pub use self::visitor::{BorrowckFlowState, BorrowckResults}; | |
dfeec247 | 55 | |
dfeec247 XL |
56 | /// Define the domain of a dataflow problem. |
57 | /// | |
1b1a35ee XL |
58 | /// This trait specifies the lattice on which this analysis operates (the domain) as well as its |
59 | /// initial value at the entry point of each basic block. | |
60 | pub trait AnalysisDomain<'tcx> { | |
61 | /// The type that holds the dataflow state at any given point in the program. | |
62 | type Domain: Clone + JoinSemiLattice; | |
dfeec247 | 63 | |
1b1a35ee | 64 | /// The direction of this analysis. Either `Forward` or `Backward`. |
f9f354fc XL |
65 | type Direction: Direction = Forward; |
66 | ||
dfeec247 XL |
67 | /// A descriptive name for this analysis. Used only for debugging. |
68 | /// | |
69 | /// This name should be brief and contain no spaces, periods or other characters that are not | |
70 | /// suitable as part of a filename. | |
71 | const NAME: &'static str; | |
72 | ||
1b1a35ee XL |
73 | /// The initial value of the dataflow state upon entry to each basic block. |
74 | fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain; | |
dfeec247 | 75 | |
1b1a35ee | 76 | /// Mutates the initial value of the dataflow state upon entry to the `START_BLOCK`. |
f9f354fc XL |
77 | /// |
78 | /// For backward analyses, initial state besides the bottom value is not yet supported. Trying | |
79 | /// to mutate the initial state will result in a panic. | |
80 | // | |
81 | // FIXME: For backward dataflow analyses, the initial state should be applied to every basic | |
82 | // block where control flow could exit the MIR body (e.g., those terminated with `return` or | |
83 | // `resume`). It's not obvious how to handle `yield` points in generators, however. | |
1b1a35ee | 84 | fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain); |
dfeec247 XL |
85 | } |
86 | ||
87 | /// A dataflow problem with an arbitrarily complex transfer function. | |
1b1a35ee XL |
88 | /// |
89 | /// # Convergence | |
90 | /// | |
91 | /// When implementing this trait directly (not via [`GenKillAnalysis`]), it's possible to choose a | |
92 | /// transfer function such that the analysis does not reach fixpoint. To guarantee convergence, | |
93 | /// your transfer functions must maintain the following invariant: | |
94 | /// | |
95 | /// > If the dataflow state **before** some point in the program changes to be greater | |
96 | /// than the prior state **before** that point, the dataflow state **after** that point must | |
97 | /// also change to be greater than the prior state **after** that point. | |
98 | /// | |
99 | /// This invariant guarantees that the dataflow state at a given point in the program increases | |
100 | /// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies | |
101 | /// to the same point in the program at different points in time. The dataflow state at a given | |
102 | /// point in the program may or may not be greater than the state at any preceding point. | |
dfeec247 XL |
103 | pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { |
104 | /// Updates the current dataflow state with the effect of evaluating a statement. | |
105 | fn apply_statement_effect( | |
106 | &self, | |
1b1a35ee | 107 | state: &mut Self::Domain, |
dfeec247 XL |
108 | statement: &mir::Statement<'tcx>, |
109 | location: Location, | |
110 | ); | |
111 | ||
112 | /// Updates the current dataflow state with an effect that occurs immediately *before* the | |
113 | /// given statement. | |
114 | /// | |
115 | /// This method is useful if the consumer of the results of this analysis needs only to observe | |
116 | /// *part* of the effect of a statement (e.g. for two-phase borrows). As a general rule, | |
117 | /// analyses should not implement this without implementing `apply_statement_effect`. | |
118 | fn apply_before_statement_effect( | |
119 | &self, | |
1b1a35ee | 120 | _state: &mut Self::Domain, |
dfeec247 XL |
121 | _statement: &mir::Statement<'tcx>, |
122 | _location: Location, | |
123 | ) { | |
124 | } | |
125 | ||
126 | /// Updates the current dataflow state with the effect of evaluating a terminator. | |
127 | /// | |
128 | /// The effect of a successful return from a `Call` terminator should **not** be accounted for | |
129 | /// in this function. That should go in `apply_call_return_effect`. For example, in the | |
130 | /// `InitializedPlaces` analyses, the return place for a function call is not marked as | |
131 | /// initialized here. | |
132 | fn apply_terminator_effect( | |
133 | &self, | |
1b1a35ee | 134 | state: &mut Self::Domain, |
dfeec247 XL |
135 | terminator: &mir::Terminator<'tcx>, |
136 | location: Location, | |
137 | ); | |
138 | ||
139 | /// Updates the current dataflow state with an effect that occurs immediately *before* the | |
140 | /// given terminator. | |
141 | /// | |
142 | /// This method is useful if the consumer of the results of this analysis needs only to observe | |
143 | /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule, | |
144 | /// analyses should not implement this without implementing `apply_terminator_effect`. | |
145 | fn apply_before_terminator_effect( | |
146 | &self, | |
1b1a35ee | 147 | _state: &mut Self::Domain, |
dfeec247 XL |
148 | _terminator: &mir::Terminator<'tcx>, |
149 | _location: Location, | |
150 | ) { | |
151 | } | |
152 | ||
1b1a35ee XL |
153 | /* Edge-specific effects */ |
154 | ||
dfeec247 XL |
155 | /// Updates the current dataflow state with the effect of a successful return from a `Call` |
156 | /// terminator. | |
157 | /// | |
158 | /// This is separate from `apply_terminator_effect` to properly track state across unwind | |
159 | /// edges. | |
160 | fn apply_call_return_effect( | |
161 | &self, | |
1b1a35ee | 162 | state: &mut Self::Domain, |
dfeec247 XL |
163 | block: BasicBlock, |
164 | func: &mir::Operand<'tcx>, | |
165 | args: &[mir::Operand<'tcx>], | |
ba9703b0 | 166 | return_place: mir::Place<'tcx>, |
dfeec247 | 167 | ); |
74b04a01 | 168 | |
ba9703b0 XL |
169 | /// Updates the current dataflow state with the effect of resuming from a `Yield` terminator. |
170 | /// | |
171 | /// This is similar to `apply_call_return_effect` in that it only takes place after the | |
172 | /// generator is resumed, not when it is dropped. | |
173 | /// | |
174 | /// By default, no effects happen. | |
175 | fn apply_yield_resume_effect( | |
176 | &self, | |
1b1a35ee | 177 | _state: &mut Self::Domain, |
ba9703b0 XL |
178 | _resume_block: BasicBlock, |
179 | _resume_place: mir::Place<'tcx>, | |
180 | ) { | |
181 | } | |
182 | ||
74b04a01 XL |
183 | /// Updates the current dataflow state with the effect of taking a particular branch in a |
184 | /// `SwitchInt` terminator. | |
185 | /// | |
1b1a35ee XL |
186 | /// Unlike the other edge-specific effects, which are allowed to mutate `Self::Domain` |
187 | /// directly, overriders of this method must pass a callback to | |
188 | /// `SwitchIntEdgeEffects::apply`. The callback will be run once for each outgoing edge and | |
189 | /// will have access to the dataflow state that will be propagated along that edge. | |
190 | /// | |
191 | /// This interface is somewhat more complex than the other visitor-like "effect" methods. | |
192 | /// However, it is both more ergonomic—callers don't need to recompute or cache information | |
193 | /// about a given `SwitchInt` terminator for each one of its edges—and more efficient—the | |
194 | /// engine doesn't need to clone the exit state for a block unless | |
195 | /// `SwitchIntEdgeEffects::apply` is actually called. | |
f9f354fc XL |
196 | /// |
197 | /// FIXME: This class of effects is not supported for backward dataflow analyses. | |
1b1a35ee | 198 | fn apply_switch_int_edge_effects( |
74b04a01 | 199 | &self, |
74b04a01 | 200 | _block: BasicBlock, |
1b1a35ee XL |
201 | _discr: &mir::Operand<'tcx>, |
202 | _apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>, | |
74b04a01 XL |
203 | ) { |
204 | } | |
205 | ||
1b1a35ee XL |
206 | /* Extension methods */ |
207 | ||
74b04a01 XL |
208 | /// Creates an `Engine` to find the fixpoint for this dataflow problem. |
209 | /// | |
210 | /// You shouldn't need to override this outside this module, since the combination of the | |
211 | /// default impl and the one for all `A: GenKillAnalysis` will do the right thing. | |
212 | /// Its purpose is to enable method chaining like so: | |
213 | /// | |
6a06907d | 214 | /// ```ignore (cross-crate-imports) |
74b04a01 XL |
215 | /// let results = MyAnalysis::new(tcx, body) |
216 | /// .into_engine(tcx, body, def_id) | |
217 | /// .iterate_to_fixpoint() | |
218 | /// .into_results_cursor(body); | |
219 | /// ``` | |
29967ef6 | 220 | fn into_engine(self, tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>) -> Engine<'mir, 'tcx, Self> |
74b04a01 XL |
221 | where |
222 | Self: Sized, | |
223 | { | |
29967ef6 | 224 | Engine::new_generic(tcx, body, self) |
74b04a01 | 225 | } |
dfeec247 XL |
226 | } |
227 | ||
228 | /// A gen/kill dataflow problem. | |
229 | /// | |
230 | /// Each method in this trait has a corresponding one in `Analysis`. However, these methods only | |
231 | /// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer | |
232 | /// functions for each statement in this way, the transfer function for an entire basic block can | |
233 | /// be computed efficiently. | |
234 | /// | |
235 | /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`. | |
236 | pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> { | |
1b1a35ee XL |
237 | type Idx: Idx; |
238 | ||
dfeec247 XL |
239 | /// See `Analysis::apply_statement_effect`. |
240 | fn statement_effect( | |
241 | &self, | |
242 | trans: &mut impl GenKill<Self::Idx>, | |
243 | statement: &mir::Statement<'tcx>, | |
244 | location: Location, | |
245 | ); | |
246 | ||
247 | /// See `Analysis::apply_before_statement_effect`. | |
248 | fn before_statement_effect( | |
249 | &self, | |
250 | _trans: &mut impl GenKill<Self::Idx>, | |
251 | _statement: &mir::Statement<'tcx>, | |
252 | _location: Location, | |
253 | ) { | |
254 | } | |
255 | ||
256 | /// See `Analysis::apply_terminator_effect`. | |
257 | fn terminator_effect( | |
258 | &self, | |
259 | trans: &mut impl GenKill<Self::Idx>, | |
260 | terminator: &mir::Terminator<'tcx>, | |
261 | location: Location, | |
262 | ); | |
263 | ||
264 | /// See `Analysis::apply_before_terminator_effect`. | |
265 | fn before_terminator_effect( | |
266 | &self, | |
267 | _trans: &mut impl GenKill<Self::Idx>, | |
268 | _terminator: &mir::Terminator<'tcx>, | |
269 | _location: Location, | |
270 | ) { | |
271 | } | |
272 | ||
1b1a35ee XL |
273 | /* Edge-specific effects */ |
274 | ||
dfeec247 XL |
275 | /// See `Analysis::apply_call_return_effect`. |
276 | fn call_return_effect( | |
277 | &self, | |
278 | trans: &mut impl GenKill<Self::Idx>, | |
279 | block: BasicBlock, | |
280 | func: &mir::Operand<'tcx>, | |
281 | args: &[mir::Operand<'tcx>], | |
ba9703b0 | 282 | return_place: mir::Place<'tcx>, |
dfeec247 | 283 | ); |
74b04a01 | 284 | |
ba9703b0 XL |
285 | /// See `Analysis::apply_yield_resume_effect`. |
286 | fn yield_resume_effect( | |
287 | &self, | |
f9f354fc | 288 | _trans: &mut impl GenKill<Self::Idx>, |
ba9703b0 XL |
289 | _resume_block: BasicBlock, |
290 | _resume_place: mir::Place<'tcx>, | |
291 | ) { | |
292 | } | |
293 | ||
1b1a35ee XL |
294 | /// See `Analysis::apply_switch_int_edge_effects`. |
295 | fn switch_int_edge_effects<G: GenKill<Self::Idx>>( | |
74b04a01 | 296 | &self, |
74b04a01 | 297 | _block: BasicBlock, |
1b1a35ee XL |
298 | _discr: &mir::Operand<'tcx>, |
299 | _edge_effects: &mut impl SwitchIntEdgeEffects<G>, | |
74b04a01 XL |
300 | ) { |
301 | } | |
dfeec247 XL |
302 | } |
303 | ||
304 | impl<A> Analysis<'tcx> for A | |
305 | where | |
306 | A: GenKillAnalysis<'tcx>, | |
1b1a35ee | 307 | A::Domain: GenKill<A::Idx> + BorrowMut<BitSet<A::Idx>>, |
dfeec247 XL |
308 | { |
309 | fn apply_statement_effect( | |
310 | &self, | |
1b1a35ee | 311 | state: &mut A::Domain, |
dfeec247 XL |
312 | statement: &mir::Statement<'tcx>, |
313 | location: Location, | |
314 | ) { | |
315 | self.statement_effect(state, statement, location); | |
316 | } | |
317 | ||
318 | fn apply_before_statement_effect( | |
319 | &self, | |
1b1a35ee | 320 | state: &mut A::Domain, |
dfeec247 XL |
321 | statement: &mir::Statement<'tcx>, |
322 | location: Location, | |
323 | ) { | |
324 | self.before_statement_effect(state, statement, location); | |
325 | } | |
326 | ||
327 | fn apply_terminator_effect( | |
328 | &self, | |
1b1a35ee | 329 | state: &mut A::Domain, |
dfeec247 XL |
330 | terminator: &mir::Terminator<'tcx>, |
331 | location: Location, | |
332 | ) { | |
333 | self.terminator_effect(state, terminator, location); | |
334 | } | |
335 | ||
336 | fn apply_before_terminator_effect( | |
337 | &self, | |
1b1a35ee | 338 | state: &mut A::Domain, |
dfeec247 XL |
339 | terminator: &mir::Terminator<'tcx>, |
340 | location: Location, | |
341 | ) { | |
342 | self.before_terminator_effect(state, terminator, location); | |
343 | } | |
344 | ||
1b1a35ee XL |
345 | /* Edge-specific effects */ |
346 | ||
dfeec247 XL |
347 | fn apply_call_return_effect( |
348 | &self, | |
1b1a35ee | 349 | state: &mut A::Domain, |
dfeec247 XL |
350 | block: BasicBlock, |
351 | func: &mir::Operand<'tcx>, | |
352 | args: &[mir::Operand<'tcx>], | |
ba9703b0 | 353 | return_place: mir::Place<'tcx>, |
dfeec247 XL |
354 | ) { |
355 | self.call_return_effect(state, block, func, args, return_place); | |
356 | } | |
74b04a01 | 357 | |
ba9703b0 XL |
358 | fn apply_yield_resume_effect( |
359 | &self, | |
1b1a35ee | 360 | state: &mut A::Domain, |
ba9703b0 XL |
361 | resume_block: BasicBlock, |
362 | resume_place: mir::Place<'tcx>, | |
363 | ) { | |
364 | self.yield_resume_effect(state, resume_block, resume_place); | |
365 | } | |
366 | ||
1b1a35ee | 367 | fn apply_switch_int_edge_effects( |
74b04a01 | 368 | &self, |
74b04a01 | 369 | block: BasicBlock, |
1b1a35ee XL |
370 | discr: &mir::Operand<'tcx>, |
371 | edge_effects: &mut impl SwitchIntEdgeEffects<A::Domain>, | |
74b04a01 | 372 | ) { |
1b1a35ee | 373 | self.switch_int_edge_effects(block, discr, edge_effects); |
74b04a01 XL |
374 | } |
375 | ||
1b1a35ee XL |
376 | /* Extension methods */ |
377 | ||
29967ef6 | 378 | fn into_engine(self, tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>) -> Engine<'mir, 'tcx, Self> |
74b04a01 XL |
379 | where |
380 | Self: Sized, | |
381 | { | |
29967ef6 | 382 | Engine::new_gen_kill(tcx, body, self) |
74b04a01 | 383 | } |
dfeec247 XL |
384 | } |
385 | ||
386 | /// The legal operations for a transfer function in a gen/kill problem. | |
387 | /// | |
388 | /// This abstraction exists because there are two different contexts in which we call the methods in | |
389 | /// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently | |
390 | /// applied multiple times, such as when computing the cumulative transfer function for each block. | |
391 | /// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes, | |
392 | /// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the | |
393 | /// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to | |
394 | /// building up a `GenKillSet` and then throwing it away. | |
395 | pub trait GenKill<T> { | |
396 | /// Inserts `elem` into the state vector. | |
397 | fn gen(&mut self, elem: T); | |
398 | ||
399 | /// Removes `elem` from the state vector. | |
400 | fn kill(&mut self, elem: T); | |
401 | ||
402 | /// Calls `gen` for each element in `elems`. | |
403 | fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) { | |
404 | for elem in elems { | |
405 | self.gen(elem); | |
406 | } | |
407 | } | |
408 | ||
409 | /// Calls `kill` for each element in `elems`. | |
410 | fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) { | |
411 | for elem in elems { | |
412 | self.kill(elem); | |
413 | } | |
414 | } | |
415 | } | |
416 | ||
417 | /// Stores a transfer function for a gen/kill problem. | |
418 | /// | |
419 | /// Calling `gen`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be | |
420 | /// applied multiple times efficiently. When there are multiple calls to `gen` and/or `kill` for | |
421 | /// the same element, the most recent one takes precedence. | |
422 | #[derive(Clone)] | |
1b1a35ee | 423 | pub struct GenKillSet<T> { |
dfeec247 XL |
424 | gen: HybridBitSet<T>, |
425 | kill: HybridBitSet<T>, | |
426 | } | |
427 | ||
428 | impl<T: Idx> GenKillSet<T> { | |
429 | /// Creates a new transfer function that will leave the dataflow state unchanged. | |
430 | pub fn identity(universe: usize) -> Self { | |
431 | GenKillSet { | |
432 | gen: HybridBitSet::new_empty(universe), | |
433 | kill: HybridBitSet::new_empty(universe), | |
434 | } | |
435 | } | |
436 | ||
dfeec247 XL |
437 | pub fn apply(&self, state: &mut BitSet<T>) { |
438 | state.union(&self.gen); | |
439 | state.subtract(&self.kill); | |
440 | } | |
441 | } | |
442 | ||
443 | impl<T: Idx> GenKill<T> for GenKillSet<T> { | |
444 | fn gen(&mut self, elem: T) { | |
445 | self.gen.insert(elem); | |
446 | self.kill.remove(elem); | |
447 | } | |
448 | ||
449 | fn kill(&mut self, elem: T) { | |
450 | self.kill.insert(elem); | |
451 | self.gen.remove(elem); | |
452 | } | |
453 | } | |
454 | ||
455 | impl<T: Idx> GenKill<T> for BitSet<T> { | |
456 | fn gen(&mut self, elem: T) { | |
457 | self.insert(elem); | |
458 | } | |
459 | ||
460 | fn kill(&mut self, elem: T) { | |
461 | self.remove(elem); | |
462 | } | |
463 | } | |
464 | ||
1b1a35ee XL |
465 | impl<T: Idx> GenKill<T> for lattice::Dual<BitSet<T>> { |
466 | fn gen(&mut self, elem: T) { | |
467 | self.0.insert(elem); | |
468 | } | |
469 | ||
470 | fn kill(&mut self, elem: T) { | |
471 | self.0.remove(elem); | |
472 | } | |
473 | } | |
474 | ||
f9f354fc XL |
475 | // NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order. |
476 | #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)] | |
477 | pub enum Effect { | |
478 | /// The "before" effect (e.g., `apply_before_statement_effect`) for a statement (or | |
479 | /// terminator). | |
480 | Before, | |
481 | ||
482 | /// The "primary" effect (e.g., `apply_statement_effect`) for a statement (or terminator). | |
483 | Primary, | |
484 | } | |
485 | ||
486 | impl Effect { | |
487 | pub const fn at_index(self, statement_index: usize) -> EffectIndex { | |
488 | EffectIndex { effect: self, statement_index } | |
489 | } | |
490 | } | |
491 | ||
492 | #[derive(Clone, Copy, Debug, PartialEq, Eq)] | |
493 | pub struct EffectIndex { | |
494 | statement_index: usize, | |
495 | effect: Effect, | |
496 | } | |
497 | ||
498 | impl EffectIndex { | |
499 | fn next_in_forward_order(self) -> Self { | |
500 | match self.effect { | |
501 | Effect::Before => Effect::Primary.at_index(self.statement_index), | |
502 | Effect::Primary => Effect::Before.at_index(self.statement_index + 1), | |
503 | } | |
504 | } | |
505 | ||
506 | fn next_in_backward_order(self) -> Self { | |
507 | match self.effect { | |
508 | Effect::Before => Effect::Primary.at_index(self.statement_index), | |
509 | Effect::Primary => Effect::Before.at_index(self.statement_index - 1), | |
510 | } | |
511 | } | |
512 | ||
cdc7bbd5 | 513 | /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other` |
f9f354fc XL |
514 | /// in forward order. |
515 | fn precedes_in_forward_order(self, other: Self) -> bool { | |
516 | let ord = self | |
517 | .statement_index | |
518 | .cmp(&other.statement_index) | |
519 | .then_with(|| self.effect.cmp(&other.effect)); | |
520 | ord == Ordering::Less | |
521 | } | |
522 | ||
523 | /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other` | |
524 | /// in backward order. | |
525 | fn precedes_in_backward_order(self, other: Self) -> bool { | |
526 | let ord = other | |
527 | .statement_index | |
528 | .cmp(&self.statement_index) | |
529 | .then_with(|| self.effect.cmp(&other.effect)); | |
530 | ord == Ordering::Less | |
531 | } | |
532 | } | |
533 | ||
1b1a35ee XL |
534 | pub struct SwitchIntTarget { |
535 | pub value: Option<u128>, | |
536 | pub target: BasicBlock, | |
537 | } | |
538 | ||
539 | /// A type that records the edge-specific effects for a `SwitchInt` terminator. | |
540 | pub trait SwitchIntEdgeEffects<D> { | |
541 | /// Calls `apply_edge_effect` for each outgoing edge from a `SwitchInt` terminator and | |
542 | /// records the results. | |
543 | fn apply(&mut self, apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget)); | |
544 | } | |
545 | ||
dfeec247 XL |
546 | #[cfg(test)] |
547 | mod tests; |