1 //! A solver for dataflow problems.
3 use std
::ffi
::OsString
;
5 use std
::path
::PathBuf
;
8 use rustc_data_structures
::work_queue
::WorkQueue
;
9 use rustc_graphviz
as dot
;
10 use rustc_hir
::def_id
::DefId
;
11 use rustc_index
::bit_set
::BitSet
;
12 use rustc_index
::vec
::IndexVec
;
13 use rustc_middle
::mir
::{self, traversal, BasicBlock}
;
14 use rustc_middle
::ty
::{self, TyCtxt}
;
15 use rustc_span
::symbol
::{sym, Symbol}
;
19 visit_results
, Analysis
, Direction
, GenKillAnalysis
, GenKillSet
, ResultsCursor
, ResultsVisitor
,
21 use crate::util
::pretty
::dump_enabled
;
23 /// A dataflow analysis that has converged to fixpoint.
24 pub struct Results
<'tcx
, A
>
29 pub(super) entry_sets
: IndexVec
<BasicBlock
, BitSet
<A
::Idx
>>,
32 impl<A
> Results
<'tcx
, A
>
36 /// Creates a `ResultsCursor` that can inspect these `Results`.
37 pub fn into_results_cursor(self, body
: &'mir mir
::Body
<'tcx
>) -> ResultsCursor
<'mir
, 'tcx
, A
> {
38 ResultsCursor
::new(body
, self)
41 /// Gets the dataflow state for the given block.
42 pub fn entry_set_for_block(&self, block
: BasicBlock
) -> &BitSet
<A
::Idx
> {
43 &self.entry_sets
[block
]
48 body
: &'mir mir
::Body
<'tcx
>,
49 blocks
: impl IntoIterator
<Item
= BasicBlock
>,
50 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= BitSet
<A
::Idx
>>,
52 visit_results(body
, blocks
, self, vis
)
55 pub fn visit_reachable_with(
57 body
: &'mir mir
::Body
<'tcx
>,
58 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= BitSet
<A
::Idx
>>,
60 let blocks
= mir
::traversal
::reachable(body
);
61 visit_results(body
, blocks
.map(|(bb
, _
)| bb
), self, vis
)
64 pub fn visit_in_rpo_with(
66 body
: &'mir mir
::Body
<'tcx
>,
67 vis
: &mut impl ResultsVisitor
<'mir
, 'tcx
, FlowState
= BitSet
<A
::Idx
>>,
69 let blocks
= mir
::traversal
::reverse_postorder(body
);
70 visit_results(body
, blocks
.map(|(bb
, _
)| bb
), self, vis
)
74 /// A solver for dataflow problems.
75 pub struct Engine
<'a
, 'tcx
, A
>
79 bits_per_block
: usize,
81 body
: &'a mir
::Body
<'tcx
>,
83 dead_unwinds
: Option
<&'a BitSet
<BasicBlock
>>,
84 entry_sets
: IndexVec
<BasicBlock
, BitSet
<A
::Idx
>>,
87 /// Cached, cumulative transfer functions for each block.
88 trans_for_block
: Option
<IndexVec
<BasicBlock
, GenKillSet
<A
::Idx
>>>,
91 impl<A
> Engine
<'a
, 'tcx
, A
>
93 A
: GenKillAnalysis
<'tcx
>,
95 /// Creates a new `Engine` to solve a gen-kill dataflow problem.
98 body
: &'a mir
::Body
<'tcx
>,
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).
105 // In this case, there's no need to compute the block transfer functions ahead of time.
106 if !body
.is_cfg_cyclic() {
107 return Self::new(tcx
, body
, def_id
, analysis
, None
);
110 // Otherwise, compute and store the cumulative transfer function for each block.
112 let bits_per_block
= analysis
.bits_per_block(body
);
113 let mut trans_for_block
=
114 IndexVec
::from_elem(GenKillSet
::identity(bits_per_block
), 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 Self::new(tcx
, body
, def_id
, analysis
, Some(trans_for_block
))
125 impl<A
> Engine
<'a
, 'tcx
, A
>
129 /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
132 /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
133 /// better performance.
136 body
: &'a mir
::Body
<'tcx
>,
140 Self::new(tcx
, body
, def_id
, analysis
, None
)
145 body
: &'a mir
::Body
<'tcx
>,
148 trans_for_block
: Option
<IndexVec
<BasicBlock
, GenKillSet
<A
::Idx
>>>,
150 let bits_per_block
= analysis
.bits_per_block(body
);
152 let bottom_value_set
= if A
::BOTTOM_VALUE
{
153 BitSet
::new_filled(bits_per_block
)
155 BitSet
::new_empty(bits_per_block
)
158 let mut entry_sets
= IndexVec
::from_elem(bottom_value_set
.clone(), body
.basic_blocks());
159 analysis
.initialize_start_block(body
, &mut entry_sets
[mir
::START_BLOCK
]);
161 if A
::Direction
::is_backward() && entry_sets
[mir
::START_BLOCK
] != bottom_value_set
{
162 bug
!("`initialize_start_block` is not yet supported for backward dataflow analyses");
177 /// Signals that we do not want dataflow state to propagate across unwind edges for these
180 /// You must take care that `dead_unwinds` does not contain a `BasicBlock` that *can* actually
181 /// unwind during execution. Otherwise, your dataflow results will not be correct.
182 pub fn dead_unwinds(mut self, dead_unwinds
: &'a BitSet
<BasicBlock
>) -> Self {
183 self.dead_unwinds
= Some(dead_unwinds
);
187 /// Computes the fixpoint for this dataflow problem and returns it.
188 pub fn iterate_to_fixpoint(self) -> Results
<'tcx
, A
> {
201 let mut dirty_queue
: WorkQueue
<BasicBlock
> =
202 WorkQueue
::with_none(body
.basic_blocks().len());
204 if A
::Direction
::is_forward() {
205 for (bb
, _
) in traversal
::reverse_postorder(body
) {
206 dirty_queue
.insert(bb
);
209 // Reverse post-order on the reverse CFG may generate a better iteration order for
210 // backward dataflow analyses, but probably not enough to matter.
211 for (bb
, _
) in traversal
::postorder(body
) {
212 dirty_queue
.insert(bb
);
216 let mut state
= BitSet
::new_empty(bits_per_block
);
217 while let Some(bb
) = dirty_queue
.pop() {
218 let bb_data
= &body
[bb
];
220 // Apply the block transfer function, using the cached one if it exists.
221 state
.overwrite(&entry_sets
[bb
]);
222 match &trans_for_block
{
223 Some(trans_for_block
) => trans_for_block
[bb
].apply(&mut state
),
224 None
=> A
::Direction
::apply_effects_in_block(&analysis
, &mut state
, bb
, bb_data
),
227 A
::Direction
::join_state_into_successors_of(
234 |target
: BasicBlock
, state
: &BitSet
<A
::Idx
>| {
235 let set_changed
= analysis
.join(&mut entry_sets
[target
], state
);
237 dirty_queue
.insert(target
);
243 let results
= Results { analysis, entry_sets }
;
245 let res
= write_graphviz_results(tcx
, def_id
, &body
, &results
, trans_for_block
);
246 if let Err(e
) = res
{
247 warn
!("Failed to write graphviz dataflow results: {}", e
);
256 /// Writes a DOT file containing the results of a dataflow analysis if the user requested it via
257 /// `rustc_mir` attributes.
258 fn write_graphviz_results
<A
>(
261 body
: &mir
::Body
<'tcx
>,
262 results
: &Results
<'tcx
, A
>,
263 block_transfer_functions
: Option
<IndexVec
<BasicBlock
, GenKillSet
<A
::Idx
>>>,
264 ) -> std
::io
::Result
<()>
268 let attrs
= match RustcMirAttrs
::parse(tcx
, def_id
) {
271 // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse`
272 Err(()) => return Ok(()),
275 let path
= match attrs
.output_path(A
::NAME
) {
278 None
if tcx
.sess
.opts
.debugging_opts
.dump_mir_dataflow
279 && dump_enabled(tcx
, A
::NAME
, def_id
) =>
281 let mut path
= PathBuf
::from(&tcx
.sess
.opts
.debugging_opts
.dump_mir_dir
);
283 let item_name
= ty
::print
::with_forced_impl_filename_line(|| {
284 tcx
.def_path(def_id
).to_filename_friendly_no_crate()
286 path
.push(format
!("rustc.{}.{}.dot", item_name
, A
::NAME
));
290 None
=> return Ok(()),
293 let bits_per_block
= results
.analysis
.bits_per_block(body
);
295 let mut formatter
: Box
<dyn graphviz
::StateFormatter
<'tcx
, _
>> = match attrs
.formatter
{
296 Some(sym
::two_phase
) => Box
::new(graphviz
::TwoPhaseDiff
::new(bits_per_block
)),
297 Some(sym
::gen_kill
) => {
298 if let Some(trans_for_block
) = block_transfer_functions
{
299 Box
::new(graphviz
::BlockTransferFunc
::new(body
, trans_for_block
))
301 Box
::new(graphviz
::SimpleDiff
::new(body
, &results
))
305 // Default to the `SimpleDiff` output style.
306 _
=> Box
::new(graphviz
::SimpleDiff
::new(body
, &results
)),
309 debug
!("printing dataflow results for {:?} to {}", def_id
, path
.display());
310 let mut buf
= Vec
::new();
312 let graphviz
= graphviz
::Formatter
::new(body
, def_id
, results
, &mut *formatter
);
313 dot
::render_opts(&graphviz
, &mut buf
, &[dot
::RenderOption
::Monospace
])?
;
315 if let Some(parent
) = path
.parent() {
316 fs
::create_dir_all(parent
)?
;
318 fs
::write(&path
, buf
)?
;
324 struct RustcMirAttrs
{
325 basename_and_suffix
: Option
<PathBuf
>,
326 formatter
: Option
<Symbol
>,
330 fn parse(tcx
: TyCtxt
<'tcx
>, def_id
: DefId
) -> Result
<Self, ()> {
331 let attrs
= tcx
.get_attrs(def_id
);
333 let mut result
= Ok(());
334 let mut ret
= RustcMirAttrs
::default();
336 let rustc_mir_attrs
= attrs
338 .filter(|attr
| tcx
.sess
.check_name(attr
, sym
::rustc_mir
))
339 .flat_map(|attr
| attr
.meta_item_list().into_iter().flat_map(|v
| v
.into_iter()));
341 for attr
in rustc_mir_attrs
{
342 let attr_result
= if attr
.has_name(sym
::borrowck_graphviz_postflow
) {
343 Self::set_field(&mut ret
.basename_and_suffix
, tcx
, &attr
, |s
| {
344 let path
= PathBuf
::from(s
.to_string());
345 match path
.file_name() {
348 tcx
.sess
.span_err(attr
.span(), "path must end in a filename");
353 } else if attr
.has_name(sym
::borrowck_graphviz_format
) {
354 Self::set_field(&mut ret
.formatter
, tcx
, &attr
, |s
| match s
{
355 sym
::gen_kill
| sym
::two_phase
=> Ok(s
),
357 tcx
.sess
.span_err(attr
.span(), "unknown formatter");
365 result
= result
.and(attr_result
);
372 field
: &mut Option
<T
>,
374 attr
: &ast
::NestedMetaItem
,
375 mapper
: impl FnOnce(Symbol
) -> Result
<T
, ()>,
376 ) -> Result
<(), ()> {
379 .span_err(attr
.span(), &format
!("duplicate values for `{}`", attr
.name_or_empty()));
384 if let Some(s
) = attr
.value_str() {
385 *field
= Some(mapper(s
)?
);
389 .span_err(attr
.span(), &format
!("`{}` requires an argument", attr
.name_or_empty()));
394 /// Returns the path where dataflow results should be written, or `None`
395 /// `borrowck_graphviz_postflow` was not specified.
397 /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
399 /// "path/suffix.dot" -> "path/analysis_name_suffix.dot"
400 fn output_path(&self, analysis_name
: &str) -> Option
<PathBuf
> {
401 let mut ret
= self.basename_and_suffix
.as_ref().cloned()?
;
402 let suffix
= ret
.file_name().unwrap(); // Checked when parsing attrs
404 let mut file_name
: OsString
= analysis_name
.into();
406 file_name
.push(suffix
);
407 ret
.set_file_name(file_name
);