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