From d78e7bbeff6006feef9c04140c1e6bf67bdbef00 Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Wed, 30 Oct 2024 09:34:37 +1100 Subject: Remove `Engine`. It's no longer needed. `Engine::iterate_to_fixpoint` can be inlined into `Analysis::iterate_to_fixpoint` and removed. The commit also renames `engine.rs` as `results.rs`. --- .../rustc_mir_dataflow/src/framework/engine.rs | 311 --------------------- compiler/rustc_mir_dataflow/src/framework/mod.rs | 78 +++++- .../rustc_mir_dataflow/src/framework/results.rs | 223 +++++++++++++++ 3 files changed, 295 insertions(+), 317 deletions(-) delete mode 100644 compiler/rustc_mir_dataflow/src/framework/engine.rs create mode 100644 compiler/rustc_mir_dataflow/src/framework/results.rs (limited to 'compiler/rustc_mir_dataflow/src/framework') diff --git a/compiler/rustc_mir_dataflow/src/framework/engine.rs b/compiler/rustc_mir_dataflow/src/framework/engine.rs deleted file mode 100644 index 44fda84ce03..00000000000 --- a/compiler/rustc_mir_dataflow/src/framework/engine.rs +++ /dev/null @@ -1,311 +0,0 @@ -//! A solver for dataflow problems. - -use std::ffi::OsString; -use std::path::PathBuf; - -use rustc_data_structures::work_queue::WorkQueue; -use rustc_hir::def_id::DefId; -use rustc_index::IndexVec; -use rustc_middle::bug; -use rustc_middle::mir::{self, BasicBlock, create_dump_file, dump_enabled, traversal}; -use rustc_middle::ty::TyCtxt; -use rustc_middle::ty::print::with_no_trimmed_paths; -use rustc_span::symbol::{Symbol, sym}; -use tracing::{debug, error}; -use {rustc_ast as ast, rustc_graphviz as dot}; - -use super::fmt::DebugWithContext; -use super::{ - Analysis, Direction, JoinSemiLattice, ResultsCursor, ResultsVisitor, graphviz, visit_results, -}; -use crate::errors::{ - DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter, -}; - -type EntrySets<'tcx, A> = IndexVec>::Domain>; - -/// A dataflow analysis that has converged to fixpoint. -#[derive(Clone)] -pub struct Results<'tcx, A> -where - A: Analysis<'tcx>, -{ - pub analysis: A, - pub(super) entry_sets: EntrySets<'tcx, A>, -} - -impl<'tcx, A> Results<'tcx, A> -where - A: Analysis<'tcx>, -{ - /// Creates a `ResultsCursor` that can inspect these `Results`. - pub fn into_results_cursor<'mir>( - self, - body: &'mir mir::Body<'tcx>, - ) -> ResultsCursor<'mir, 'tcx, A> { - ResultsCursor::new(body, self) - } - - /// Gets the dataflow state for the given block. - pub fn entry_set_for_block(&self, block: BasicBlock) -> &A::Domain { - &self.entry_sets[block] - } - - pub fn visit_with<'mir>( - &mut self, - body: &'mir mir::Body<'tcx>, - blocks: impl IntoIterator, - vis: &mut impl ResultsVisitor<'mir, 'tcx, Self, Domain = A::Domain>, - ) { - visit_results(body, blocks, self, vis) - } - - pub fn visit_reachable_with<'mir>( - &mut self, - body: &'mir mir::Body<'tcx>, - vis: &mut impl ResultsVisitor<'mir, 'tcx, Self, Domain = A::Domain>, - ) { - let blocks = mir::traversal::reachable(body); - visit_results(body, blocks.map(|(bb, _)| bb), self, vis) - } -} - -/// A solver for dataflow problems. -pub struct Engine; - -impl Engine { - /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer - /// function. - pub(crate) fn iterate_to_fixpoint<'mir, 'tcx, A>( - tcx: TyCtxt<'tcx>, - body: &'mir mir::Body<'tcx>, - mut analysis: A, - pass_name: Option<&'static str>, - ) -> Results<'tcx, A> - where - A: Analysis<'tcx>, - A::Domain: DebugWithContext + Clone + JoinSemiLattice, - { - let mut entry_sets = - IndexVec::from_fn_n(|_| analysis.bottom_value(body), body.basic_blocks.len()); - analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]); - - if A::Direction::IS_BACKWARD && entry_sets[mir::START_BLOCK] != analysis.bottom_value(body) - { - bug!("`initialize_start_block` is not yet supported for backward dataflow analyses"); - } - - let mut dirty_queue: WorkQueue = WorkQueue::with_none(body.basic_blocks.len()); - - if A::Direction::IS_FORWARD { - for (bb, _) in traversal::reverse_postorder(body) { - dirty_queue.insert(bb); - } - } else { - // Reverse post-order on the reverse CFG may generate a better iteration order for - // backward dataflow analyses, but probably not enough to matter. - for (bb, _) in traversal::postorder(body) { - dirty_queue.insert(bb); - } - } - - // `state` is not actually used between iterations; - // this is just an optimization to avoid reallocating - // every iteration. - let mut state = analysis.bottom_value(body); - while let Some(bb) = dirty_queue.pop() { - let bb_data = &body[bb]; - - // Set the state to the entry state of the block. - // This is equivalent to `state = entry_sets[bb].clone()`, - // but it saves an allocation, thus improving compile times. - state.clone_from(&entry_sets[bb]); - - // Apply the block transfer function, using the cached one if it exists. - let edges = - A::Direction::apply_effects_in_block(&mut analysis, &mut state, bb, bb_data); - - A::Direction::join_state_into_successors_of( - &mut analysis, - body, - &mut state, - bb, - edges, - |target: BasicBlock, state: &A::Domain| { - let set_changed = entry_sets[target].join(state); - if set_changed { - dirty_queue.insert(target); - } - }, - ); - } - - let results = Results { analysis, entry_sets }; - - if tcx.sess.opts.unstable_opts.dump_mir_dataflow { - let (res, results) = write_graphviz_results(tcx, body, results, pass_name); - if let Err(e) = res { - error!("Failed to write graphviz dataflow results: {}", e); - } - results - } else { - results - } - } -} - -// Graphviz - -/// Writes a DOT file containing the results of a dataflow analysis if the user requested it via -/// `rustc_mir` attributes and `-Z dump-mir-dataflow`. The `Result` in and the `Results` out are -/// the same. -fn write_graphviz_results<'tcx, A>( - tcx: TyCtxt<'tcx>, - body: &mir::Body<'tcx>, - results: Results<'tcx, A>, - pass_name: Option<&'static str>, -) -> (std::io::Result<()>, Results<'tcx, A>) -where - A: Analysis<'tcx>, - A::Domain: DebugWithContext, -{ - use std::fs; - use std::io::Write; - - let def_id = body.source.def_id(); - let Ok(attrs) = RustcMirAttrs::parse(tcx, def_id) else { - // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse` - return (Ok(()), results); - }; - - let file = try { - match attrs.output_path(A::NAME) { - Some(path) => { - debug!("printing dataflow results for {:?} to {}", def_id, path.display()); - if let Some(parent) = path.parent() { - fs::create_dir_all(parent)?; - } - fs::File::create_buffered(&path)? - } - - None if dump_enabled(tcx, A::NAME, def_id) => { - create_dump_file(tcx, "dot", false, A::NAME, &pass_name.unwrap_or("-----"), body)? - } - - _ => return (Ok(()), results), - } - }; - let mut file = match file { - Ok(f) => f, - Err(e) => return (Err(e), results), - }; - - let style = match attrs.formatter { - Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter, - _ => graphviz::OutputStyle::AfterOnly, - }; - - let mut buf = Vec::new(); - - let graphviz = graphviz::Formatter::new(body, results, style); - let mut render_opts = - vec![dot::RenderOption::Fontname(tcx.sess.opts.unstable_opts.graphviz_font.clone())]; - if tcx.sess.opts.unstable_opts.graphviz_dark_mode { - render_opts.push(dot::RenderOption::DarkTheme); - } - let r = with_no_trimmed_paths!(dot::render_opts(&graphviz, &mut buf, &render_opts)); - - let lhs = try { - r?; - file.write_all(&buf)?; - }; - - (lhs, graphviz.into_results()) -} - -#[derive(Default)] -struct RustcMirAttrs { - basename_and_suffix: Option, - formatter: Option, -} - -impl RustcMirAttrs { - fn parse(tcx: TyCtxt<'_>, def_id: DefId) -> Result { - let mut result = Ok(()); - let mut ret = RustcMirAttrs::default(); - - let rustc_mir_attrs = tcx - .get_attrs(def_id, sym::rustc_mir) - .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter())); - - for attr in rustc_mir_attrs { - let attr_result = if attr.has_name(sym::borrowck_graphviz_postflow) { - Self::set_field(&mut ret.basename_and_suffix, tcx, &attr, |s| { - let path = PathBuf::from(s.to_string()); - match path.file_name() { - Some(_) => Ok(path), - None => { - tcx.dcx().emit_err(PathMustEndInFilename { span: attr.span() }); - Err(()) - } - } - }) - } else if attr.has_name(sym::borrowck_graphviz_format) { - Self::set_field(&mut ret.formatter, tcx, &attr, |s| match s { - sym::gen_kill | sym::two_phase => Ok(s), - _ => { - tcx.dcx().emit_err(UnknownFormatter { span: attr.span() }); - Err(()) - } - }) - } else { - Ok(()) - }; - - result = result.and(attr_result); - } - - result.map(|()| ret) - } - - fn set_field( - field: &mut Option, - tcx: TyCtxt<'_>, - attr: &ast::MetaItemInner, - mapper: impl FnOnce(Symbol) -> Result, - ) -> Result<(), ()> { - if field.is_some() { - tcx.dcx() - .emit_err(DuplicateValuesFor { span: attr.span(), name: attr.name_or_empty() }); - - return Err(()); - } - - if let Some(s) = attr.value_str() { - *field = Some(mapper(s)?); - Ok(()) - } else { - tcx.dcx() - .emit_err(RequiresAnArgument { span: attr.span(), name: attr.name_or_empty() }); - Err(()) - } - } - - /// Returns the path where dataflow results should be written, or `None` - /// `borrowck_graphviz_postflow` was not specified. - /// - /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`: - /// - /// "path/suffix.dot" -> "path/analysis_name_suffix.dot" - fn output_path(&self, analysis_name: &str) -> Option { - let mut ret = self.basename_and_suffix.as_ref().cloned()?; - let suffix = ret.file_name().unwrap(); // Checked when parsing attrs - - let mut file_name: OsString = analysis_name.into(); - file_name.push("_"); - file_name.push(suffix); - ret.set_file_name(file_name); - - Some(ret) - } -} diff --git a/compiler/rustc_mir_dataflow/src/framework/mod.rs b/compiler/rustc_mir_dataflow/src/framework/mod.rs index 5ad05921b4f..8f81da8bb04 100644 --- a/compiler/rustc_mir_dataflow/src/framework/mod.rs +++ b/compiler/rustc_mir_dataflow/src/framework/mod.rs @@ -33,25 +33,29 @@ use std::cmp::Ordering; -use rustc_index::Idx; +use rustc_data_structures::work_queue::WorkQueue; use rustc_index::bit_set::{BitSet, ChunkedBitSet, HybridBitSet}; -use rustc_middle::mir::{self, BasicBlock, CallReturnPlaces, Location, TerminatorEdges}; +use rustc_index::{Idx, IndexVec}; +use rustc_middle::bug; +use rustc_middle::mir::{self, BasicBlock, CallReturnPlaces, Location, TerminatorEdges, traversal}; use rustc_middle::ty::TyCtxt; +use tracing::error; +use self::results::write_graphviz_results; use super::fmt::DebugWithContext; mod cursor; mod direction; -mod engine; pub mod fmt; pub mod graphviz; pub mod lattice; +mod results; mod visitor; pub use self::cursor::ResultsCursor; pub use self::direction::{Backward, Direction, Forward}; -pub use self::engine::{Engine, Results}; pub use self::lattice::{JoinSemiLattice, MaybeReachable}; +pub use self::results::Results; pub use self::visitor::{ResultsVisitable, ResultsVisitor, visit_results}; /// Analysis domains are all bitsets of various kinds. This trait holds @@ -238,7 +242,7 @@ pub trait Analysis<'tcx> { /// Without a `pass_name` to differentiates them, only the results for the latest run will be /// saved. fn iterate_to_fixpoint<'mir>( - self, + mut self, tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>, pass_name: Option<&'static str>, @@ -247,7 +251,69 @@ pub trait Analysis<'tcx> { Self: Sized, Self::Domain: DebugWithContext, { - Engine::iterate_to_fixpoint(tcx, body, self, pass_name) + let mut entry_sets = + IndexVec::from_fn_n(|_| self.bottom_value(body), body.basic_blocks.len()); + self.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]); + + if Self::Direction::IS_BACKWARD && entry_sets[mir::START_BLOCK] != self.bottom_value(body) { + bug!("`initialize_start_block` is not yet supported for backward dataflow analyses"); + } + + let mut dirty_queue: WorkQueue = WorkQueue::with_none(body.basic_blocks.len()); + + if Self::Direction::IS_FORWARD { + for (bb, _) in traversal::reverse_postorder(body) { + dirty_queue.insert(bb); + } + } else { + // Reverse post-order on the reverse CFG may generate a better iteration order for + // backward dataflow analyses, but probably not enough to matter. + for (bb, _) in traversal::postorder(body) { + dirty_queue.insert(bb); + } + } + + // `state` is not actually used between iterations; + // this is just an optimization to avoid reallocating + // every iteration. + let mut state = self.bottom_value(body); + while let Some(bb) = dirty_queue.pop() { + let bb_data = &body[bb]; + + // Set the state to the entry state of the block. + // This is equivalent to `state = entry_sets[bb].clone()`, + // but it saves an allocation, thus improving compile times. + state.clone_from(&entry_sets[bb]); + + // Apply the block transfer function, using the cached one if it exists. + let edges = Self::Direction::apply_effects_in_block(&mut self, &mut state, bb, bb_data); + + Self::Direction::join_state_into_successors_of( + &mut self, + body, + &mut state, + bb, + edges, + |target: BasicBlock, state: &Self::Domain| { + let set_changed = entry_sets[target].join(state); + if set_changed { + dirty_queue.insert(target); + } + }, + ); + } + + let results = Results { analysis: self, entry_sets }; + + if tcx.sess.opts.unstable_opts.dump_mir_dataflow { + let (res, results) = write_graphviz_results(tcx, body, results, pass_name); + if let Err(e) = res { + error!("Failed to write graphviz dataflow results: {}", e); + } + results + } else { + results + } } } diff --git a/compiler/rustc_mir_dataflow/src/framework/results.rs b/compiler/rustc_mir_dataflow/src/framework/results.rs new file mode 100644 index 00000000000..366fcbf33ba --- /dev/null +++ b/compiler/rustc_mir_dataflow/src/framework/results.rs @@ -0,0 +1,223 @@ +//! Dataflow analysis results. + +use std::ffi::OsString; +use std::path::PathBuf; + +use rustc_hir::def_id::DefId; +use rustc_index::IndexVec; +use rustc_middle::mir::{self, BasicBlock, create_dump_file, dump_enabled, traversal}; +use rustc_middle::ty::TyCtxt; +use rustc_middle::ty::print::with_no_trimmed_paths; +use rustc_span::symbol::{Symbol, sym}; +use tracing::debug; +use {rustc_ast as ast, rustc_graphviz as dot}; + +use super::fmt::DebugWithContext; +use super::{Analysis, ResultsCursor, ResultsVisitor, graphviz, visit_results}; +use crate::errors::{ + DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter, +}; + +type EntrySets<'tcx, A> = IndexVec>::Domain>; + +/// A dataflow analysis that has converged to fixpoint. +#[derive(Clone)] +pub struct Results<'tcx, A> +where + A: Analysis<'tcx>, +{ + pub analysis: A, + pub(super) entry_sets: EntrySets<'tcx, A>, +} + +impl<'tcx, A> Results<'tcx, A> +where + A: Analysis<'tcx>, +{ + /// Creates a `ResultsCursor` that can inspect these `Results`. + pub fn into_results_cursor<'mir>( + self, + body: &'mir mir::Body<'tcx>, + ) -> ResultsCursor<'mir, 'tcx, A> { + ResultsCursor::new(body, self) + } + + /// Gets the dataflow state for the given block. + pub fn entry_set_for_block(&self, block: BasicBlock) -> &A::Domain { + &self.entry_sets[block] + } + + pub fn visit_with<'mir>( + &mut self, + body: &'mir mir::Body<'tcx>, + blocks: impl IntoIterator, + vis: &mut impl ResultsVisitor<'mir, 'tcx, Self, Domain = A::Domain>, + ) { + visit_results(body, blocks, self, vis) + } + + pub fn visit_reachable_with<'mir>( + &mut self, + body: &'mir mir::Body<'tcx>, + vis: &mut impl ResultsVisitor<'mir, 'tcx, Self, Domain = A::Domain>, + ) { + let blocks = traversal::reachable(body); + visit_results(body, blocks.map(|(bb, _)| bb), self, vis) + } +} + +// Graphviz + +/// Writes a DOT file containing the results of a dataflow analysis if the user requested it via +/// `rustc_mir` attributes and `-Z dump-mir-dataflow`. The `Result` in and the `Results` out are +/// the same. +pub(super) fn write_graphviz_results<'tcx, A>( + tcx: TyCtxt<'tcx>, + body: &mir::Body<'tcx>, + results: Results<'tcx, A>, + pass_name: Option<&'static str>, +) -> (std::io::Result<()>, Results<'tcx, A>) +where + A: Analysis<'tcx>, + A::Domain: DebugWithContext, +{ + use std::fs; + use std::io::Write; + + let def_id = body.source.def_id(); + let Ok(attrs) = RustcMirAttrs::parse(tcx, def_id) else { + // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse` + return (Ok(()), results); + }; + + let file = try { + match attrs.output_path(A::NAME) { + Some(path) => { + debug!("printing dataflow results for {:?} to {}", def_id, path.display()); + if let Some(parent) = path.parent() { + fs::create_dir_all(parent)?; + } + fs::File::create_buffered(&path)? + } + + None if dump_enabled(tcx, A::NAME, def_id) => { + create_dump_file(tcx, "dot", false, A::NAME, &pass_name.unwrap_or("-----"), body)? + } + + _ => return (Ok(()), results), + } + }; + let mut file = match file { + Ok(f) => f, + Err(e) => return (Err(e), results), + }; + + let style = match attrs.formatter { + Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter, + _ => graphviz::OutputStyle::AfterOnly, + }; + + let mut buf = Vec::new(); + + let graphviz = graphviz::Formatter::new(body, results, style); + let mut render_opts = + vec![dot::RenderOption::Fontname(tcx.sess.opts.unstable_opts.graphviz_font.clone())]; + if tcx.sess.opts.unstable_opts.graphviz_dark_mode { + render_opts.push(dot::RenderOption::DarkTheme); + } + let r = with_no_trimmed_paths!(dot::render_opts(&graphviz, &mut buf, &render_opts)); + + let lhs = try { + r?; + file.write_all(&buf)?; + }; + + (lhs, graphviz.into_results()) +} + +#[derive(Default)] +struct RustcMirAttrs { + basename_and_suffix: Option, + formatter: Option, +} + +impl RustcMirAttrs { + fn parse(tcx: TyCtxt<'_>, def_id: DefId) -> Result { + let mut result = Ok(()); + let mut ret = RustcMirAttrs::default(); + + let rustc_mir_attrs = tcx + .get_attrs(def_id, sym::rustc_mir) + .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter())); + + for attr in rustc_mir_attrs { + let attr_result = if attr.has_name(sym::borrowck_graphviz_postflow) { + Self::set_field(&mut ret.basename_and_suffix, tcx, &attr, |s| { + let path = PathBuf::from(s.to_string()); + match path.file_name() { + Some(_) => Ok(path), + None => { + tcx.dcx().emit_err(PathMustEndInFilename { span: attr.span() }); + Err(()) + } + } + }) + } else if attr.has_name(sym::borrowck_graphviz_format) { + Self::set_field(&mut ret.formatter, tcx, &attr, |s| match s { + sym::gen_kill | sym::two_phase => Ok(s), + _ => { + tcx.dcx().emit_err(UnknownFormatter { span: attr.span() }); + Err(()) + } + }) + } else { + Ok(()) + }; + + result = result.and(attr_result); + } + + result.map(|()| ret) + } + + fn set_field( + field: &mut Option, + tcx: TyCtxt<'_>, + attr: &ast::MetaItemInner, + mapper: impl FnOnce(Symbol) -> Result, + ) -> Result<(), ()> { + if field.is_some() { + tcx.dcx() + .emit_err(DuplicateValuesFor { span: attr.span(), name: attr.name_or_empty() }); + + return Err(()); + } + + if let Some(s) = attr.value_str() { + *field = Some(mapper(s)?); + Ok(()) + } else { + tcx.dcx() + .emit_err(RequiresAnArgument { span: attr.span(), name: attr.name_or_empty() }); + Err(()) + } + } + + /// Returns the path where dataflow results should be written, or `None` + /// `borrowck_graphviz_postflow` was not specified. + /// + /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`: + /// + /// "path/suffix.dot" -> "path/analysis_name_suffix.dot" + fn output_path(&self, analysis_name: &str) -> Option { + let mut ret = self.basename_and_suffix.as_ref().cloned()?; + let suffix = ret.file_name().unwrap(); // Checked when parsing attrs + + let mut file_name: OsString = analysis_name.into(); + file_name.push("_"); + file_name.push(suffix); + ret.set_file_name(file_name); + + Some(ret) + } +} -- cgit 1.4.1-3-g733a5