1 //! A solver for dataflow problems.
4 DuplicateValuesFor
, PathMustEndInFilename
, RequiresAnArgument
, UnknownFormatter
,
6 use crate::framework
::BitSetExt
;
8 use std
::ffi
::OsString
;
9 use std
::path
::PathBuf
;
12 use rustc_data_structures
::work_queue
::WorkQueue
;
13 use rustc_graphviz
as dot
;
14 use rustc_hir
::def_id
::DefId
;
15 use rustc_index
::bit_set
::BitSet
;
16 use rustc_index
::vec
::{Idx, IndexVec}
;
17 use rustc_middle
::mir
::{self, traversal, BasicBlock}
;
18 use rustc_middle
::mir
::{create_dump_file, dump_enabled}
;
19 use rustc_middle
::ty
::TyCtxt
;
20 use rustc_span
::symbol
::{sym, Symbol}
;
22 use super::fmt
::DebugWithContext
;
25 visit_results
, Analysis
, Direction
, GenKill
, GenKillAnalysis
, GenKillSet
, JoinSemiLattice
,
26 ResultsCursor
, ResultsVisitor
,
29 /// A dataflow analysis that has converged to fixpoint.
30 pub struct Results
<'tcx
, A
>
35 pub(super) entry_sets
: IndexVec
<BasicBlock
, A
::Domain
>,
38 impl<'tcx
, A
> Results
<'tcx
, A
>
42 /// Creates a `ResultsCursor` that can inspect these `Results`.
43 pub fn into_results_cursor
<'mir
>(
45 body
: &'mir mir
::Body
<'tcx
>,
46 ) -> ResultsCursor
<'mir
, 'tcx
, A
> {
47 ResultsCursor
::new(body
, self)
50 /// Gets the dataflow state for the given block.
51 pub fn entry_set_for_block(&self, block
: BasicBlock
) -> &A
::Domain
{
52 &self.entry_sets
[block
]
55 pub fn visit_with
<'mir
>(
57 body
: &'mir mir
::Body
<'tcx
>,
58 blocks
: impl IntoIterator
<Item
= BasicBlock
>,
59 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= A
::Domain
>,
61 visit_results(body
, blocks
, self, vis
)
64 pub fn visit_reachable_with
<'mir
>(
66 body
: &'mir mir
::Body
<'tcx
>,
67 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= A
::Domain
>,
69 let blocks
= mir
::traversal
::reachable(body
);
70 visit_results(body
, blocks
.map(|(bb
, _
)| bb
), self, vis
)
74 /// A solver for dataflow problems.
75 pub struct Engine
<'a
, 'tcx
, A
>
80 body
: &'a mir
::Body
<'tcx
>,
81 dead_unwinds
: Option
<&'a BitSet
<BasicBlock
>>,
82 entry_sets
: IndexVec
<BasicBlock
, A
::Domain
>,
83 pass_name
: Option
<&'
static str>,
86 /// Cached, cumulative transfer functions for each block.
88 // FIXME(ecstaticmorse): This boxed `Fn` trait object is invoked inside a tight loop for
89 // gen/kill problems on cyclic CFGs. This is not ideal, but it doesn't seem to degrade
90 // performance in practice. I've tried a few ways to avoid this, but they have downsides. See
91 // the message for the commit that added this FIXME for more information.
92 apply_trans_for_block
: Option
<Box
<dyn Fn(BasicBlock
, &mut A
::Domain
)>>,
95 impl<'a
, 'tcx
, A
, D
, T
> Engine
<'a
, 'tcx
, A
>
97 A
: GenKillAnalysis
<'tcx
, Idx
= T
, Domain
= D
>,
98 D
: Clone
+ JoinSemiLattice
+ GenKill
<T
> + BitSetExt
<T
>,
101 /// Creates a new `Engine` to solve a gen-kill dataflow problem.
102 pub fn new_gen_kill(tcx
: TyCtxt
<'tcx
>, body
: &'a mir
::Body
<'tcx
>, analysis
: A
) -> Self {
103 // If there are no back-edges in the control-flow graph, we only ever need to apply the
104 // transfer function for each block exactly once (assuming that we process blocks in RPO).
106 // In this case, there's no need to compute the block transfer functions ahead of time.
107 if !body
.basic_blocks
.is_cfg_cyclic() {
108 return Self::new(tcx
, body
, analysis
, None
);
111 // Otherwise, compute and store the cumulative transfer function for each block.
113 let identity
= GenKillSet
::identity(analysis
.bottom_value(body
).domain_size());
114 let mut trans_for_block
= IndexVec
::from_elem(identity
, &body
.basic_blocks
);
116 for (block
, block_data
) in body
.basic_blocks
.iter_enumerated() {
117 let trans
= &mut trans_for_block
[block
];
118 A
::Direction
::gen_kill_effects_in_block(&analysis
, trans
, block
, block_data
);
121 let apply_trans
= Box
::new(move |bb
: BasicBlock
, state
: &mut A
::Domain
| {
122 trans_for_block
[bb
].apply(state
);
125 Self::new(tcx
, body
, analysis
, Some(apply_trans
as Box
<_
>))
129 impl<'a
, 'tcx
, A
, D
> Engine
<'a
, 'tcx
, A
>
131 A
: Analysis
<'tcx
, Domain
= D
>,
132 D
: Clone
+ JoinSemiLattice
,
134 /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
137 /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
138 /// better performance.
139 pub fn new_generic(tcx
: TyCtxt
<'tcx
>, body
: &'a mir
::Body
<'tcx
>, analysis
: A
) -> Self {
140 Self::new(tcx
, body
, analysis
, None
)
145 body
: &'a mir
::Body
<'tcx
>,
147 apply_trans_for_block
: Option
<Box
<dyn Fn(BasicBlock
, &mut A
::Domain
)>>,
149 let bottom_value
= analysis
.bottom_value(body
);
150 let mut entry_sets
= IndexVec
::from_elem(bottom_value
.clone(), &body
.basic_blocks
);
151 analysis
.initialize_start_block(body
, &mut entry_sets
[mir
::START_BLOCK
]);
153 if A
::Direction
::IS_BACKWARD
&& entry_sets
[mir
::START_BLOCK
] != bottom_value
{
154 bug
!("`initialize_start_block` is not yet supported for backward dataflow analyses");
164 apply_trans_for_block
,
168 /// Signals that we do not want dataflow state to propagate across unwind edges for these
171 /// You must take care that `dead_unwinds` does not contain a `BasicBlock` that *can* actually
172 /// unwind during execution. Otherwise, your dataflow results will not be correct.
173 pub fn dead_unwinds(mut self, dead_unwinds
: &'a BitSet
<BasicBlock
>) -> Self {
174 self.dead_unwinds
= Some(dead_unwinds
);
178 /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis.
180 /// Some analyses are run multiple times in the compilation pipeline. Give them a `pass_name`
181 /// to differentiate them. Otherwise, only the results for the latest run will be saved.
182 pub fn pass_name(mut self, name
: &'
static str) -> Self {
183 self.pass_name
= Some(name
);
187 /// Computes the fixpoint for this dataflow problem and returns it.
188 pub fn iterate_to_fixpoint(self) -> Results
<'tcx
, A
>
190 A
::Domain
: DebugWithContext
<A
>,
198 apply_trans_for_block
,
203 let mut dirty_queue
: WorkQueue
<BasicBlock
> = WorkQueue
::with_none(body
.basic_blocks
.len());
205 if A
::Direction
::IS_FORWARD
{
206 for (bb
, _
) in traversal
::reverse_postorder(body
) {
207 dirty_queue
.insert(bb
);
210 // Reverse post-order on the reverse CFG may generate a better iteration order for
211 // backward dataflow analyses, but probably not enough to matter.
212 for (bb
, _
) in traversal
::postorder(body
) {
213 dirty_queue
.insert(bb
);
217 // `state` is not actually used between iterations;
218 // this is just an optimization to avoid reallocating
220 let mut state
= analysis
.bottom_value(body
);
221 while let Some(bb
) = dirty_queue
.pop() {
222 let bb_data
= &body
[bb
];
224 // Set the state to the entry state of the block.
225 // This is equivalent to `state = entry_sets[bb].clone()`,
226 // but it saves an allocation, thus improving compile times.
227 state
.clone_from(&entry_sets
[bb
]);
229 // Apply the block transfer function, using the cached one if it exists.
230 match &apply_trans_for_block
{
231 Some(apply
) => apply(bb
, &mut state
),
232 None
=> A
::Direction
::apply_effects_in_block(&analysis
, &mut state
, bb
, bb_data
),
235 A
::Direction
::join_state_into_successors_of(
242 |target
: BasicBlock
, state
: &A
::Domain
| {
243 let set_changed
= entry_sets
[target
].join(state
);
245 dirty_queue
.insert(target
);
251 let results
= Results { analysis, entry_sets }
;
253 let res
= write_graphviz_results(tcx
, &body
, &results
, pass_name
);
254 if let Err(e
) = res
{
255 error
!("Failed to write graphviz dataflow results: {}", e
);
264 /// Writes a DOT file containing the results of a dataflow analysis if the user requested it via
265 /// `rustc_mir` attributes.
266 fn write_graphviz_results
<'tcx
, A
>(
268 body
: &mir
::Body
<'tcx
>,
269 results
: &Results
<'tcx
, A
>,
270 pass_name
: Option
<&'
static str>,
271 ) -> std
::io
::Result
<()>
274 A
::Domain
: DebugWithContext
<A
>,
277 use std
::io
::{self, Write}
;
279 let def_id
= body
.source
.def_id();
280 let Ok(attrs
) = RustcMirAttrs
::parse(tcx
, def_id
) else {
281 // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse`
285 let mut file
= match attrs
.output_path(A
::NAME
) {
287 debug
!("printing dataflow results for {:?} to {}", def_id
, path
.display());
288 if let Some(parent
) = path
.parent() {
289 fs
::create_dir_all(parent
)?
;
291 io
::BufWriter
::new(fs
::File
::create(&path
)?
)
294 None
if tcx
.sess
.opts
.unstable_opts
.dump_mir_dataflow
295 && dump_enabled(tcx
, A
::NAME
, def_id
) =>
302 &pass_name
.unwrap_or("-----"),
310 let style
= match attrs
.formatter
{
311 Some(sym
::two_phase
) => graphviz
::OutputStyle
::BeforeAndAfter
,
312 _
=> graphviz
::OutputStyle
::AfterOnly
,
315 let mut buf
= Vec
::new();
317 let graphviz
= graphviz
::Formatter
::new(body
, results
, style
);
318 let mut render_opts
=
319 vec
![dot
::RenderOption
::Fontname(tcx
.sess
.opts
.unstable_opts
.graphviz_font
.clone())];
320 if tcx
.sess
.opts
.unstable_opts
.graphviz_dark_mode
{
321 render_opts
.push(dot
::RenderOption
::DarkTheme
);
323 dot
::render_opts(&graphviz
, &mut buf
, &render_opts
)?
;
325 file
.write_all(&buf
)?
;
331 struct RustcMirAttrs
{
332 basename_and_suffix
: Option
<PathBuf
>,
333 formatter
: Option
<Symbol
>,
337 fn parse(tcx
: TyCtxt
<'_
>, def_id
: DefId
) -> Result
<Self, ()> {
338 let mut result
= Ok(());
339 let mut ret
= RustcMirAttrs
::default();
341 let rustc_mir_attrs
= tcx
342 .get_attrs(def_id
, sym
::rustc_mir
)
343 .flat_map(|attr
| attr
.meta_item_list().into_iter().flat_map(|v
| v
.into_iter()));
345 for attr
in rustc_mir_attrs
{
346 let attr_result
= if attr
.has_name(sym
::borrowck_graphviz_postflow
) {
347 Self::set_field(&mut ret
.basename_and_suffix
, tcx
, &attr
, |s
| {
348 let path
= PathBuf
::from(s
.to_string());
349 match path
.file_name() {
352 tcx
.sess
.emit_err(PathMustEndInFilename { span: attr.span() }
);
357 } else if attr
.has_name(sym
::borrowck_graphviz_format
) {
358 Self::set_field(&mut ret
.formatter
, tcx
, &attr
, |s
| match s
{
359 sym
::gen_kill
| sym
::two_phase
=> Ok(s
),
361 tcx
.sess
.emit_err(UnknownFormatter { span: attr.span() }
);
369 result
= result
.and(attr_result
);
376 field
: &mut Option
<T
>,
378 attr
: &ast
::NestedMetaItem
,
379 mapper
: impl FnOnce(Symbol
) -> Result
<T
, ()>,
380 ) -> Result
<(), ()> {
382 tcx
.sess
.emit_err(DuplicateValuesFor { span: attr.span(), name: attr.name_or_empty() }
);
387 if let Some(s
) = attr
.value_str() {
388 *field
= Some(mapper(s
)?
);
391 tcx
.sess
.emit_err(RequiresAnArgument { span: attr.span(), name: attr.name_or_empty() }
);
396 /// Returns the path where dataflow results should be written, or `None`
397 /// `borrowck_graphviz_postflow` was not specified.
399 /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
401 /// "path/suffix.dot" -> "path/analysis_name_suffix.dot"
402 fn output_path(&self, analysis_name
: &str) -> Option
<PathBuf
> {
403 let mut ret
= self.basename_and_suffix
.as_ref().cloned()?
;
404 let suffix
= ret
.file_name().unwrap(); // Checked when parsing attrs
406 let mut file_name
: OsString
= analysis_name
.into();
408 file_name
.push(suffix
);
409 ret
.set_file_name(file_name
);