]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
1 | //! A solver for dataflow problems. |
2 | ||
f2b60f7d FG |
3 | use crate::errors::{ |
4 | DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter, | |
5 | }; | |
5e7ed085 FG |
6 | use crate::framework::BitSetExt; |
7 | ||
dfeec247 | 8 | use std::ffi::OsString; |
dfeec247 XL |
9 | use std::path::PathBuf; |
10 | ||
3dfed10e | 11 | use rustc_ast as ast; |
dfeec247 | 12 | use rustc_data_structures::work_queue::WorkQueue; |
f035d41b | 13 | use rustc_graphviz as dot; |
dfeec247 | 14 | use rustc_hir::def_id::DefId; |
49aad941 | 15 | use rustc_index::{Idx, IndexVec}; |
f9f354fc | 16 | use rustc_middle::mir::{self, traversal, BasicBlock}; |
c295e0f8 | 17 | use rustc_middle::mir::{create_dump_file, dump_enabled}; |
353b0b11 | 18 | use rustc_middle::ty::print::with_no_trimmed_paths; |
29967ef6 | 19 | use rustc_middle::ty::TyCtxt; |
dfeec247 | 20 | use rustc_span::symbol::{sym, Symbol}; |
dfeec247 | 21 | |
1b1a35ee | 22 | use super::fmt::DebugWithContext; |
dfeec247 | 23 | use super::graphviz; |
f9f354fc | 24 | use super::{ |
1b1a35ee XL |
25 | visit_results, Analysis, Direction, GenKill, GenKillAnalysis, GenKillSet, JoinSemiLattice, |
26 | ResultsCursor, ResultsVisitor, | |
f9f354fc | 27 | }; |
dfeec247 | 28 | |
f9f354fc XL |
29 | /// A dataflow analysis that has converged to fixpoint. |
30 | pub struct Results<'tcx, A> | |
31 | where | |
32 | A: Analysis<'tcx>, | |
33 | { | |
34 | pub analysis: A, | |
1b1a35ee | 35 | pub(super) entry_sets: IndexVec<BasicBlock, A::Domain>, |
f9f354fc XL |
36 | } |
37 | ||
a2a8927a | 38 | impl<'tcx, A> Results<'tcx, A> |
f9f354fc XL |
39 | where |
40 | A: Analysis<'tcx>, | |
41 | { | |
42 | /// Creates a `ResultsCursor` that can inspect these `Results`. | |
a2a8927a XL |
43 | pub fn into_results_cursor<'mir>( |
44 | self, | |
45 | body: &'mir mir::Body<'tcx>, | |
46 | ) -> ResultsCursor<'mir, 'tcx, A> { | |
f9f354fc XL |
47 | ResultsCursor::new(body, self) |
48 | } | |
49 | ||
50 | /// Gets the dataflow state for the given block. | |
1b1a35ee | 51 | pub fn entry_set_for_block(&self, block: BasicBlock) -> &A::Domain { |
f9f354fc XL |
52 | &self.entry_sets[block] |
53 | } | |
54 | ||
a2a8927a | 55 | pub fn visit_with<'mir>( |
f9f354fc XL |
56 | &self, |
57 | body: &'mir mir::Body<'tcx>, | |
58 | blocks: impl IntoIterator<Item = BasicBlock>, | |
1b1a35ee | 59 | vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>, |
f9f354fc XL |
60 | ) { |
61 | visit_results(body, blocks, self, vis) | |
62 | } | |
63 | ||
a2a8927a | 64 | pub fn visit_reachable_with<'mir>( |
3dfed10e XL |
65 | &self, |
66 | body: &'mir mir::Body<'tcx>, | |
1b1a35ee | 67 | vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>, |
3dfed10e XL |
68 | ) { |
69 | let blocks = mir::traversal::reachable(body); | |
70 | visit_results(body, blocks.map(|(bb, _)| bb), self, vis) | |
71 | } | |
f9f354fc XL |
72 | } |
73 | ||
dfeec247 XL |
74 | /// A solver for dataflow problems. |
75 | pub struct Engine<'a, 'tcx, A> | |
76 | where | |
77 | A: Analysis<'tcx>, | |
78 | { | |
dfeec247 XL |
79 | tcx: TyCtxt<'tcx>, |
80 | body: &'a mir::Body<'tcx>, | |
1b1a35ee XL |
81 | entry_sets: IndexVec<BasicBlock, A::Domain>, |
82 | pass_name: Option<&'static str>, | |
dfeec247 XL |
83 | analysis: A, |
84 | ||
85 | /// Cached, cumulative transfer functions for each block. | |
1b1a35ee XL |
86 | // |
87 | // FIXME(ecstaticmorse): This boxed `Fn` trait object is invoked inside a tight loop for | |
88 | // gen/kill problems on cyclic CFGs. This is not ideal, but it doesn't seem to degrade | |
89 | // performance in practice. I've tried a few ways to avoid this, but they have downsides. See | |
90 | // the message for the commit that added this FIXME for more information. | |
91 | apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>, | |
dfeec247 XL |
92 | } |
93 | ||
a2a8927a | 94 | impl<'a, 'tcx, A, D, T> Engine<'a, 'tcx, A> |
dfeec247 | 95 | where |
1b1a35ee | 96 | A: GenKillAnalysis<'tcx, Idx = T, Domain = D>, |
5e7ed085 | 97 | D: Clone + JoinSemiLattice + GenKill<T> + BitSetExt<T>, |
1b1a35ee | 98 | T: Idx, |
dfeec247 XL |
99 | { |
100 | /// Creates a new `Engine` to solve a gen-kill dataflow problem. | |
29967ef6 | 101 | pub fn new_gen_kill(tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, analysis: A) -> Self { |
74b04a01 XL |
102 | // If there are no back-edges in the control-flow graph, we only ever need to apply the |
103 | // transfer function for each block exactly once (assuming that we process blocks in RPO). | |
104 | // | |
105 | // In this case, there's no need to compute the block transfer functions ahead of time. | |
064997fb | 106 | if !body.basic_blocks.is_cfg_cyclic() { |
29967ef6 | 107 | return Self::new(tcx, body, analysis, None); |
74b04a01 XL |
108 | } |
109 | ||
110 | // Otherwise, compute and store the cumulative transfer function for each block. | |
111 | ||
5e7ed085 | 112 | let identity = GenKillSet::identity(analysis.bottom_value(body).domain_size()); |
f2b60f7d | 113 | let mut trans_for_block = IndexVec::from_elem(identity, &body.basic_blocks); |
dfeec247 | 114 | |
f2b60f7d | 115 | for (block, block_data) in body.basic_blocks.iter_enumerated() { |
dfeec247 | 116 | let trans = &mut trans_for_block[block]; |
f9f354fc | 117 | A::Direction::gen_kill_effects_in_block(&analysis, trans, block, block_data); |
dfeec247 XL |
118 | } |
119 | ||
1b1a35ee | 120 | let apply_trans = Box::new(move |bb: BasicBlock, state: &mut A::Domain| { |
5e7ed085 | 121 | trans_for_block[bb].apply(state); |
1b1a35ee XL |
122 | }); |
123 | ||
29967ef6 | 124 | Self::new(tcx, body, analysis, Some(apply_trans as Box<_>)) |
dfeec247 XL |
125 | } |
126 | } | |
127 | ||
a2a8927a | 128 | impl<'a, 'tcx, A, D> Engine<'a, 'tcx, A> |
dfeec247 | 129 | where |
1b1a35ee XL |
130 | A: Analysis<'tcx, Domain = D>, |
131 | D: Clone + JoinSemiLattice, | |
dfeec247 XL |
132 | { |
133 | /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer | |
134 | /// function. | |
135 | /// | |
136 | /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for | |
137 | /// better performance. | |
29967ef6 XL |
138 | pub fn new_generic(tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, analysis: A) -> Self { |
139 | Self::new(tcx, body, analysis, None) | |
dfeec247 XL |
140 | } |
141 | ||
142 | fn new( | |
143 | tcx: TyCtxt<'tcx>, | |
144 | body: &'a mir::Body<'tcx>, | |
dfeec247 | 145 | analysis: A, |
1b1a35ee | 146 | apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>, |
dfeec247 | 147 | ) -> Self { |
1b1a35ee | 148 | let bottom_value = analysis.bottom_value(body); |
f2b60f7d | 149 | let mut entry_sets = IndexVec::from_elem(bottom_value.clone(), &body.basic_blocks); |
dfeec247 XL |
150 | analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]); |
151 | ||
923072b8 | 152 | if A::Direction::IS_BACKWARD && entry_sets[mir::START_BLOCK] != bottom_value { |
f9f354fc XL |
153 | bug!("`initialize_start_block` is not yet supported for backward dataflow analyses"); |
154 | } | |
155 | ||
9ffffee4 | 156 | Engine { analysis, tcx, body, pass_name: None, entry_sets, apply_trans_for_block } |
dfeec247 XL |
157 | } |
158 | ||
1b1a35ee XL |
159 | /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis. |
160 | /// | |
161 | /// Some analyses are run multiple times in the compilation pipeline. Give them a `pass_name` | |
162 | /// to differentiate them. Otherwise, only the results for the latest run will be saved. | |
163 | pub fn pass_name(mut self, name: &'static str) -> Self { | |
164 | self.pass_name = Some(name); | |
165 | self | |
166 | } | |
167 | ||
dfeec247 | 168 | /// Computes the fixpoint for this dataflow problem and returns it. |
1b1a35ee XL |
169 | pub fn iterate_to_fixpoint(self) -> Results<'tcx, A> |
170 | where | |
171 | A::Domain: DebugWithContext<A>, | |
172 | { | |
f9f354fc | 173 | let Engine { |
9ffffee4 | 174 | analysis, body, mut entry_sets, tcx, apply_trans_for_block, pass_name, .. |
f9f354fc | 175 | } = self; |
dfeec247 | 176 | |
f2b60f7d | 177 | let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks.len()); |
dfeec247 | 178 | |
923072b8 | 179 | if A::Direction::IS_FORWARD { |
f9f354fc XL |
180 | for (bb, _) in traversal::reverse_postorder(body) { |
181 | dirty_queue.insert(bb); | |
182 | } | |
183 | } else { | |
184 | // Reverse post-order on the reverse CFG may generate a better iteration order for | |
185 | // backward dataflow analyses, but probably not enough to matter. | |
186 | for (bb, _) in traversal::postorder(body) { | |
187 | dirty_queue.insert(bb); | |
188 | } | |
dfeec247 XL |
189 | } |
190 | ||
29967ef6 XL |
191 | // `state` is not actually used between iterations; |
192 | // this is just an optimization to avoid reallocating | |
193 | // every iteration. | |
1b1a35ee | 194 | let mut state = analysis.bottom_value(body); |
dfeec247 | 195 | while let Some(bb) = dirty_queue.pop() { |
f9f354fc | 196 | let bb_data = &body[bb]; |
dfeec247 | 197 | |
29967ef6 XL |
198 | // Set the state to the entry state of the block. |
199 | // This is equivalent to `state = entry_sets[bb].clone()`, | |
200 | // but it saves an allocation, thus improving compile times. | |
1b1a35ee | 201 | state.clone_from(&entry_sets[bb]); |
29967ef6 XL |
202 | |
203 | // Apply the block transfer function, using the cached one if it exists. | |
1b1a35ee XL |
204 | match &apply_trans_for_block { |
205 | Some(apply) => apply(bb, &mut state), | |
f9f354fc XL |
206 | None => A::Direction::apply_effects_in_block(&analysis, &mut state, bb, bb_data), |
207 | } | |
dfeec247 | 208 | |
f9f354fc XL |
209 | A::Direction::join_state_into_successors_of( |
210 | &analysis, | |
211 | tcx, | |
212 | body, | |
f9f354fc | 213 | &mut state, |
dfeec247 | 214 | (bb, bb_data), |
1b1a35ee XL |
215 | |target: BasicBlock, state: &A::Domain| { |
216 | let set_changed = entry_sets[target].join(state); | |
f9f354fc XL |
217 | if set_changed { |
218 | dirty_queue.insert(target); | |
219 | } | |
220 | }, | |
dfeec247 XL |
221 | ); |
222 | } | |
223 | ||
dfeec247 XL |
224 | let results = Results { analysis, entry_sets }; |
225 | ||
29967ef6 | 226 | let res = write_graphviz_results(tcx, &body, &results, pass_name); |
dfeec247 | 227 | if let Err(e) = res { |
29967ef6 | 228 | error!("Failed to write graphviz dataflow results: {}", e); |
dfeec247 XL |
229 | } |
230 | ||
231 | results | |
232 | } | |
dfeec247 XL |
233 | } |
234 | ||
235 | // Graphviz | |
236 | ||
237 | /// Writes a DOT file containing the results of a dataflow analysis if the user requested it via | |
238 | /// `rustc_mir` attributes. | |
a2a8927a | 239 | fn write_graphviz_results<'tcx, A>( |
dfeec247 | 240 | tcx: TyCtxt<'tcx>, |
dfeec247 XL |
241 | body: &mir::Body<'tcx>, |
242 | results: &Results<'tcx, A>, | |
1b1a35ee | 243 | pass_name: Option<&'static str>, |
dfeec247 XL |
244 | ) -> std::io::Result<()> |
245 | where | |
246 | A: Analysis<'tcx>, | |
1b1a35ee | 247 | A::Domain: DebugWithContext<A>, |
dfeec247 | 248 | { |
29967ef6 XL |
249 | use std::fs; |
250 | use std::io::{self, Write}; | |
251 | ||
252 | let def_id = body.source.def_id(); | |
5e7ed085 | 253 | let Ok(attrs) = RustcMirAttrs::parse(tcx, def_id) else { |
ba9703b0 | 254 | // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse` |
5e7ed085 | 255 | return Ok(()); |
dfeec247 XL |
256 | }; |
257 | ||
29967ef6 XL |
258 | let mut file = match attrs.output_path(A::NAME) { |
259 | Some(path) => { | |
260 | debug!("printing dataflow results for {:?} to {}", def_id, path.display()); | |
261 | if let Some(parent) = path.parent() { | |
262 | fs::create_dir_all(parent)?; | |
263 | } | |
264 | io::BufWriter::new(fs::File::create(&path)?) | |
265 | } | |
ba9703b0 | 266 | |
064997fb | 267 | None if tcx.sess.opts.unstable_opts.dump_mir_dataflow |
ba9703b0 XL |
268 | && dump_enabled(tcx, A::NAME, def_id) => |
269 | { | |
487cf647 | 270 | create_dump_file(tcx, ".dot", false, A::NAME, &pass_name.unwrap_or("-----"), body)? |
ba9703b0 XL |
271 | } |
272 | ||
29967ef6 | 273 | _ => return Ok(()), |
dfeec247 XL |
274 | }; |
275 | ||
1b1a35ee XL |
276 | let style = match attrs.formatter { |
277 | Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter, | |
278 | _ => graphviz::OutputStyle::AfterOnly, | |
dfeec247 XL |
279 | }; |
280 | ||
dfeec247 XL |
281 | let mut buf = Vec::new(); |
282 | ||
29967ef6 | 283 | let graphviz = graphviz::Formatter::new(body, results, style); |
1b1a35ee | 284 | let mut render_opts = |
064997fb FG |
285 | vec![dot::RenderOption::Fontname(tcx.sess.opts.unstable_opts.graphviz_font.clone())]; |
286 | if tcx.sess.opts.unstable_opts.graphviz_dark_mode { | |
1b1a35ee XL |
287 | render_opts.push(dot::RenderOption::DarkTheme); |
288 | } | |
353b0b11 | 289 | with_no_trimmed_paths!(dot::render_opts(&graphviz, &mut buf, &render_opts)?); |
ba9703b0 | 290 | |
29967ef6 | 291 | file.write_all(&buf)?; |
ba9703b0 | 292 | |
dfeec247 XL |
293 | Ok(()) |
294 | } | |
295 | ||
296 | #[derive(Default)] | |
297 | struct RustcMirAttrs { | |
298 | basename_and_suffix: Option<PathBuf>, | |
299 | formatter: Option<Symbol>, | |
300 | } | |
301 | ||
302 | impl RustcMirAttrs { | |
a2a8927a | 303 | fn parse(tcx: TyCtxt<'_>, def_id: DefId) -> Result<Self, ()> { |
dfeec247 XL |
304 | let mut result = Ok(()); |
305 | let mut ret = RustcMirAttrs::default(); | |
306 | ||
04454e1e FG |
307 | let rustc_mir_attrs = tcx |
308 | .get_attrs(def_id, sym::rustc_mir) | |
dfeec247 XL |
309 | .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter())); |
310 | ||
311 | for attr in rustc_mir_attrs { | |
3dfed10e | 312 | let attr_result = if attr.has_name(sym::borrowck_graphviz_postflow) { |
dfeec247 XL |
313 | Self::set_field(&mut ret.basename_and_suffix, tcx, &attr, |s| { |
314 | let path = PathBuf::from(s.to_string()); | |
315 | match path.file_name() { | |
316 | Some(_) => Ok(path), | |
317 | None => { | |
f2b60f7d | 318 | tcx.sess.emit_err(PathMustEndInFilename { span: attr.span() }); |
dfeec247 XL |
319 | Err(()) |
320 | } | |
321 | } | |
322 | }) | |
3dfed10e | 323 | } else if attr.has_name(sym::borrowck_graphviz_format) { |
dfeec247 XL |
324 | Self::set_field(&mut ret.formatter, tcx, &attr, |s| match s { |
325 | sym::gen_kill | sym::two_phase => Ok(s), | |
326 | _ => { | |
f2b60f7d | 327 | tcx.sess.emit_err(UnknownFormatter { span: attr.span() }); |
dfeec247 XL |
328 | Err(()) |
329 | } | |
330 | }) | |
331 | } else { | |
332 | Ok(()) | |
333 | }; | |
334 | ||
335 | result = result.and(attr_result); | |
336 | } | |
337 | ||
338 | result.map(|()| ret) | |
339 | } | |
340 | ||
341 | fn set_field<T>( | |
342 | field: &mut Option<T>, | |
a2a8927a | 343 | tcx: TyCtxt<'_>, |
dfeec247 XL |
344 | attr: &ast::NestedMetaItem, |
345 | mapper: impl FnOnce(Symbol) -> Result<T, ()>, | |
346 | ) -> Result<(), ()> { | |
347 | if field.is_some() { | |
f2b60f7d | 348 | tcx.sess.emit_err(DuplicateValuesFor { span: attr.span(), name: attr.name_or_empty() }); |
dfeec247 XL |
349 | |
350 | return Err(()); | |
351 | } | |
352 | ||
353 | if let Some(s) = attr.value_str() { | |
354 | *field = Some(mapper(s)?); | |
355 | Ok(()) | |
356 | } else { | |
f2b60f7d | 357 | tcx.sess.emit_err(RequiresAnArgument { span: attr.span(), name: attr.name_or_empty() }); |
dfeec247 XL |
358 | Err(()) |
359 | } | |
360 | } | |
361 | ||
362 | /// Returns the path where dataflow results should be written, or `None` | |
363 | /// `borrowck_graphviz_postflow` was not specified. | |
364 | /// | |
365 | /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`: | |
366 | /// | |
367 | /// "path/suffix.dot" -> "path/analysis_name_suffix.dot" | |
368 | fn output_path(&self, analysis_name: &str) -> Option<PathBuf> { | |
369 | let mut ret = self.basename_and_suffix.as_ref().cloned()?; | |
370 | let suffix = ret.file_name().unwrap(); // Checked when parsing attrs | |
371 | ||
372 | let mut file_name: OsString = analysis_name.into(); | |
373 | file_name.push("_"); | |
374 | file_name.push(suffix); | |
375 | ret.set_file_name(file_name); | |
376 | ||
377 | Some(ret) | |
378 | } | |
379 | } |