]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
1 | //! A framework that can express both [gen-kill] and generic dataflow problems. |
2 | //! | |
3 | //! There is another interface for dataflow in the compiler in `librustc_mir/dataflow/mod.rs`. The | |
4 | //! interface in this module will eventually [replace that one][design-meeting]. | |
5 | //! | |
6 | //! To actually use this framework, you must implement either the `Analysis` or the `GenKillAnalysis` | |
7 | //! trait. If your transfer function can be expressed with only gen/kill operations, prefer | |
8 | //! `GenKillAnalysis` since it will run faster while iterating to fixpoint. Create an `Engine` using | |
9 | //! the appropriate constructor and call `iterate_to_fixpoint`. You can use a `ResultsCursor` to | |
10 | //! inspect the fixpoint solution to your dataflow problem. | |
11 | //! | |
12 | //! ```ignore(cross-crate-imports) | |
13 | //! fn do_my_analysis(tcx: TyCtxt<'tcx>, body: &mir::Body<'tcx>, did: DefId) { | |
14 | //! let analysis = MyAnalysis::new(); | |
15 | //! | |
16 | //! // If `MyAnalysis` implements `GenKillAnalysis`. | |
17 | //! let results = Engine::new_gen_kill(tcx, body, did, analysis).iterate_to_fixpoint(); | |
18 | //! | |
19 | //! // If `MyAnalysis` implements `Analysis`. | |
20 | //! // let results = Engine::new_generic(tcx, body, did, analysis).iterate_to_fixpoint(); | |
21 | //! | |
22 | //! let mut cursor = ResultsCursor::new(body, results); | |
23 | //! | |
24 | //! for (_, statement_index) in body.block_data[START_BLOCK].statements.iter_enumerated() { | |
25 | //! cursor.seek_after(Location { block: START_BLOCK, statement_index }); | |
26 | //! let state = cursor.get(); | |
27 | //! println!("{:?}", state); | |
28 | //! } | |
29 | //! } | |
30 | //! ``` | |
31 | //! | |
32 | //! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems | |
33 | //! [design-meeting]https://github.com/rust-lang/compiler-team/issues/202 | |
34 | ||
35 | use std::io; | |
36 | ||
37 | use rustc::mir::{self, BasicBlock, Location}; | |
74b04a01 XL |
38 | use rustc::ty::layout::VariantIdx; |
39 | use rustc::ty::{self, TyCtxt}; | |
40 | use rustc_hir::def_id::DefId; | |
dfeec247 XL |
41 | use rustc_index::bit_set::{BitSet, HybridBitSet}; |
42 | use rustc_index::vec::{Idx, IndexVec}; | |
43 | ||
44 | use crate::dataflow::BottomValue; | |
45 | ||
46 | mod cursor; | |
47 | mod engine; | |
48 | mod graphviz; | |
74b04a01 | 49 | mod visitor; |
dfeec247 XL |
50 | |
51 | pub use self::cursor::{ResultsCursor, ResultsRefCursor}; | |
52 | pub use self::engine::Engine; | |
74b04a01 XL |
53 | pub use self::visitor::{visit_results, ResultsVisitor}; |
54 | pub use self::visitor::{BorrowckFlowState, BorrowckResults}; | |
dfeec247 XL |
55 | |
56 | /// A dataflow analysis that has converged to fixpoint. | |
57 | pub struct Results<'tcx, A> | |
58 | where | |
59 | A: Analysis<'tcx>, | |
60 | { | |
61 | pub analysis: A, | |
62 | entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>, | |
63 | } | |
64 | ||
65 | impl<A> Results<'tcx, A> | |
66 | where | |
67 | A: Analysis<'tcx>, | |
68 | { | |
69 | /// Creates a `ResultsCursor` that can inspect these `Results`. | |
70 | pub fn into_results_cursor(self, body: &'mir mir::Body<'tcx>) -> ResultsCursor<'mir, 'tcx, A> { | |
71 | ResultsCursor::new(body, self) | |
72 | } | |
73 | ||
74 | /// Gets the entry set for the given block. | |
75 | pub fn entry_set_for_block(&self, block: BasicBlock) -> &BitSet<A::Idx> { | |
76 | &self.entry_sets[block] | |
77 | } | |
74b04a01 XL |
78 | |
79 | pub fn visit_with( | |
80 | &self, | |
81 | body: &'mir mir::Body<'tcx>, | |
82 | blocks: impl IntoIterator<Item = BasicBlock>, | |
83 | vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = BitSet<A::Idx>>, | |
84 | ) { | |
85 | visit_results(body, blocks, self, vis) | |
86 | } | |
87 | ||
88 | pub fn visit_in_rpo_with( | |
89 | &self, | |
90 | body: &'mir mir::Body<'tcx>, | |
91 | vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = BitSet<A::Idx>>, | |
92 | ) { | |
93 | let blocks = mir::traversal::reverse_postorder(body); | |
94 | visit_results(body, blocks.map(|(bb, _)| bb), self, vis) | |
95 | } | |
dfeec247 XL |
96 | } |
97 | ||
98 | /// Define the domain of a dataflow problem. | |
99 | /// | |
100 | /// This trait specifies the lattice on which this analysis operates. For now, this must be a | |
101 | /// powerset of values of type `Idx`. The elements of this lattice are represented with a `BitSet` | |
102 | /// and referred to as the state vector. | |
103 | /// | |
104 | /// This trait also defines the initial value for the dataflow state upon entry to the | |
105 | /// `START_BLOCK`, as well as some names used to refer to this analysis when debugging. | |
106 | pub trait AnalysisDomain<'tcx>: BottomValue { | |
107 | /// The type of the elements in the state vector. | |
108 | type Idx: Idx; | |
109 | ||
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 | ||
116 | /// The size of the state vector. | |
117 | fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize; | |
118 | ||
119 | /// Mutates the entry set of the `START_BLOCK` to contain the initial state for dataflow | |
120 | /// analysis. | |
121 | fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>); | |
122 | ||
123 | /// Prints an element in the state vector for debugging. | |
124 | fn pretty_print_idx(&self, w: &mut impl io::Write, idx: Self::Idx) -> io::Result<()> { | |
125 | write!(w, "{:?}", idx) | |
126 | } | |
127 | } | |
128 | ||
129 | /// A dataflow problem with an arbitrarily complex transfer function. | |
130 | pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { | |
131 | /// Updates the current dataflow state with the effect of evaluating a statement. | |
132 | fn apply_statement_effect( | |
133 | &self, | |
134 | state: &mut BitSet<Self::Idx>, | |
135 | statement: &mir::Statement<'tcx>, | |
136 | location: Location, | |
137 | ); | |
138 | ||
139 | /// Updates the current dataflow state with an effect that occurs immediately *before* the | |
140 | /// given statement. | |
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 statement (e.g. for two-phase borrows). As a general rule, | |
144 | /// analyses should not implement this without implementing `apply_statement_effect`. | |
145 | fn apply_before_statement_effect( | |
146 | &self, | |
147 | _state: &mut BitSet<Self::Idx>, | |
148 | _statement: &mir::Statement<'tcx>, | |
149 | _location: Location, | |
150 | ) { | |
151 | } | |
152 | ||
153 | /// Updates the current dataflow state with the effect of evaluating a terminator. | |
154 | /// | |
155 | /// The effect of a successful return from a `Call` terminator should **not** be accounted for | |
156 | /// in this function. That should go in `apply_call_return_effect`. For example, in the | |
157 | /// `InitializedPlaces` analyses, the return place for a function call is not marked as | |
158 | /// initialized here. | |
159 | fn apply_terminator_effect( | |
160 | &self, | |
161 | state: &mut BitSet<Self::Idx>, | |
162 | terminator: &mir::Terminator<'tcx>, | |
163 | location: Location, | |
164 | ); | |
165 | ||
166 | /// Updates the current dataflow state with an effect that occurs immediately *before* the | |
167 | /// given terminator. | |
168 | /// | |
169 | /// This method is useful if the consumer of the results of this analysis needs only to observe | |
170 | /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule, | |
171 | /// analyses should not implement this without implementing `apply_terminator_effect`. | |
172 | fn apply_before_terminator_effect( | |
173 | &self, | |
174 | _state: &mut BitSet<Self::Idx>, | |
175 | _terminator: &mir::Terminator<'tcx>, | |
176 | _location: Location, | |
177 | ) { | |
178 | } | |
179 | ||
180 | /// Updates the current dataflow state with the effect of a successful return from a `Call` | |
181 | /// terminator. | |
182 | /// | |
183 | /// This is separate from `apply_terminator_effect` to properly track state across unwind | |
184 | /// edges. | |
185 | fn apply_call_return_effect( | |
186 | &self, | |
187 | state: &mut BitSet<Self::Idx>, | |
188 | block: BasicBlock, | |
189 | func: &mir::Operand<'tcx>, | |
190 | args: &[mir::Operand<'tcx>], | |
191 | return_place: &mir::Place<'tcx>, | |
192 | ); | |
74b04a01 XL |
193 | |
194 | /// Updates the current dataflow state with the effect of taking a particular branch in a | |
195 | /// `SwitchInt` terminator. | |
196 | /// | |
197 | /// Much like `apply_call_return_effect`, this effect is only propagated along a single | |
198 | /// outgoing edge from this basic block. | |
199 | fn apply_discriminant_switch_effect( | |
200 | &self, | |
201 | _state: &mut BitSet<Self::Idx>, | |
202 | _block: BasicBlock, | |
203 | _enum_place: &mir::Place<'tcx>, | |
204 | _adt: &ty::AdtDef, | |
205 | _variant: VariantIdx, | |
206 | ) { | |
207 | } | |
208 | ||
209 | /// Creates an `Engine` to find the fixpoint for this dataflow problem. | |
210 | /// | |
211 | /// You shouldn't need to override this outside this module, since the combination of the | |
212 | /// default impl and the one for all `A: GenKillAnalysis` will do the right thing. | |
213 | /// Its purpose is to enable method chaining like so: | |
214 | /// | |
215 | /// ```ignore(cross-crate-imports) | |
216 | /// let results = MyAnalysis::new(tcx, body) | |
217 | /// .into_engine(tcx, body, def_id) | |
218 | /// .iterate_to_fixpoint() | |
219 | /// .into_results_cursor(body); | |
220 | /// ``` | |
221 | fn into_engine( | |
222 | self, | |
223 | tcx: TyCtxt<'tcx>, | |
224 | body: &'mir mir::Body<'tcx>, | |
225 | def_id: DefId, | |
226 | ) -> Engine<'mir, 'tcx, Self> | |
227 | where | |
228 | Self: Sized, | |
229 | { | |
230 | Engine::new_generic(tcx, body, def_id, self) | |
231 | } | |
dfeec247 XL |
232 | } |
233 | ||
234 | /// A gen/kill dataflow problem. | |
235 | /// | |
236 | /// Each method in this trait has a corresponding one in `Analysis`. However, these methods only | |
237 | /// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer | |
238 | /// functions for each statement in this way, the transfer function for an entire basic block can | |
239 | /// be computed efficiently. | |
240 | /// | |
241 | /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`. | |
242 | pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> { | |
243 | /// See `Analysis::apply_statement_effect`. | |
244 | fn statement_effect( | |
245 | &self, | |
246 | trans: &mut impl GenKill<Self::Idx>, | |
247 | statement: &mir::Statement<'tcx>, | |
248 | location: Location, | |
249 | ); | |
250 | ||
251 | /// See `Analysis::apply_before_statement_effect`. | |
252 | fn before_statement_effect( | |
253 | &self, | |
254 | _trans: &mut impl GenKill<Self::Idx>, | |
255 | _statement: &mir::Statement<'tcx>, | |
256 | _location: Location, | |
257 | ) { | |
258 | } | |
259 | ||
260 | /// See `Analysis::apply_terminator_effect`. | |
261 | fn terminator_effect( | |
262 | &self, | |
263 | trans: &mut impl GenKill<Self::Idx>, | |
264 | terminator: &mir::Terminator<'tcx>, | |
265 | location: Location, | |
266 | ); | |
267 | ||
268 | /// See `Analysis::apply_before_terminator_effect`. | |
269 | fn before_terminator_effect( | |
270 | &self, | |
271 | _trans: &mut impl GenKill<Self::Idx>, | |
272 | _terminator: &mir::Terminator<'tcx>, | |
273 | _location: Location, | |
274 | ) { | |
275 | } | |
276 | ||
277 | /// See `Analysis::apply_call_return_effect`. | |
278 | fn call_return_effect( | |
279 | &self, | |
280 | trans: &mut impl GenKill<Self::Idx>, | |
281 | block: BasicBlock, | |
282 | func: &mir::Operand<'tcx>, | |
283 | args: &[mir::Operand<'tcx>], | |
284 | return_place: &mir::Place<'tcx>, | |
285 | ); | |
74b04a01 XL |
286 | |
287 | /// See `Analysis::apply_discriminant_switch_effect`. | |
288 | fn discriminant_switch_effect( | |
289 | &self, | |
290 | _state: &mut impl GenKill<Self::Idx>, | |
291 | _block: BasicBlock, | |
292 | _enum_place: &mir::Place<'tcx>, | |
293 | _adt: &ty::AdtDef, | |
294 | _variant: VariantIdx, | |
295 | ) { | |
296 | } | |
dfeec247 XL |
297 | } |
298 | ||
299 | impl<A> Analysis<'tcx> for A | |
300 | where | |
301 | A: GenKillAnalysis<'tcx>, | |
302 | { | |
303 | fn apply_statement_effect( | |
304 | &self, | |
305 | state: &mut BitSet<Self::Idx>, | |
306 | statement: &mir::Statement<'tcx>, | |
307 | location: Location, | |
308 | ) { | |
309 | self.statement_effect(state, statement, location); | |
310 | } | |
311 | ||
312 | fn apply_before_statement_effect( | |
313 | &self, | |
314 | state: &mut BitSet<Self::Idx>, | |
315 | statement: &mir::Statement<'tcx>, | |
316 | location: Location, | |
317 | ) { | |
318 | self.before_statement_effect(state, statement, location); | |
319 | } | |
320 | ||
321 | fn apply_terminator_effect( | |
322 | &self, | |
323 | state: &mut BitSet<Self::Idx>, | |
324 | terminator: &mir::Terminator<'tcx>, | |
325 | location: Location, | |
326 | ) { | |
327 | self.terminator_effect(state, terminator, location); | |
328 | } | |
329 | ||
330 | fn apply_before_terminator_effect( | |
331 | &self, | |
332 | state: &mut BitSet<Self::Idx>, | |
333 | terminator: &mir::Terminator<'tcx>, | |
334 | location: Location, | |
335 | ) { | |
336 | self.before_terminator_effect(state, terminator, location); | |
337 | } | |
338 | ||
339 | fn apply_call_return_effect( | |
340 | &self, | |
341 | state: &mut BitSet<Self::Idx>, | |
342 | block: BasicBlock, | |
343 | func: &mir::Operand<'tcx>, | |
344 | args: &[mir::Operand<'tcx>], | |
345 | return_place: &mir::Place<'tcx>, | |
346 | ) { | |
347 | self.call_return_effect(state, block, func, args, return_place); | |
348 | } | |
74b04a01 XL |
349 | |
350 | fn apply_discriminant_switch_effect( | |
351 | &self, | |
352 | state: &mut BitSet<Self::Idx>, | |
353 | block: BasicBlock, | |
354 | enum_place: &mir::Place<'tcx>, | |
355 | adt: &ty::AdtDef, | |
356 | variant: VariantIdx, | |
357 | ) { | |
358 | self.discriminant_switch_effect(state, block, enum_place, adt, variant); | |
359 | } | |
360 | ||
361 | fn into_engine( | |
362 | self, | |
363 | tcx: TyCtxt<'tcx>, | |
364 | body: &'mir mir::Body<'tcx>, | |
365 | def_id: DefId, | |
366 | ) -> Engine<'mir, 'tcx, Self> | |
367 | where | |
368 | Self: Sized, | |
369 | { | |
370 | Engine::new_gen_kill(tcx, body, def_id, self) | |
371 | } | |
dfeec247 XL |
372 | } |
373 | ||
374 | /// The legal operations for a transfer function in a gen/kill problem. | |
375 | /// | |
376 | /// This abstraction exists because there are two different contexts in which we call the methods in | |
377 | /// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently | |
378 | /// applied multiple times, such as when computing the cumulative transfer function for each block. | |
379 | /// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes, | |
380 | /// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the | |
381 | /// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to | |
382 | /// building up a `GenKillSet` and then throwing it away. | |
383 | pub trait GenKill<T> { | |
384 | /// Inserts `elem` into the state vector. | |
385 | fn gen(&mut self, elem: T); | |
386 | ||
387 | /// Removes `elem` from the state vector. | |
388 | fn kill(&mut self, elem: T); | |
389 | ||
390 | /// Calls `gen` for each element in `elems`. | |
391 | fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) { | |
392 | for elem in elems { | |
393 | self.gen(elem); | |
394 | } | |
395 | } | |
396 | ||
397 | /// Calls `kill` for each element in `elems`. | |
398 | fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) { | |
399 | for elem in elems { | |
400 | self.kill(elem); | |
401 | } | |
402 | } | |
403 | } | |
404 | ||
405 | /// Stores a transfer function for a gen/kill problem. | |
406 | /// | |
407 | /// Calling `gen`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be | |
408 | /// applied multiple times efficiently. When there are multiple calls to `gen` and/or `kill` for | |
409 | /// the same element, the most recent one takes precedence. | |
410 | #[derive(Clone)] | |
411 | pub struct GenKillSet<T: Idx> { | |
412 | gen: HybridBitSet<T>, | |
413 | kill: HybridBitSet<T>, | |
414 | } | |
415 | ||
416 | impl<T: Idx> GenKillSet<T> { | |
417 | /// Creates a new transfer function that will leave the dataflow state unchanged. | |
418 | pub fn identity(universe: usize) -> Self { | |
419 | GenKillSet { | |
420 | gen: HybridBitSet::new_empty(universe), | |
421 | kill: HybridBitSet::new_empty(universe), | |
422 | } | |
423 | } | |
424 | ||
425 | /// Applies this transfer function to the given state vector. | |
426 | pub fn apply(&self, state: &mut BitSet<T>) { | |
427 | state.union(&self.gen); | |
428 | state.subtract(&self.kill); | |
429 | } | |
430 | } | |
431 | ||
432 | impl<T: Idx> GenKill<T> for GenKillSet<T> { | |
433 | fn gen(&mut self, elem: T) { | |
434 | self.gen.insert(elem); | |
435 | self.kill.remove(elem); | |
436 | } | |
437 | ||
438 | fn kill(&mut self, elem: T) { | |
439 | self.kill.insert(elem); | |
440 | self.gen.remove(elem); | |
441 | } | |
442 | } | |
443 | ||
444 | impl<T: Idx> GenKill<T> for BitSet<T> { | |
445 | fn gen(&mut self, elem: T) { | |
446 | self.insert(elem); | |
447 | } | |
448 | ||
449 | fn kill(&mut self, elem: T) { | |
450 | self.remove(elem); | |
451 | } | |
452 | } | |
453 | ||
454 | #[cfg(test)] | |
455 | mod tests; |