Auto merge of #68423 - Centril:rollup-bdjykrv, r=Centril
Rollup of 7 pull requests
Successful merges:
- #67686 (Simplify NodeHeader by avoiding slices in BTreeMaps with shared roots)
- #68140 (Implement `?const` opt-out for trait bounds)
- #68313 (Options IP_MULTICAST_TTL and IP_MULTICAST_LOOP are 1 byte on BSD)
- #68328 (Actually pass target LLVM args to LLVM)
- #68399 (check_match: misc unifications and ICE fixes)
- #68415 (tidy: fix most clippy warnings)
- #68416 (lowering: cleanup some hofs)
Failed merges:
r? @ghost
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index ccd2a96..3a7c650 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -215,6 +215,31 @@
}
}
+ /// Returns a partially initialized MIR body containing only a list of basic blocks.
+ ///
+ /// The returned MIR contains no `LocalDecl`s (even for the return place) or source scopes. It
+ /// is only useful for testing but cannot be `#[cfg(test)]` because it is used in a different
+ /// crate.
+ pub fn new_cfg_only(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>) -> Self {
+ Body {
+ phase: MirPhase::Build,
+ basic_blocks,
+ source_scopes: IndexVec::new(),
+ yield_ty: None,
+ generator_drop: None,
+ generator_layout: None,
+ local_decls: IndexVec::new(),
+ user_type_annotations: IndexVec::new(),
+ arg_count: 0,
+ spread_arg: None,
+ span: DUMMY_SP,
+ control_flow_destroyed: Vec::new(),
+ generator_kind: None,
+ var_debug_info: Vec::new(),
+ ignore_interior_mut_in_const_validation: false,
+ }
+ }
+
#[inline]
pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
&self.basic_blocks
diff --git a/src/librustc_mir/dataflow/generic.rs b/src/librustc_mir/dataflow/generic.rs
deleted file mode 100644
index d2ca4f1..0000000
--- a/src/librustc_mir/dataflow/generic.rs
+++ /dev/null
@@ -1,595 +0,0 @@
-//! Dataflow analysis with arbitrary transfer functions.
-//!
-//! This module is a work in progress. You should instead use `BitDenotation` in
-//! `librustc_mir/dataflow/mod.rs` and encode your transfer function as a [gen/kill set][gk]. In
-//! doing so, your analysis will run faster and you will be able to generate graphviz diagrams for
-//! debugging with no extra effort. The interface in this module is intended only for dataflow
-//! problems that cannot be expressed using gen/kill sets.
-//!
-//! FIXME(ecstaticmorse): In the long term, the plan is to preserve the existing `BitDenotation`
-//! interface, but make `Engine` and `ResultsCursor` the canonical way to perform and inspect a
-//! dataflow analysis. This requires porting the graphviz debugging logic to this module, deciding
-//! on a way to handle the `before` methods in `BitDenotation` and creating an adapter so that
-//! gen-kill problems can still be evaluated efficiently. See the discussion in [#64566] for more
-//! information.
-//!
-//! [gk]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems
-//! [#64566]: https://github.com/rust-lang/rust/pull/64566
-
-use std::borrow::Borrow;
-use std::cmp::Ordering;
-use std::ffi::OsString;
-use std::path::{Path, PathBuf};
-use std::{fs, io, ops};
-
-use rustc::mir::{self, traversal, BasicBlock, Location};
-use rustc::ty::{self, TyCtxt};
-use rustc_data_structures::work_queue::WorkQueue;
-use rustc_hir::def_id::DefId;
-use rustc_index::bit_set::BitSet;
-use rustc_index::vec::{Idx, IndexVec};
-use rustc_span::symbol::sym;
-
-use crate::dataflow::BottomValue;
-
-mod graphviz;
-
-/// A specific kind of dataflow analysis.
-///
-/// To run a dataflow analysis, one must set the initial state of the `START_BLOCK` via
-/// `initialize_start_block` and define a transfer function for each statement or terminator via
-/// the various `effect` methods. The entry set for all other basic blocks is initialized to
-/// `Self::BOTTOM_VALUE`. The dataflow `Engine` then iteratively updates the various entry sets for
-/// each block with the cumulative effects of the transfer functions of all preceding blocks.
-///
-/// You should use an `Engine` to actually run an analysis, and a `ResultsCursor` to inspect the
-/// results of that analysis like so:
-///
-/// ```ignore(cross-crate-imports)
-/// fn do_my_analysis(body: &mir::Body<'tcx>, dead_unwinds: &BitSet<BasicBlock>) {
-/// // `MyAnalysis` implements `Analysis`.
-/// let analysis = MyAnalysis::new();
-///
-/// let results = Engine::new(body, dead_unwinds, analysis).iterate_to_fixpoint();
-/// let mut cursor = ResultsCursor::new(body, results);
-///
-/// for (_, statement_index) in body.block_data[START_BLOCK].statements.iter_enumerated() {
-/// cursor.seek_after(Location { block: START_BLOCK, statement_index });
-/// let state = cursor.get();
-/// println!("{:?}", state);
-/// }
-/// }
-/// ```
-pub trait Analysis<'tcx>: BottomValue {
- /// The index type used to access the dataflow state.
- type Idx: Idx;
-
- /// A name, used for debugging, that describes this dataflow analysis.
- ///
- /// The name should be suitable as part of a filename, so avoid whitespace, slashes or periods
- /// and try to keep it short.
- const NAME: &'static str;
-
- /// How each element of your dataflow state will be displayed during debugging.
- ///
- /// By default, this is the `fmt::Debug` representation of `Self::Idx`.
- fn pretty_print_idx(&self, w: &mut impl io::Write, idx: Self::Idx) -> io::Result<()> {
- write!(w, "{:?}", idx)
- }
-
- /// The size of each bitvector allocated for each block.
- fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize;
-
- /// Mutates the entry set of the `START_BLOCK` to contain the initial state for dataflow
- /// analysis.
- fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>);
-
- /// Updates the current dataflow state with the effect of evaluating a statement.
- fn apply_statement_effect(
- &self,
- state: &mut BitSet<Self::Idx>,
- statement: &mir::Statement<'tcx>,
- location: Location,
- );
-
- /// Updates the current dataflow state with the effect of evaluating a terminator.
- ///
- /// Note that the effect of a successful return from a `Call` terminator should **not** be
- /// acounted for in this function. That should go in `apply_call_return_effect`. For example,
- /// in the `InitializedPlaces` analyses, the return place is not marked as initialized here.
- fn apply_terminator_effect(
- &self,
- state: &mut BitSet<Self::Idx>,
- terminator: &mir::Terminator<'tcx>,
- location: Location,
- );
-
- /// Updates the current dataflow state with the effect of a successful return from a `Call`
- /// terminator.
- ///
- /// This is separated from `apply_terminator_effect` to properly track state across
- /// unwind edges for `Call`s.
- fn apply_call_return_effect(
- &self,
- state: &mut BitSet<Self::Idx>,
- block: BasicBlock,
- func: &mir::Operand<'tcx>,
- args: &[mir::Operand<'tcx>],
- return_place: &mir::Place<'tcx>,
- );
-
- /// Applies the cumulative effect of an entire basic block to the dataflow state (except for
- /// `call_return_effect`, which is handled in the `Engine`).
- ///
- /// The default implementation calls `statement_effect` for every statement in the block before
- /// finally calling `terminator_effect`. However, some dataflow analyses are able to coalesce
- /// transfer functions for an entire block and apply them at once. Such analyses should
- /// override `block_effect`.
- fn apply_whole_block_effect(
- &self,
- state: &mut BitSet<Self::Idx>,
- block: BasicBlock,
- block_data: &mir::BasicBlockData<'tcx>,
- ) {
- for (statement_index, stmt) in block_data.statements.iter().enumerate() {
- let location = Location { block, statement_index };
- self.apply_statement_effect(state, stmt, location);
- }
-
- let location = Location { block, statement_index: block_data.statements.len() };
- self.apply_terminator_effect(state, block_data.terminator(), location);
- }
-
- /// Applies the cumulative effect of a sequence of statements (and possibly a terminator)
- /// within a single basic block.
- ///
- /// When called with `0..block_data.statements.len() + 1` as the statement range, this function
- /// is equivalent to `apply_whole_block_effect`.
- fn apply_partial_block_effect(
- &self,
- state: &mut BitSet<Self::Idx>,
- block: BasicBlock,
- block_data: &mir::BasicBlockData<'tcx>,
- mut range: ops::Range<usize>,
- ) {
- if range.is_empty() {
- return;
- }
-
- // The final location might be a terminator, so iterate through all statements until the
- // final one, then check to see whether the final one is a statement or terminator.
- //
- // This can't cause the range to wrap-around since we check that the range contains at
- // least one element above.
- range.end -= 1;
- let final_location = Location { block, statement_index: range.end };
-
- for statement_index in range {
- let location = Location { block, statement_index };
- let stmt = &block_data.statements[statement_index];
- self.apply_statement_effect(state, stmt, location);
- }
-
- if final_location.statement_index == block_data.statements.len() {
- let terminator = block_data.terminator();
- self.apply_terminator_effect(state, terminator, final_location);
- } else {
- let stmt = &block_data.statements[final_location.statement_index];
- self.apply_statement_effect(state, stmt, final_location);
- }
- }
-}
-
-#[derive(Clone, Copy, Debug)]
-enum CursorPosition {
- AtBlockStart(BasicBlock),
- After(Location),
-}
-
-impl CursorPosition {
- fn block(&self) -> BasicBlock {
- match *self {
- Self::AtBlockStart(block) => block,
- Self::After(Location { block, .. }) => block,
- }
- }
-}
-
-type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>;
-
-/// Inspect the results of dataflow analysis.
-///
-/// This cursor has linear performance when visiting statements in a block in order. Visiting
-/// statements within a block in reverse order is `O(n^2)`, where `n` is the number of statements
-/// in that block.
-pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>>
-where
- A: Analysis<'tcx>,
-{
- body: &'mir mir::Body<'tcx>,
- results: R,
- state: BitSet<A::Idx>,
-
- pos: CursorPosition,
-
- /// Whether the effects of `apply_call_return_effect` are currently stored in `state`.
- ///
- /// This flag ensures that multiple calls to `seek_after_assume_call_returns` with the same
- /// target only result in one invocation of `apply_call_return_effect`.
- is_call_return_effect_applied: bool,
-}
-
-impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
-where
- A: Analysis<'tcx>,
- R: Borrow<Results<'tcx, A>>,
-{
- /// Returns a new cursor for `results` that points to the start of the `START_BLOCK`.
- pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self {
- ResultsCursor {
- body,
- pos: CursorPosition::AtBlockStart(mir::START_BLOCK),
- is_call_return_effect_applied: false,
- state: results.borrow().entry_sets[mir::START_BLOCK].clone(),
- results,
- }
- }
-
- pub fn analysis(&self) -> &A {
- &self.results.borrow().analysis
- }
-
- /// Resets the cursor to the start of the given `block`.
- pub fn seek_to_block_start(&mut self, block: BasicBlock) {
- self.state.overwrite(&self.results.borrow().entry_sets[block]);
- self.pos = CursorPosition::AtBlockStart(block);
- self.is_call_return_effect_applied = false;
- }
-
- /// Updates the cursor to hold the dataflow state immediately before `target`.
- pub fn seek_before(&mut self, target: Location) {
- assert!(target <= self.body.terminator_loc(target.block));
-
- if target.statement_index == 0 {
- self.seek_to_block_start(target.block);
- } else {
- self._seek_after(Location {
- block: target.block,
- statement_index: target.statement_index - 1,
- });
- }
- }
-
- /// Updates the cursor to hold the dataflow state at `target`.
- ///
- /// If `target` is a `Call` terminator, `apply_call_return_effect` will not be called. See
- /// `seek_after_assume_call_returns` if you wish to observe the dataflow state upon a
- /// successful return.
- pub fn seek_after(&mut self, target: Location) {
- assert!(target <= self.body.terminator_loc(target.block));
-
- // This check ensures the correctness of a call to `seek_after_assume_call_returns`
- // followed by one to `seek_after` with the same target.
- if self.is_call_return_effect_applied {
- self.seek_to_block_start(target.block);
- }
-
- self._seek_after(target);
- }
-
- /// Equivalent to `seek_after`, but also calls `apply_call_return_effect` if `target` is a
- /// `Call` terminator whose callee is convergent.
- pub fn seek_after_assume_call_returns(&mut self, target: Location) {
- assert!(target <= self.body.terminator_loc(target.block));
-
- self._seek_after(target);
-
- if target != self.body.terminator_loc(target.block) {
- return;
- }
-
- let term = self.body.basic_blocks()[target.block].terminator();
- if let mir::TerminatorKind::Call {
- destination: Some((return_place, _)), func, args, ..
- } = &term.kind
- {
- if !self.is_call_return_effect_applied {
- self.is_call_return_effect_applied = true;
- self.results.borrow().analysis.apply_call_return_effect(
- &mut self.state,
- target.block,
- func,
- args,
- return_place,
- );
- }
- }
- }
-
- fn _seek_after(&mut self, target: Location) {
- let Location { block: target_block, statement_index: target_index } = target;
-
- if self.pos.block() != target_block {
- self.seek_to_block_start(target_block);
- }
-
- // If we're in the same block but after the target statement, we need to reset to the start
- // of the block.
- if let CursorPosition::After(Location { statement_index: curr_index, .. }) = self.pos {
- match curr_index.cmp(&target_index) {
- Ordering::Equal => return,
- Ordering::Less => {}
- Ordering::Greater => self.seek_to_block_start(target_block),
- }
- }
-
- // The cursor is now in the same block as the target location pointing at an earlier
- // statement.
- debug_assert_eq!(self.pos.block(), target_block);
- if let CursorPosition::After(Location { statement_index, .. }) = self.pos {
- debug_assert!(statement_index < target_index);
- }
-
- let first_unapplied_statement = match self.pos {
- CursorPosition::AtBlockStart(_) => 0,
- CursorPosition::After(Location { statement_index, .. }) => statement_index + 1,
- };
-
- let block_data = &self.body.basic_blocks()[target_block];
- self.results.borrow().analysis.apply_partial_block_effect(
- &mut self.state,
- target_block,
- block_data,
- first_unapplied_statement..target_index + 1,
- );
-
- self.pos = CursorPosition::After(target);
- self.is_call_return_effect_applied = false;
- }
-
- /// Gets the dataflow state at the current location.
- pub fn get(&self) -> &BitSet<A::Idx> {
- &self.state
- }
-}
-
-/// A completed dataflow analysis.
-pub struct Results<'tcx, A>
-where
- A: Analysis<'tcx>,
-{
- analysis: A,
- entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
-}
-
-/// All information required to iterate a dataflow analysis to fixpoint.
-pub struct Engine<'a, 'tcx, A>
-where
- A: Analysis<'tcx>,
-{
- analysis: A,
- bits_per_block: usize,
- tcx: TyCtxt<'tcx>,
- body: &'a mir::Body<'tcx>,
- def_id: DefId,
- dead_unwinds: &'a BitSet<BasicBlock>,
- entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
-}
-
-impl<A> Engine<'a, 'tcx, A>
-where
- A: Analysis<'tcx>,
-{
- pub fn new(
- tcx: TyCtxt<'tcx>,
- body: &'a mir::Body<'tcx>,
- def_id: DefId,
- dead_unwinds: &'a BitSet<BasicBlock>,
- analysis: A,
- ) -> Self {
- let bits_per_block = analysis.bits_per_block(body);
-
- let bottom_value_set = if A::BOTTOM_VALUE == true {
- BitSet::new_filled(bits_per_block)
- } else {
- BitSet::new_empty(bits_per_block)
- };
-
- let mut entry_sets = IndexVec::from_elem(bottom_value_set, body.basic_blocks());
- analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]);
-
- Engine { analysis, bits_per_block, tcx, body, def_id, dead_unwinds, entry_sets }
- }
-
- pub fn iterate_to_fixpoint(mut self) -> Results<'tcx, A> {
- let mut temp_state = BitSet::new_empty(self.bits_per_block);
-
- let mut dirty_queue: WorkQueue<BasicBlock> =
- WorkQueue::with_none(self.body.basic_blocks().len());
-
- for (bb, _) in traversal::reverse_postorder(self.body) {
- dirty_queue.insert(bb);
- }
-
- // Add blocks that are not reachable from START_BLOCK to the work queue. These blocks will
- // be processed after the ones added above.
- for bb in self.body.basic_blocks().indices() {
- dirty_queue.insert(bb);
- }
-
- while let Some(bb) = dirty_queue.pop() {
- let bb_data = &self.body[bb];
- let on_entry = &self.entry_sets[bb];
-
- temp_state.overwrite(on_entry);
- self.analysis.apply_whole_block_effect(&mut temp_state, bb, bb_data);
-
- self.propagate_bits_into_graph_successors_of(
- &mut temp_state,
- (bb, bb_data),
- &mut dirty_queue,
- );
- }
-
- let Engine { tcx, body, def_id, analysis, entry_sets, .. } = self;
-
- let results = Results { analysis, entry_sets };
-
- let attrs = tcx.get_attrs(def_id);
- if let Some(path) = get_dataflow_graphviz_output_path(tcx, attrs, A::NAME) {
- let result = write_dataflow_graphviz_results(body, def_id, &path, &results);
- if let Err(e) = result {
- warn!("Failed to write dataflow results to {}: {}", path.display(), e);
- }
- }
-
- results
- }
-
- fn propagate_bits_into_graph_successors_of(
- &mut self,
- in_out: &mut BitSet<A::Idx>,
- (bb, bb_data): (BasicBlock, &'a mir::BasicBlockData<'tcx>),
- dirty_list: &mut WorkQueue<BasicBlock>,
- ) {
- match bb_data.terminator().kind {
- mir::TerminatorKind::Return
- | mir::TerminatorKind::Resume
- | mir::TerminatorKind::Abort
- | mir::TerminatorKind::GeneratorDrop
- | mir::TerminatorKind::Unreachable => {}
-
- mir::TerminatorKind::Goto { target }
- | mir::TerminatorKind::Assert { target, cleanup: None, .. }
- | mir::TerminatorKind::Yield { resume: target, drop: None, .. }
- | mir::TerminatorKind::Drop { target, location: _, unwind: None }
- | mir::TerminatorKind::DropAndReplace { target, value: _, location: _, unwind: None } =>
- {
- self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
- }
-
- mir::TerminatorKind::Yield { resume: target, drop: Some(drop), .. } => {
- self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
- self.propagate_bits_into_entry_set_for(in_out, drop, dirty_list);
- }
-
- mir::TerminatorKind::Assert { target, cleanup: Some(unwind), .. }
- | mir::TerminatorKind::Drop { target, location: _, unwind: Some(unwind) }
- | mir::TerminatorKind::DropAndReplace {
- target,
- value: _,
- location: _,
- unwind: Some(unwind),
- } => {
- self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
- if !self.dead_unwinds.contains(bb) {
- self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
- }
- }
-
- mir::TerminatorKind::SwitchInt { ref targets, .. } => {
- for target in targets {
- self.propagate_bits_into_entry_set_for(in_out, *target, dirty_list);
- }
- }
-
- mir::TerminatorKind::Call { cleanup, ref destination, ref func, ref args, .. } => {
- if let Some(unwind) = cleanup {
- if !self.dead_unwinds.contains(bb) {
- self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
- }
- }
-
- if let Some((ref dest_place, dest_bb)) = *destination {
- // N.B.: This must be done *last*, after all other
- // propagation, as documented in comment above.
- self.analysis.apply_call_return_effect(in_out, bb, func, args, dest_place);
- self.propagate_bits_into_entry_set_for(in_out, dest_bb, dirty_list);
- }
- }
-
- mir::TerminatorKind::FalseEdges { real_target, imaginary_target } => {
- self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
- self.propagate_bits_into_entry_set_for(in_out, imaginary_target, dirty_list);
- }
-
- mir::TerminatorKind::FalseUnwind { real_target, unwind } => {
- self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
- if let Some(unwind) = unwind {
- if !self.dead_unwinds.contains(bb) {
- self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
- }
- }
- }
- }
- }
-
- fn propagate_bits_into_entry_set_for(
- &mut self,
- in_out: &BitSet<A::Idx>,
- bb: BasicBlock,
- dirty_queue: &mut WorkQueue<BasicBlock>,
- ) {
- let entry_set = &mut self.entry_sets[bb];
- let set_changed = self.analysis.join(entry_set, &in_out);
- if set_changed {
- dirty_queue.insert(bb);
- }
- }
-}
-
-/// Looks for attributes like `#[rustc_mir(borrowck_graphviz_postflow="./path/to/suffix.dot")]` and
-/// extracts the path with the given analysis name prepended to the suffix.
-///
-/// Returns `None` if no such attribute exists.
-fn get_dataflow_graphviz_output_path(
- tcx: TyCtxt<'tcx>,
- attrs: ty::Attributes<'tcx>,
- analysis: &str,
-) -> Option<PathBuf> {
- let mut rustc_mir_attrs = attrs
- .into_iter()
- .filter(|attr| attr.check_name(sym::rustc_mir))
- .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter()));
-
- let borrowck_graphviz_postflow =
- rustc_mir_attrs.find(|attr| attr.check_name(sym::borrowck_graphviz_postflow))?;
-
- let path_and_suffix = match borrowck_graphviz_postflow.value_str() {
- Some(p) => p,
- None => {
- tcx.sess.span_err(
- borrowck_graphviz_postflow.span(),
- "borrowck_graphviz_postflow requires a path",
- );
-
- return None;
- }
- };
-
- // Change "path/suffix.dot" to "path/analysis_name_suffix.dot"
- let mut ret = PathBuf::from(path_and_suffix.to_string());
- let suffix = ret.file_name().unwrap();
-
- let mut file_name: OsString = analysis.into();
- file_name.push("_");
- file_name.push(suffix);
- ret.set_file_name(file_name);
-
- Some(ret)
-}
-
-fn write_dataflow_graphviz_results<A: Analysis<'tcx>>(
- body: &mir::Body<'tcx>,
- def_id: DefId,
- path: &Path,
- results: &Results<'tcx, A>,
-) -> io::Result<()> {
- debug!("printing dataflow results for {:?} to {}", def_id, path.display());
-
- let mut buf = Vec::new();
- let graphviz = graphviz::Formatter::new(body, def_id, results);
-
- dot::render(&graphviz, &mut buf)?;
- fs::write(path, buf)
-}
diff --git a/src/librustc_mir/dataflow/generic/cursor.rs b/src/librustc_mir/dataflow/generic/cursor.rs
new file mode 100644
index 0000000..d2eff49
--- /dev/null
+++ b/src/librustc_mir/dataflow/generic/cursor.rs
@@ -0,0 +1,265 @@
+//! Random access inspection of the results of a dataflow analysis.
+
+use std::borrow::Borrow;
+
+use rustc::mir::{self, BasicBlock, Location};
+use rustc_index::bit_set::BitSet;
+
+use super::{Analysis, Results};
+
+/// A `ResultsCursor` that borrows the underlying `Results`.
+pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>;
+
+/// Allows random access inspection of the results of a dataflow analysis.
+///
+/// This cursor only has linear performance within a basic block when its statements are visited in
+/// order. In the worst case—when statements are visited in *reverse* order—performance will be
+/// quadratic in the number of statements in the block. The order in which basic blocks are
+/// inspected has no impact on performance.
+///
+/// A `ResultsCursor` can either own (the default) or borrow the dataflow results it inspects. The
+/// type of ownership is determined by `R` (see `ResultsRefCursor` above).
+pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>>
+where
+ A: Analysis<'tcx>,
+{
+ body: &'mir mir::Body<'tcx>,
+ results: R,
+ state: BitSet<A::Idx>,
+
+ pos: CursorPosition,
+
+ /// When this flag is set, the cursor is pointing at a `Call` terminator whose call return
+ /// effect has been applied to `state`.
+ ///
+ /// This flag helps to ensure that multiple calls to `seek_after_assume_call_returns` with the
+ /// same target will result in exactly one invocation of `apply_call_return_effect`. It is
+ /// sufficient to clear this only in `seek_to_block_start`, since seeking away from a
+ /// terminator will always require a cursor reset.
+ call_return_effect_applied: bool,
+}
+
+impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
+where
+ A: Analysis<'tcx>,
+ R: Borrow<Results<'tcx, A>>,
+{
+ /// Returns a new cursor for `results` that points to the start of the `START_BLOCK`.
+ pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self {
+ ResultsCursor {
+ body,
+ pos: CursorPosition::BlockStart(mir::START_BLOCK),
+ state: results.borrow().entry_sets[mir::START_BLOCK].clone(),
+ call_return_effect_applied: false,
+ results,
+ }
+ }
+
+ /// Returns the `Analysis` used to generate the underlying results.
+ pub fn analysis(&self) -> &A {
+ &self.results.borrow().analysis
+ }
+
+ /// Returns the dataflow state at the current location.
+ pub fn get(&self) -> &BitSet<A::Idx> {
+ &self.state
+ }
+
+ /// Resets the cursor to the start of the given basic block.
+ pub fn seek_to_block_start(&mut self, block: BasicBlock) {
+ self.state.overwrite(&self.results.borrow().entry_sets[block]);
+ self.pos = CursorPosition::BlockStart(block);
+ self.call_return_effect_applied = false;
+ }
+
+ /// Advances the cursor to hold all effects up to and including to the "before" effect of the
+ /// statement (or terminator) at the given location.
+ ///
+ /// If you wish to observe the full effect of a statement or terminator, not just the "before"
+ /// effect, use `seek_after` or `seek_after_assume_call_returns`.
+ pub fn seek_before(&mut self, target: Location) {
+ assert!(target <= self.body.terminator_loc(target.block));
+ self.seek_(target, false);
+ }
+
+ /// Advances the cursor to hold the full effect of all statements (and possibly closing
+ /// terminators) up to and including the `target`.
+ ///
+ /// If the `target` is a `Call` terminator, any call return effect for that terminator will
+ /// **not** be observed. Use `seek_after_assume_call_returns` if you wish to observe the call
+ /// return effect.
+ pub fn seek_after(&mut self, target: Location) {
+ assert!(target <= self.body.terminator_loc(target.block));
+
+ // If we have already applied the call return effect, we are currently pointing at a `Call`
+ // terminator. Unconditionally reset the dataflow cursor, since there is no way to "undo"
+ // the call return effect.
+ if self.call_return_effect_applied {
+ self.seek_to_block_start(target.block);
+ }
+
+ self.seek_(target, true);
+ }
+
+ /// Advances the cursor to hold all effects up to and including of the statement (or
+ /// terminator) at the given location.
+ ///
+ /// If the `target` is a `Call` terminator, any call return effect for that terminator will
+ /// be observed. Use `seek_after` if you do **not** wish to observe the call return effect.
+ pub fn seek_after_assume_call_returns(&mut self, target: Location) {
+ let terminator_loc = self.body.terminator_loc(target.block);
+ assert!(target.statement_index <= terminator_loc.statement_index);
+
+ self.seek_(target, true);
+
+ if target != terminator_loc {
+ return;
+ }
+
+ let terminator = self.body.basic_blocks()[target.block].terminator();
+ if let mir::TerminatorKind::Call {
+ destination: Some((return_place, _)), func, args, ..
+ } = &terminator.kind
+ {
+ if !self.call_return_effect_applied {
+ self.call_return_effect_applied = true;
+ self.results.borrow().analysis.apply_call_return_effect(
+ &mut self.state,
+ target.block,
+ func,
+ args,
+ return_place,
+ );
+ }
+ }
+ }
+
+ fn seek_(&mut self, target: Location, apply_after_effect_at_target: bool) {
+ use CursorPosition::*;
+
+ match self.pos {
+ // Return early if we are already at the target location.
+ Before(curr) if curr == target && !apply_after_effect_at_target => return,
+ After(curr) if curr == target && apply_after_effect_at_target => return,
+
+ // Otherwise, we must reset to the start of the target block if...
+
+ // we are in a different block entirely.
+ BlockStart(block) | Before(Location { block, .. }) | After(Location { block, .. })
+ if block != target.block =>
+ {
+ self.seek_to_block_start(target.block)
+ }
+
+ // we are in the same block but have advanced past the target statement.
+ Before(curr) | After(curr) if curr.statement_index > target.statement_index => {
+ self.seek_to_block_start(target.block)
+ }
+
+ // we have already applied the entire effect of a statement but only wish to observe
+ // its "before" effect.
+ After(curr)
+ if curr.statement_index == target.statement_index
+ && !apply_after_effect_at_target =>
+ {
+ self.seek_to_block_start(target.block)
+ }
+
+ // N.B., `call_return_effect_applied` is checked in `seek_after`, not here.
+ _ => (),
+ }
+
+ let analysis = &self.results.borrow().analysis;
+ let block_data = &self.body.basic_blocks()[target.block];
+
+ // At this point, the cursor is in the same block as the target location at an earlier
+ // statement.
+ debug_assert_eq!(target.block, self.pos.block());
+
+ // Find the first statement whose transfer function has not yet been applied.
+ let first_unapplied_statement = match self.pos {
+ BlockStart(_) => 0,
+ After(Location { statement_index, .. }) => statement_index + 1,
+
+ // If we have only applied the "before" effect for the current statement, apply the
+ // remainder before continuing.
+ Before(curr) => {
+ if curr.statement_index == block_data.statements.len() {
+ let terminator = block_data.terminator();
+ analysis.apply_terminator_effect(&mut self.state, terminator, curr);
+ } else {
+ let statement = &block_data.statements[curr.statement_index];
+ analysis.apply_statement_effect(&mut self.state, statement, curr);
+ }
+
+ // If all we needed to do was go from `Before` to `After` in the same statement,
+ // we are now done.
+ if curr.statement_index == target.statement_index {
+ debug_assert!(apply_after_effect_at_target);
+ self.pos = After(target);
+ return;
+ }
+
+ curr.statement_index + 1
+ }
+ };
+
+ // We have now applied all effects prior to `first_unapplied_statement`.
+
+ // Apply the effects of all statements before `target`.
+ let mut location = Location { block: target.block, statement_index: 0 };
+ for statement_index in first_unapplied_statement..target.statement_index {
+ location.statement_index = statement_index;
+ let statement = &block_data.statements[statement_index];
+ analysis.apply_before_statement_effect(&mut self.state, statement, location);
+ analysis.apply_statement_effect(&mut self.state, statement, location);
+ }
+
+ // Apply the effect of the statement (or terminator) at `target`.
+ location.statement_index = target.statement_index;
+ if target.statement_index == block_data.statements.len() {
+ let terminator = &block_data.terminator();
+ analysis.apply_before_terminator_effect(&mut self.state, terminator, location);
+
+ if apply_after_effect_at_target {
+ analysis.apply_terminator_effect(&mut self.state, terminator, location);
+ self.pos = After(target);
+ } else {
+ self.pos = Before(target);
+ }
+ } else {
+ let statement = &block_data.statements[target.statement_index];
+ analysis.apply_before_statement_effect(&mut self.state, statement, location);
+
+ if apply_after_effect_at_target {
+ analysis.apply_statement_effect(&mut self.state, statement, location);
+ self.pos = After(target)
+ } else {
+ self.pos = Before(target);
+ }
+ }
+ }
+}
+
+#[derive(Clone, Copy, Debug)]
+enum CursorPosition {
+ /// No effects within this block have been applied.
+ BlockStart(BasicBlock),
+
+ /// Only the "before" effect of the statement (or terminator) at this location has been
+ /// applied (along with the effects of all previous statements).
+ Before(Location),
+
+ /// The effects of all statements up to and including the one at this location have been
+ /// applied.
+ After(Location),
+}
+
+impl CursorPosition {
+ fn block(&self) -> BasicBlock {
+ match *self {
+ Self::BlockStart(block) => block,
+ Self::Before(loc) | Self::After(loc) => loc.block,
+ }
+ }
+}
diff --git a/src/librustc_mir/dataflow/generic/engine.rs b/src/librustc_mir/dataflow/generic/engine.rs
new file mode 100644
index 0000000..c0152b0
--- /dev/null
+++ b/src/librustc_mir/dataflow/generic/engine.rs
@@ -0,0 +1,427 @@
+//! A solver for dataflow problems.
+
+use std::ffi::OsString;
+use std::fs;
+use std::path::PathBuf;
+
+use rustc::mir::{self, traversal, BasicBlock, Location};
+use rustc::ty::TyCtxt;
+use rustc_data_structures::work_queue::WorkQueue;
+use rustc_hir::def_id::DefId;
+use rustc_index::bit_set::BitSet;
+use rustc_index::vec::IndexVec;
+use rustc_span::symbol::{sym, Symbol};
+use syntax::ast;
+
+use super::graphviz;
+use super::{Analysis, GenKillAnalysis, GenKillSet, Results};
+
+/// A solver for dataflow problems.
+pub struct Engine<'a, 'tcx, A>
+where
+ A: Analysis<'tcx>,
+{
+ bits_per_block: usize,
+ tcx: TyCtxt<'tcx>,
+ body: &'a mir::Body<'tcx>,
+ def_id: DefId,
+ dead_unwinds: Option<&'a BitSet<BasicBlock>>,
+ entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
+ analysis: A,
+
+ /// Cached, cumulative transfer functions for each block.
+ trans_for_block: Option<IndexVec<BasicBlock, GenKillSet<A::Idx>>>,
+}
+
+impl<A> Engine<'a, 'tcx, A>
+where
+ A: GenKillAnalysis<'tcx>,
+{
+ /// Creates a new `Engine` to solve a gen-kill dataflow problem.
+ pub fn new_gen_kill(
+ tcx: TyCtxt<'tcx>,
+ body: &'a mir::Body<'tcx>,
+ def_id: DefId,
+ analysis: A,
+ ) -> Self {
+ let bits_per_block = analysis.bits_per_block(body);
+ let mut trans_for_block =
+ IndexVec::from_elem(GenKillSet::identity(bits_per_block), body.basic_blocks());
+
+ // Compute cumulative block transfer functions.
+ //
+ // FIXME: we may want to skip this if the MIR is acyclic, since we will never access a
+ // block transfer function more than once.
+
+ for (block, block_data) in body.basic_blocks().iter_enumerated() {
+ let trans = &mut trans_for_block[block];
+
+ for (i, statement) in block_data.statements.iter().enumerate() {
+ let loc = Location { block, statement_index: i };
+ analysis.before_statement_effect(trans, statement, loc);
+ analysis.statement_effect(trans, statement, loc);
+ }
+
+ if let Some(terminator) = &block_data.terminator {
+ let loc = Location { block, statement_index: block_data.statements.len() };
+ analysis.before_terminator_effect(trans, terminator, loc);
+ analysis.terminator_effect(trans, terminator, loc);
+ }
+ }
+
+ Self::new(tcx, body, def_id, analysis, Some(trans_for_block))
+ }
+}
+
+impl<A> Engine<'a, 'tcx, A>
+where
+ A: Analysis<'tcx>,
+{
+ /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
+ /// function.
+ ///
+ /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
+ /// better performance.
+ pub fn new_generic(
+ tcx: TyCtxt<'tcx>,
+ body: &'a mir::Body<'tcx>,
+ def_id: DefId,
+ analysis: A,
+ ) -> Self {
+ Self::new(tcx, body, def_id, analysis, None)
+ }
+
+ fn new(
+ tcx: TyCtxt<'tcx>,
+ body: &'a mir::Body<'tcx>,
+ def_id: DefId,
+ analysis: A,
+ trans_for_block: Option<IndexVec<BasicBlock, GenKillSet<A::Idx>>>,
+ ) -> Self {
+ let bits_per_block = analysis.bits_per_block(body);
+
+ let bottom_value_set = if A::BOTTOM_VALUE == true {
+ BitSet::new_filled(bits_per_block)
+ } else {
+ BitSet::new_empty(bits_per_block)
+ };
+
+ let mut entry_sets = IndexVec::from_elem(bottom_value_set, body.basic_blocks());
+ analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]);
+
+ Engine {
+ analysis,
+ bits_per_block,
+ tcx,
+ body,
+ def_id,
+ dead_unwinds: None,
+ entry_sets,
+ trans_for_block,
+ }
+ }
+
+ /// Signals that we do not want dataflow state to propagate across unwind edges for these
+ /// `BasicBlock`s.
+ ///
+ /// You must take care that `dead_unwinds` does not contain a `BasicBlock` that *can* actually
+ /// unwind during execution. Otherwise, your dataflow results will not be correct.
+ pub fn dead_unwinds(mut self, dead_unwinds: &'a BitSet<BasicBlock>) -> Self {
+ self.dead_unwinds = Some(dead_unwinds);
+ self
+ }
+
+ /// Computes the fixpoint for this dataflow problem and returns it.
+ pub fn iterate_to_fixpoint(mut self) -> Results<'tcx, A> {
+ let mut temp_state = BitSet::new_empty(self.bits_per_block);
+
+ let mut dirty_queue: WorkQueue<BasicBlock> =
+ WorkQueue::with_none(self.body.basic_blocks().len());
+
+ for (bb, _) in traversal::reverse_postorder(self.body) {
+ dirty_queue.insert(bb);
+ }
+
+ // Add blocks that are not reachable from START_BLOCK to the work queue. These blocks will
+ // be processed after the ones added above.
+ for bb in self.body.basic_blocks().indices() {
+ dirty_queue.insert(bb);
+ }
+
+ while let Some(bb) = dirty_queue.pop() {
+ let bb_data = &self.body[bb];
+ let on_entry = &self.entry_sets[bb];
+
+ temp_state.overwrite(on_entry);
+ self.apply_whole_block_effect(&mut temp_state, bb, bb_data);
+
+ self.propagate_bits_into_graph_successors_of(
+ &mut temp_state,
+ (bb, bb_data),
+ &mut dirty_queue,
+ );
+ }
+
+ let Engine { tcx, body, def_id, trans_for_block, entry_sets, analysis, .. } = self;
+ let results = Results { analysis, entry_sets };
+
+ let res = write_graphviz_results(tcx, def_id, body, &results, trans_for_block);
+ if let Err(e) = res {
+ warn!("Failed to write graphviz dataflow results: {}", e);
+ }
+
+ results
+ }
+
+ /// Applies the cumulative effect of an entire block, excluding the call return effect if one
+ /// exists.
+ fn apply_whole_block_effect(
+ &self,
+ state: &mut BitSet<A::Idx>,
+ block: BasicBlock,
+ block_data: &mir::BasicBlockData<'tcx>,
+ ) {
+ // Use the cached block transfer function if available.
+ if let Some(trans_for_block) = &self.trans_for_block {
+ trans_for_block[block].apply(state);
+ return;
+ }
+
+ // Otherwise apply effects one-by-one.
+
+ for (statement_index, statement) in block_data.statements.iter().enumerate() {
+ let location = Location { block, statement_index };
+ self.analysis.apply_before_statement_effect(state, statement, location);
+ self.analysis.apply_statement_effect(state, statement, location);
+ }
+
+ let terminator = block_data.terminator();
+ let location = Location { block, statement_index: block_data.statements.len() };
+ self.analysis.apply_before_terminator_effect(state, terminator, location);
+ self.analysis.apply_terminator_effect(state, terminator, location);
+ }
+
+ fn propagate_bits_into_graph_successors_of(
+ &mut self,
+ in_out: &mut BitSet<A::Idx>,
+ (bb, bb_data): (BasicBlock, &'a mir::BasicBlockData<'tcx>),
+ dirty_list: &mut WorkQueue<BasicBlock>,
+ ) {
+ use mir::TerminatorKind::*;
+
+ match bb_data.terminator().kind {
+ Return | Resume | Abort | GeneratorDrop | Unreachable => {}
+
+ Goto { target }
+ | Assert { target, cleanup: None, .. }
+ | Yield { resume: target, drop: None, .. }
+ | Drop { target, location: _, unwind: None }
+ | DropAndReplace { target, value: _, location: _, unwind: None } => {
+ self.propagate_bits_into_entry_set_for(in_out, target, dirty_list)
+ }
+
+ Yield { resume: target, drop: Some(drop), .. } => {
+ self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
+ self.propagate_bits_into_entry_set_for(in_out, drop, dirty_list);
+ }
+
+ Assert { target, cleanup: Some(unwind), .. }
+ | Drop { target, location: _, unwind: Some(unwind) }
+ | DropAndReplace { target, value: _, location: _, unwind: Some(unwind) } => {
+ self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
+ if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
+ self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
+ }
+ }
+
+ SwitchInt { ref targets, .. } => {
+ for target in targets {
+ self.propagate_bits_into_entry_set_for(in_out, *target, dirty_list);
+ }
+ }
+
+ Call { cleanup, ref destination, ref func, ref args, .. } => {
+ if let Some(unwind) = cleanup {
+ if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
+ self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
+ }
+ }
+
+ if let Some((ref dest_place, dest_bb)) = *destination {
+ // N.B.: This must be done *last*, otherwise the unwind path will see the call
+ // return effect.
+ self.analysis.apply_call_return_effect(in_out, bb, func, args, dest_place);
+ self.propagate_bits_into_entry_set_for(in_out, dest_bb, dirty_list);
+ }
+ }
+
+ FalseEdges { real_target, imaginary_target } => {
+ self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
+ self.propagate_bits_into_entry_set_for(in_out, imaginary_target, dirty_list);
+ }
+
+ FalseUnwind { real_target, unwind } => {
+ self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
+ if let Some(unwind) = unwind {
+ if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
+ self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
+ }
+ }
+ }
+ }
+ }
+
+ fn propagate_bits_into_entry_set_for(
+ &mut self,
+ in_out: &BitSet<A::Idx>,
+ bb: BasicBlock,
+ dirty_queue: &mut WorkQueue<BasicBlock>,
+ ) {
+ let entry_set = &mut self.entry_sets[bb];
+ let set_changed = self.analysis.join(entry_set, &in_out);
+ if set_changed {
+ dirty_queue.insert(bb);
+ }
+ }
+}
+
+// Graphviz
+
+/// Writes a DOT file containing the results of a dataflow analysis if the user requested it via
+/// `rustc_mir` attributes.
+fn write_graphviz_results<A>(
+ tcx: TyCtxt<'tcx>,
+ def_id: DefId,
+ body: &mir::Body<'tcx>,
+ results: &Results<'tcx, A>,
+ block_transfer_functions: Option<IndexVec<BasicBlock, GenKillSet<A::Idx>>>,
+) -> std::io::Result<()>
+where
+ A: Analysis<'tcx>,
+{
+ let attrs = match RustcMirAttrs::parse(tcx, def_id) {
+ Ok(attrs) => attrs,
+
+ // Invalid `rustc_mir` attrs will be reported using `span_err`.
+ Err(()) => return Ok(()),
+ };
+
+ let path = match attrs.output_path(A::NAME) {
+ Some(path) => path,
+ None => return Ok(()),
+ };
+
+ let bits_per_block = results.analysis.bits_per_block(body);
+
+ let mut formatter: Box<dyn graphviz::StateFormatter<'tcx, _>> = match attrs.formatter {
+ Some(sym::two_phase) => Box::new(graphviz::TwoPhaseDiff::new(bits_per_block)),
+ Some(sym::gen_kill) => {
+ if let Some(trans_for_block) = block_transfer_functions {
+ Box::new(graphviz::BlockTransferFunc::new(body, trans_for_block))
+ } else {
+ Box::new(graphviz::SimpleDiff::new(bits_per_block))
+ }
+ }
+
+ // Default to the `SimpleDiff` output style.
+ _ => Box::new(graphviz::SimpleDiff::new(bits_per_block)),
+ };
+
+ debug!("printing dataflow results for {:?} to {}", def_id, path.display());
+ let mut buf = Vec::new();
+
+ let graphviz = graphviz::Formatter::new(body, def_id, results, &mut *formatter);
+ dot::render(&graphviz, &mut buf)?;
+ fs::write(&path, buf)?;
+ Ok(())
+}
+
+#[derive(Default)]
+struct RustcMirAttrs {
+ basename_and_suffix: Option<PathBuf>,
+ formatter: Option<Symbol>,
+}
+
+impl RustcMirAttrs {
+ fn parse(tcx: TyCtxt<'tcx>, def_id: DefId) -> Result<Self, ()> {
+ let attrs = tcx.get_attrs(def_id);
+
+ let mut result = Ok(());
+ let mut ret = RustcMirAttrs::default();
+
+ let rustc_mir_attrs = attrs
+ .into_iter()
+ .filter(|attr| attr.check_name(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.check_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.sess.span_err(attr.span(), "path must end in a filename");
+ Err(())
+ }
+ }
+ })
+ } else if attr.check_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.sess.span_err(attr.span(), "unknown formatter");
+ Err(())
+ }
+ })
+ } else {
+ Ok(())
+ };
+
+ result = result.and(attr_result);
+ }
+
+ result.map(|()| ret)
+ }
+
+ fn set_field<T>(
+ field: &mut Option<T>,
+ tcx: TyCtxt<'tcx>,
+ attr: &ast::NestedMetaItem,
+ mapper: impl FnOnce(Symbol) -> Result<T, ()>,
+ ) -> Result<(), ()> {
+ if field.is_some() {
+ tcx.sess
+ .span_err(attr.span(), &format!("duplicate values for `{}`", attr.name_or_empty()));
+
+ return Err(());
+ }
+
+ if let Some(s) = attr.value_str() {
+ *field = Some(mapper(s)?);
+ Ok(())
+ } else {
+ tcx.sess
+ .span_err(attr.span(), &format!("`{}` requires an argument", 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<PathBuf> {
+ 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/src/librustc_mir/dataflow/generic/graphviz.rs b/src/librustc_mir/dataflow/generic/graphviz.rs
index e843956..fdf86e7 100644
--- a/src/librustc_mir/dataflow/generic/graphviz.rs
+++ b/src/librustc_mir/dataflow/generic/graphviz.rs
@@ -1,13 +1,14 @@
+//! A helpful diagram for debugging dataflow problems.
+
use std::cell::RefCell;
-use std::io::{self, Write};
-use std::{ops, str};
+use std::{io, ops, str};
use rustc::mir::{self, BasicBlock, Body, Location};
use rustc_hir::def_id::DefId;
use rustc_index::bit_set::{BitSet, HybridBitSet};
-use rustc_index::vec::Idx;
+use rustc_index::vec::{Idx, IndexVec};
-use super::{Analysis, Results, ResultsRefCursor};
+use super::{Analysis, GenKillSet, Results, ResultsRefCursor};
use crate::util::graphviz_safe_def_name;
pub struct Formatter<'a, 'tcx, A>
@@ -25,11 +26,16 @@
where
A: Analysis<'tcx>,
{
- pub fn new(body: &'a Body<'tcx>, def_id: DefId, results: &'a Results<'tcx, A>) -> Self {
+ pub fn new(
+ body: &'a Body<'tcx>,
+ def_id: DefId,
+ results: &'a Results<'tcx, A>,
+ state_formatter: &'a mut dyn StateFormatter<'tcx, A>,
+ ) -> Self {
let block_formatter = BlockFormatter {
bg: Background::Light,
- prev_state: BitSet::new_empty(results.analysis.bits_per_block(body)),
results: ResultsRefCursor::new(body, results),
+ state_formatter,
};
Formatter { body, def_id, block_formatter: RefCell::new(block_formatter) }
@@ -117,15 +123,21 @@
where
A: Analysis<'tcx>,
{
- prev_state: BitSet<A::Idx>,
results: ResultsRefCursor<'a, 'a, 'tcx, A>,
bg: Background,
+ state_formatter: &'a mut dyn StateFormatter<'tcx, A>,
}
impl<A> BlockFormatter<'a, 'tcx, A>
where
A: Analysis<'tcx>,
{
+ const HEADER_COLOR: &'static str = "#a0a0a0";
+
+ fn num_state_columns(&self) -> usize {
+ std::cmp::max(1, self.state_formatter.column_names().len())
+ }
+
fn toggle_background(&mut self) -> Background {
let bg = self.bg;
self.bg = !bg;
@@ -164,196 +176,470 @@
r#"<table border="1" cellborder="1" cellspacing="0" cellpadding="3" sides="rb">"#,
)?;
- // A: Block info
- write!(
- w,
- r#"<tr>
- <td colspan="{num_headers}" sides="tl">bb{block_id}</td>
- </tr>"#,
- num_headers = 3,
- block_id = block.index(),
- )?;
-
- // B: Column headings
- write!(
- w,
- r#"<tr>
- <td colspan="2" {fmt}>MIR</td>
- <td {fmt}>STATE</td>
- </tr>"#,
- fmt = r##"bgcolor="#a0a0a0" sides="tl""##,
- )?;
+ // A + B: Block header
+ if self.state_formatter.column_names().is_empty() {
+ self.write_block_header_simple(w, block)?;
+ } else {
+ self.write_block_header_with_state_columns(w, block)?;
+ }
// C: Entry state
self.bg = Background::Light;
self.results.seek_to_block_start(block);
- self.write_row_with_curr_state(w, "", "(on entry)")?;
- self.prev_state.overwrite(self.results.get());
+ self.write_row_with_full_state(w, "", "(on_entry)")?;
// D: Statement transfer functions
for (i, statement) in body[block].statements.iter().enumerate() {
let location = Location { block, statement_index: i };
-
- let mir_col = format!("{:?}", statement);
- let i_col = i.to_string();
-
- self.results.seek_after(location);
- self.write_row_with_curr_diff(w, &i_col, &mir_col)?;
- self.prev_state.overwrite(self.results.get());
+ let statement_str = format!("{:?}", statement);
+ self.write_row_for_location(w, &i.to_string(), &statement_str, location)?;
}
// E: Terminator transfer function
let terminator = body[block].terminator();
- let location = body.terminator_loc(block);
+ let terminator_loc = body.terminator_loc(block);
+ let mut terminator_str = String::new();
+ terminator.kind.fmt_head(&mut terminator_str).unwrap();
- let mut mir_col = String::new();
- terminator.kind.fmt_head(&mut mir_col).unwrap();
-
- self.results.seek_after(location);
- self.write_row_with_curr_diff(w, "T", &mir_col)?;
- self.prev_state.overwrite(self.results.get());
+ self.write_row_for_location(w, "T", &terminator_str, terminator_loc)?;
// F: Exit state
+ self.results.seek_after(terminator_loc);
if let mir::TerminatorKind::Call { destination: Some(_), .. } = &terminator.kind {
- self.write_row_with_curr_state(w, "", "(on unwind)")?;
+ self.write_row_with_full_state(w, "", "(on unwind)")?;
- self.results.seek_after_assume_call_returns(location);
- self.write_row_with_curr_diff(w, "", "(on successful return)")?;
+ let num_state_columns = self.num_state_columns();
+ self.write_row(w, "", "(on successful return)", |this, w, fmt| {
+ write!(
+ w,
+ r#"<td colspan="{colspan}" {fmt} align="left">"#,
+ colspan = num_state_columns,
+ fmt = fmt,
+ )?;
+
+ let state_on_unwind = this.results.get().clone();
+ this.results.seek_after_assume_call_returns(terminator_loc);
+ write_diff(w, this.results.analysis(), &state_on_unwind, this.results.get())?;
+
+ write!(w, "</td>")
+ })?;
} else {
- self.write_row_with_curr_state(w, "", "(on exit)")?;
+ self.write_row_with_full_state(w, "", "(on exit)")?;
}
write!(w, "</table>")
}
- fn write_row_with_curr_state(
+ fn write_block_header_simple(
&mut self,
w: &mut impl io::Write,
- i: &str,
- mir: &str,
+ block: BasicBlock,
) -> io::Result<()> {
- let bg = self.toggle_background();
+ // +-------------------------------------------------+
+ // A | bb4 |
+ // +-----------------------------------+-------------+
+ // B | MIR | STATE |
+ // +-+---------------------------------+-------------+
+ // | | ... | |
- let mut out = Vec::new();
- write!(&mut out, "{{")?;
- pretty_print_state_elems(&mut out, self.results.analysis(), self.results.get().iter())?;
- write!(&mut out, "}}")?;
-
+ // A
write!(
w,
- r#"<tr>
- <td {fmt} align="right">{i}</td>
- <td {fmt} align="left">{mir}</td>
- <td {fmt} align="left">{state}</td>
- </tr>"#,
- fmt = &["sides=\"tl\"", bg.attr()].join(" "),
- i = i,
- mir = dot::escape_html(mir),
- state = dot::escape_html(str::from_utf8(&out).unwrap()),
+ concat!("<tr>", r#"<td colspan="3" sides="tl">bb{block_id}</td>"#, "</tr>",),
+ block_id = block.index(),
+ )?;
+
+ // B
+ write!(
+ w,
+ concat!(
+ "<tr>",
+ r#"<td colspan="2" {fmt}>MIR</td>"#,
+ r#"<td {fmt}>STATE</td>"#,
+ "</tr>",
+ ),
+ fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR),
)
}
- fn write_row_with_curr_diff(
+ fn write_block_header_with_state_columns(
+ &mut self,
+ w: &mut impl io::Write,
+ block: BasicBlock,
+ ) -> io::Result<()> {
+ // +------------------------------------+-------------+
+ // A | bb4 | STATE |
+ // +------------------------------------+------+------+
+ // B | MIR | GEN | KILL |
+ // +-+----------------------------------+------+------+
+ // | | ... | | |
+
+ let state_column_names = self.state_formatter.column_names();
+
+ // A
+ write!(
+ w,
+ concat!(
+ "<tr>",
+ r#"<td {fmt} colspan="2">bb{block_id}</td>"#,
+ r#"<td {fmt} colspan="{num_state_cols}">STATE</td>"#,
+ "</tr>",
+ ),
+ fmt = "sides=\"tl\"",
+ num_state_cols = state_column_names.len(),
+ block_id = block.index(),
+ )?;
+
+ // B
+ let fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR);
+ write!(w, concat!("<tr>", r#"<td colspan="2" {fmt}>MIR</td>"#,), fmt = fmt,)?;
+
+ for name in state_column_names {
+ write!(w, "<td {fmt}>{name}</td>", fmt = fmt, name = name)?;
+ }
+
+ write!(w, "</tr>")
+ }
+
+ /// Write a row with the given index and MIR, using the function argument to fill in the
+ /// "STATE" column(s).
+ fn write_row<W: io::Write>(
+ &mut self,
+ w: &mut W,
+ i: &str,
+ mir: &str,
+ f: impl FnOnce(&mut Self, &mut W, &str) -> io::Result<()>,
+ ) -> io::Result<()> {
+ let bg = self.toggle_background();
+ let fmt = format!("sides=\"tl\" {}", bg.attr());
+
+ write!(
+ w,
+ concat!(
+ "<tr>",
+ r#"<td {fmt} align="right">{i}</td>"#,
+ r#"<td {fmt} align="left">{mir}</td>"#,
+ ),
+ i = i,
+ fmt = fmt,
+ mir = dot::escape_html(mir),
+ )?;
+
+ f(self, w, &fmt)?;
+ write!(w, "</tr>")
+ }
+
+ fn write_row_with_full_state(
&mut self,
w: &mut impl io::Write,
i: &str,
mir: &str,
) -> io::Result<()> {
- let bg = self.toggle_background();
- let analysis = self.results.analysis();
+ self.write_row(w, i, mir, |this, w, fmt| {
+ let state = this.results.get();
+ let analysis = this.results.analysis();
- let diff = BitSetDiff::compute(&self.prev_state, self.results.get());
-
- let mut set = Vec::new();
- pretty_print_state_elems(&mut set, analysis, diff.set.iter())?;
-
- let mut clear = Vec::new();
- pretty_print_state_elems(&mut clear, analysis, diff.clear.iter())?;
-
- write!(
- w,
- r#"<tr>
- <td {fmt} align="right">{i}</td>
- <td {fmt} align="left">{mir}</td>
- <td {fmt} align="left">"#,
- i = i,
- fmt = &["sides=\"tl\"", bg.attr()].join(" "),
- mir = dot::escape_html(mir),
- )?;
-
- if !set.is_empty() {
write!(
w,
- r#"<font color="darkgreen">+{}</font>"#,
- dot::escape_html(str::from_utf8(&set).unwrap()),
+ r#"<td colspan="{colspan}" {fmt} align="left">{{"#,
+ colspan = this.num_state_columns(),
+ fmt = fmt,
)?;
- }
+ pretty_print_state_elems(w, analysis, state.iter(), ",", LIMIT_40_ALIGN_1)?;
+ write!(w, "}}</td>")
+ })
+ }
- if !set.is_empty() && !clear.is_empty() {
- write!(w, " ")?;
- }
-
- if !clear.is_empty() {
- write!(
- w,
- r#"<font color="red">-{}</font>"#,
- dot::escape_html(str::from_utf8(&clear).unwrap()),
- )?;
- }
-
- write!(w, "</td></tr>")
+ fn write_row_for_location(
+ &mut self,
+ w: &mut impl io::Write,
+ i: &str,
+ mir: &str,
+ location: Location,
+ ) -> io::Result<()> {
+ self.write_row(w, i, mir, |this, w, fmt| {
+ this.state_formatter.write_state_for_location(w, fmt, &mut this.results, location)
+ })
}
}
-/// The operations required to transform one `BitSet` into another.
-struct BitSetDiff<T: Idx> {
- set: HybridBitSet<T>,
- clear: HybridBitSet<T>,
+/// Controls what gets printed under the `STATE` header.
+pub trait StateFormatter<'tcx, A>
+where
+ A: Analysis<'tcx>,
+{
+ /// The columns that will get printed under `STATE`.
+ fn column_names(&self) -> &[&str];
+
+ fn write_state_for_location(
+ &mut self,
+ w: &mut dyn io::Write,
+ fmt: &str,
+ results: &mut ResultsRefCursor<'_, '_, 'tcx, A>,
+ location: Location,
+ ) -> io::Result<()>;
}
-impl<T: Idx> BitSetDiff<T> {
- fn compute(from: &BitSet<T>, to: &BitSet<T>) -> Self {
- assert_eq!(from.domain_size(), to.domain_size());
- let len = from.domain_size();
+/// Prints a single column containing the state vector immediately *after* each statement.
+pub struct SimpleDiff<T: Idx> {
+ prev_state: BitSet<T>,
+ prev_loc: Location,
+}
- let mut set = HybridBitSet::new_empty(len);
- let mut clear = HybridBitSet::new_empty(len);
-
- // FIXME: This could be made faster if `BitSet::xor` were implemented.
- for i in (0..len).map(|i| T::new(i)) {
- match (from.contains(i), to.contains(i)) {
- (false, true) => set.insert(i),
- (true, false) => clear.insert(i),
- _ => continue,
- };
- }
-
- BitSetDiff { set, clear }
+impl<T: Idx> SimpleDiff<T> {
+ #![allow(unused)]
+ pub fn new(bits_per_block: usize) -> Self {
+ SimpleDiff { prev_state: BitSet::new_empty(bits_per_block), prev_loc: Location::START }
}
}
-/// Formats each `elem` using the pretty printer provided by `analysis` into a comma-separated
-/// list.
+impl<A> StateFormatter<'tcx, A> for SimpleDiff<A::Idx>
+where
+ A: Analysis<'tcx>,
+{
+ fn column_names(&self) -> &[&str] {
+ &[]
+ }
+
+ fn write_state_for_location(
+ &mut self,
+ mut w: &mut dyn io::Write,
+ fmt: &str,
+ results: &mut ResultsRefCursor<'_, '_, 'tcx, A>,
+ location: Location,
+ ) -> io::Result<()> {
+ if location.statement_index == 0 {
+ results.seek_to_block_start(location.block);
+ self.prev_state.overwrite(results.get());
+ } else {
+ // Ensure that we are visiting statements in order, so `prev_state` is correct.
+ assert_eq!(self.prev_loc.successor_within_block(), location);
+ }
+
+ self.prev_loc = location;
+ write!(w, r#"<td {fmt} align="left">"#, fmt = fmt)?;
+ results.seek_before(location);
+ let curr_state = results.get();
+ write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?;
+ self.prev_state.overwrite(curr_state);
+ write!(w, "</td>")
+ }
+}
+
+/// Prints two state columns, one containing only the "before" effect of each statement and one
+/// containing the full effect.
+pub struct TwoPhaseDiff<T: Idx> {
+ prev_state: BitSet<T>,
+ prev_loc: Location,
+}
+
+impl<T: Idx> TwoPhaseDiff<T> {
+ #![allow(unused)]
+ pub fn new(bits_per_block: usize) -> Self {
+ TwoPhaseDiff { prev_state: BitSet::new_empty(bits_per_block), prev_loc: Location::START }
+ }
+}
+
+impl<A> StateFormatter<'tcx, A> for TwoPhaseDiff<A::Idx>
+where
+ A: Analysis<'tcx>,
+{
+ fn column_names(&self) -> &[&str] {
+ &["ENTRY", " EXIT"]
+ }
+
+ fn write_state_for_location(
+ &mut self,
+ mut w: &mut dyn io::Write,
+ fmt: &str,
+ results: &mut ResultsRefCursor<'_, '_, 'tcx, A>,
+ location: Location,
+ ) -> io::Result<()> {
+ if location.statement_index == 0 {
+ results.seek_to_block_start(location.block);
+ self.prev_state.overwrite(results.get());
+ } else {
+ // Ensure that we are visiting statements in order, so `prev_state` is correct.
+ assert_eq!(self.prev_loc.successor_within_block(), location);
+ }
+
+ self.prev_loc = location;
+
+ // Entry
+
+ write!(w, r#"<td {fmt} align="left">"#, fmt = fmt)?;
+ results.seek_before(location);
+ let curr_state = results.get();
+ write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?;
+ self.prev_state.overwrite(curr_state);
+ write!(w, "</td>")?;
+
+ // Exit
+
+ write!(w, r#"<td {fmt} align="left">"#, fmt = fmt)?;
+ results.seek_after(location);
+ let curr_state = results.get();
+ write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?;
+ self.prev_state.overwrite(curr_state);
+ write!(w, "</td>")
+ }
+}
+
+/// Prints the gen/kill set for the entire block.
+pub struct BlockTransferFunc<'a, 'tcx, T: Idx> {
+ body: &'a mir::Body<'tcx>,
+ trans_for_block: IndexVec<BasicBlock, GenKillSet<T>>,
+}
+
+impl<T: Idx> BlockTransferFunc<'mir, 'tcx, T> {
+ #![allow(unused)]
+ pub fn new(
+ body: &'mir mir::Body<'tcx>,
+ trans_for_block: IndexVec<BasicBlock, GenKillSet<T>>,
+ ) -> Self {
+ BlockTransferFunc { body, trans_for_block }
+ }
+}
+
+impl<A> StateFormatter<'tcx, A> for BlockTransferFunc<'mir, 'tcx, A::Idx>
+where
+ A: Analysis<'tcx>,
+{
+ fn column_names(&self) -> &[&str] {
+ &["GEN", "KILL"]
+ }
+
+ fn write_state_for_location(
+ &mut self,
+ mut w: &mut dyn io::Write,
+ fmt: &str,
+ results: &mut ResultsRefCursor<'_, '_, 'tcx, A>,
+ location: Location,
+ ) -> io::Result<()> {
+ // Only print a single row.
+ if location.statement_index != 0 {
+ return Ok(());
+ }
+
+ let block_trans = &self.trans_for_block[location.block];
+ let rowspan = self.body.basic_blocks()[location.block].statements.len();
+
+ for set in &[&block_trans.gen, &block_trans.kill] {
+ write!(
+ w,
+ r#"<td {fmt} rowspan="{rowspan}" align="center">"#,
+ fmt = fmt,
+ rowspan = rowspan
+ )?;
+
+ pretty_print_state_elems(&mut w, results.analysis(), set.iter(), "\n", None)?;
+ write!(w, "</td>")?;
+ }
+
+ Ok(())
+ }
+}
+
+/// Writes two lines, one containing the added bits and one the removed bits.
+fn write_diff<A: Analysis<'tcx>>(
+ w: &mut impl io::Write,
+ analysis: &A,
+ from: &BitSet<A::Idx>,
+ to: &BitSet<A::Idx>,
+) -> io::Result<()> {
+ assert_eq!(from.domain_size(), to.domain_size());
+ let len = from.domain_size();
+
+ let mut set = HybridBitSet::new_empty(len);
+ let mut clear = HybridBitSet::new_empty(len);
+
+ // FIXME: Implement a lazy iterator over the symmetric difference of two bitsets.
+ for i in (0..len).map(|i| A::Idx::new(i)) {
+ match (from.contains(i), to.contains(i)) {
+ (false, true) => set.insert(i),
+ (true, false) => clear.insert(i),
+ _ => continue,
+ };
+ }
+
+ if !set.is_empty() {
+ write!(w, r#"<font color="darkgreen">+"#)?;
+ pretty_print_state_elems(w, analysis, set.iter(), ",", LIMIT_40_ALIGN_1)?;
+ write!(w, r#"</font>"#)?;
+ }
+
+ if !set.is_empty() && !clear.is_empty() {
+ write!(w, "<br/>")?;
+ }
+
+ if !clear.is_empty() {
+ write!(w, r#"<font color="red">-"#)?;
+ pretty_print_state_elems(w, analysis, clear.iter(), ",", LIMIT_40_ALIGN_1)?;
+ write!(w, r#"</font>"#)?;
+ }
+
+ Ok(())
+}
+
+/// Line break policy that breaks at 40 characters and starts the next line with a single space.
+const LIMIT_40_ALIGN_1: Option<LineBreak> = Some(LineBreak { sequence: "<br/> ", limit: 40 });
+
+struct LineBreak {
+ sequence: &'static str,
+ limit: usize,
+}
+
+/// Formats each `elem` using the pretty printer provided by `analysis` into a list with the given
+/// separator (`sep`).
+///
+/// Optionally, it will break lines using the given character sequence (usually `<br/>`) and
+/// character limit.
fn pretty_print_state_elems<A>(
w: &mut impl io::Write,
analysis: &A,
elems: impl Iterator<Item = A::Idx>,
-) -> io::Result<()>
+ sep: &str,
+ line_break: Option<LineBreak>,
+) -> io::Result<bool>
where
A: Analysis<'tcx>,
{
+ let sep_width = sep.chars().count();
+
+ let mut buf = Vec::new();
+
let mut first = true;
+ let mut curr_line_width = 0;
+ let mut line_break_inserted = false;
+
for idx in elems {
if first {
first = false;
} else {
- write!(w, ",")?;
+ write!(w, "{}", sep)?;
+ curr_line_width += sep_width;
}
- analysis.pretty_print_idx(w, idx)?;
+ buf.clear();
+ analysis.pretty_print_idx(&mut buf, idx)?;
+ let idx_str =
+ str::from_utf8(&buf).expect("Output of `pretty_print_idx` must be valid UTF-8");
+ let escaped = dot::escape_html(idx_str);
+ let escaped_width = escaped.chars().count();
+
+ if let Some(line_break) = &line_break {
+ if curr_line_width + sep_width + escaped_width > line_break.limit {
+ write!(w, "{}", line_break.sequence)?;
+ line_break_inserted = true;
+ curr_line_width = 0;
+ }
+ }
+
+ write!(w, "{}", escaped)?;
+ curr_line_width += escaped_width;
}
- Ok(())
+ Ok(line_break_inserted)
}
/// The background color used for zebra-striping the table.
diff --git a/src/librustc_mir/dataflow/generic/mod.rs b/src/librustc_mir/dataflow/generic/mod.rs
new file mode 100644
index 0000000..c9b4f87
--- /dev/null
+++ b/src/librustc_mir/dataflow/generic/mod.rs
@@ -0,0 +1,358 @@
+//! A framework that can express both [gen-kill] and generic dataflow problems.
+//!
+//! There is another interface for dataflow in the compiler in `librustc_mir/dataflow/mod.rs`. The
+//! interface in this module will eventually [replace that one][design-meeting].
+//!
+//! To actually use this framework, you must implement either the `Analysis` or the `GenKillAnalysis`
+//! trait. If your transfer function can be expressed with only gen/kill operations, prefer
+//! `GenKillAnalysis` since it will run faster while iterating to fixpoint. Create an `Engine` using
+//! the appropriate constructor and call `iterate_to_fixpoint`. You can use a `ResultsCursor` to
+//! inspect the fixpoint solution to your dataflow problem.
+//!
+//! ```ignore(cross-crate-imports)
+//! fn do_my_analysis(tcx: TyCtxt<'tcx>, body: &mir::Body<'tcx>, did: DefId) {
+//! let analysis = MyAnalysis::new();
+//!
+//! // If `MyAnalysis` implements `GenKillAnalysis`.
+//! let results = Engine::new_gen_kill(tcx, body, did, analysis).iterate_to_fixpoint();
+//!
+//! // If `MyAnalysis` implements `Analysis`.
+//! // let results = Engine::new_generic(tcx, body, did, analysis).iterate_to_fixpoint();
+//!
+//! let mut cursor = ResultsCursor::new(body, results);
+//!
+//! for (_, statement_index) in body.block_data[START_BLOCK].statements.iter_enumerated() {
+//! cursor.seek_after(Location { block: START_BLOCK, statement_index });
+//! let state = cursor.get();
+//! println!("{:?}", state);
+//! }
+//! }
+//! ```
+//!
+//! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems
+//! [design-meeting]https://github.com/rust-lang/compiler-team/issues/202
+
+use std::io;
+
+use rustc::mir::{self, BasicBlock, Location};
+use rustc_index::bit_set::{BitSet, HybridBitSet};
+use rustc_index::vec::{Idx, IndexVec};
+
+use crate::dataflow::BottomValue;
+
+mod cursor;
+mod engine;
+mod graphviz;
+
+pub use self::cursor::{ResultsCursor, ResultsRefCursor};
+pub use self::engine::Engine;
+
+/// A dataflow analysis that has converged to fixpoint.
+pub struct Results<'tcx, A>
+where
+ A: Analysis<'tcx>,
+{
+ pub analysis: A,
+ entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
+}
+
+impl<A> Results<'tcx, A>
+where
+ A: Analysis<'tcx>,
+{
+ /// Creates a `ResultsCursor` that can inspect these `Results`.
+ pub fn into_results_cursor(self, body: &'mir mir::Body<'tcx>) -> ResultsCursor<'mir, 'tcx, A> {
+ ResultsCursor::new(body, self)
+ }
+
+ /// Gets the entry set for the given block.
+ pub fn entry_set_for_block(&self, block: BasicBlock) -> &BitSet<A::Idx> {
+ &self.entry_sets[block]
+ }
+}
+
+/// Define the domain of a dataflow problem.
+///
+/// This trait specifies the lattice on which this analysis operates. For now, this must be a
+/// powerset of values of type `Idx`. The elements of this lattice are represented with a `BitSet`
+/// and referred to as the state vector.
+///
+/// This trait also defines the initial value for the dataflow state upon entry to the
+/// `START_BLOCK`, as well as some names used to refer to this analysis when debugging.
+pub trait AnalysisDomain<'tcx>: BottomValue {
+ /// The type of the elements in the state vector.
+ type Idx: Idx;
+
+ /// A descriptive name for this analysis. Used only for debugging.
+ ///
+ /// This name should be brief and contain no spaces, periods or other characters that are not
+ /// suitable as part of a filename.
+ const NAME: &'static str;
+
+ /// The size of the state vector.
+ fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize;
+
+ /// Mutates the entry set of the `START_BLOCK` to contain the initial state for dataflow
+ /// analysis.
+ fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>);
+
+ /// Prints an element in the state vector for debugging.
+ fn pretty_print_idx(&self, w: &mut impl io::Write, idx: Self::Idx) -> io::Result<()> {
+ write!(w, "{:?}", idx)
+ }
+}
+
+/// A dataflow problem with an arbitrarily complex transfer function.
+pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
+ /// Updates the current dataflow state with the effect of evaluating a statement.
+ fn apply_statement_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ statement: &mir::Statement<'tcx>,
+ location: Location,
+ );
+
+ /// Updates the current dataflow state with an effect that occurs immediately *before* the
+ /// given statement.
+ ///
+ /// This method is useful if the consumer of the results of this analysis needs only to observe
+ /// *part* of the effect of a statement (e.g. for two-phase borrows). As a general rule,
+ /// analyses should not implement this without implementing `apply_statement_effect`.
+ fn apply_before_statement_effect(
+ &self,
+ _state: &mut BitSet<Self::Idx>,
+ _statement: &mir::Statement<'tcx>,
+ _location: Location,
+ ) {
+ }
+
+ /// Updates the current dataflow state with the effect of evaluating a terminator.
+ ///
+ /// The effect of a successful return from a `Call` terminator should **not** be accounted for
+ /// in this function. That should go in `apply_call_return_effect`. For example, in the
+ /// `InitializedPlaces` analyses, the return place for a function call is not marked as
+ /// initialized here.
+ fn apply_terminator_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ terminator: &mir::Terminator<'tcx>,
+ location: Location,
+ );
+
+ /// Updates the current dataflow state with an effect that occurs immediately *before* the
+ /// given terminator.
+ ///
+ /// This method is useful if the consumer of the results of this analysis needs only to observe
+ /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule,
+ /// analyses should not implement this without implementing `apply_terminator_effect`.
+ fn apply_before_terminator_effect(
+ &self,
+ _state: &mut BitSet<Self::Idx>,
+ _terminator: &mir::Terminator<'tcx>,
+ _location: Location,
+ ) {
+ }
+
+ /// Updates the current dataflow state with the effect of a successful return from a `Call`
+ /// terminator.
+ ///
+ /// This is separate from `apply_terminator_effect` to properly track state across unwind
+ /// edges.
+ fn apply_call_return_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ block: BasicBlock,
+ func: &mir::Operand<'tcx>,
+ args: &[mir::Operand<'tcx>],
+ return_place: &mir::Place<'tcx>,
+ );
+}
+
+/// A gen/kill dataflow problem.
+///
+/// Each method in this trait has a corresponding one in `Analysis`. However, these methods only
+/// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer
+/// functions for each statement in this way, the transfer function for an entire basic block can
+/// be computed efficiently.
+///
+/// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`.
+pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
+ /// See `Analysis::apply_statement_effect`.
+ fn statement_effect(
+ &self,
+ trans: &mut impl GenKill<Self::Idx>,
+ statement: &mir::Statement<'tcx>,
+ location: Location,
+ );
+
+ /// See `Analysis::apply_before_statement_effect`.
+ fn before_statement_effect(
+ &self,
+ _trans: &mut impl GenKill<Self::Idx>,
+ _statement: &mir::Statement<'tcx>,
+ _location: Location,
+ ) {
+ }
+
+ /// See `Analysis::apply_terminator_effect`.
+ fn terminator_effect(
+ &self,
+ trans: &mut impl GenKill<Self::Idx>,
+ terminator: &mir::Terminator<'tcx>,
+ location: Location,
+ );
+
+ /// See `Analysis::apply_before_terminator_effect`.
+ fn before_terminator_effect(
+ &self,
+ _trans: &mut impl GenKill<Self::Idx>,
+ _terminator: &mir::Terminator<'tcx>,
+ _location: Location,
+ ) {
+ }
+
+ /// See `Analysis::apply_call_return_effect`.
+ fn call_return_effect(
+ &self,
+ trans: &mut impl GenKill<Self::Idx>,
+ block: BasicBlock,
+ func: &mir::Operand<'tcx>,
+ args: &[mir::Operand<'tcx>],
+ return_place: &mir::Place<'tcx>,
+ );
+}
+
+impl<A> Analysis<'tcx> for A
+where
+ A: GenKillAnalysis<'tcx>,
+{
+ fn apply_statement_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ statement: &mir::Statement<'tcx>,
+ location: Location,
+ ) {
+ self.statement_effect(state, statement, location);
+ }
+
+ fn apply_before_statement_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ statement: &mir::Statement<'tcx>,
+ location: Location,
+ ) {
+ self.before_statement_effect(state, statement, location);
+ }
+
+ fn apply_terminator_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ terminator: &mir::Terminator<'tcx>,
+ location: Location,
+ ) {
+ self.terminator_effect(state, terminator, location);
+ }
+
+ fn apply_before_terminator_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ terminator: &mir::Terminator<'tcx>,
+ location: Location,
+ ) {
+ self.before_terminator_effect(state, terminator, location);
+ }
+
+ fn apply_call_return_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ block: BasicBlock,
+ func: &mir::Operand<'tcx>,
+ args: &[mir::Operand<'tcx>],
+ return_place: &mir::Place<'tcx>,
+ ) {
+ self.call_return_effect(state, block, func, args, return_place);
+ }
+}
+
+/// The legal operations for a transfer function in a gen/kill problem.
+///
+/// This abstraction exists because there are two different contexts in which we call the methods in
+/// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently
+/// applied multiple times, such as when computing the cumulative transfer function for each block.
+/// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes,
+/// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the
+/// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to
+/// building up a `GenKillSet` and then throwing it away.
+pub trait GenKill<T> {
+ /// Inserts `elem` into the state vector.
+ fn gen(&mut self, elem: T);
+
+ /// Removes `elem` from the state vector.
+ fn kill(&mut self, elem: T);
+
+ /// Calls `gen` for each element in `elems`.
+ fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) {
+ for elem in elems {
+ self.gen(elem);
+ }
+ }
+
+ /// Calls `kill` for each element in `elems`.
+ fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) {
+ for elem in elems {
+ self.kill(elem);
+ }
+ }
+}
+
+/// Stores a transfer function for a gen/kill problem.
+///
+/// Calling `gen`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be
+/// applied multiple times efficiently. When there are multiple calls to `gen` and/or `kill` for
+/// the same element, the most recent one takes precedence.
+#[derive(Clone)]
+pub struct GenKillSet<T: Idx> {
+ gen: HybridBitSet<T>,
+ kill: HybridBitSet<T>,
+}
+
+impl<T: Idx> GenKillSet<T> {
+ /// Creates a new transfer function that will leave the dataflow state unchanged.
+ pub fn identity(universe: usize) -> Self {
+ GenKillSet {
+ gen: HybridBitSet::new_empty(universe),
+ kill: HybridBitSet::new_empty(universe),
+ }
+ }
+
+ /// Applies this transfer function to the given state vector.
+ pub fn apply(&self, state: &mut BitSet<T>) {
+ state.union(&self.gen);
+ state.subtract(&self.kill);
+ }
+}
+
+impl<T: Idx> GenKill<T> for GenKillSet<T> {
+ fn gen(&mut self, elem: T) {
+ self.gen.insert(elem);
+ self.kill.remove(elem);
+ }
+
+ fn kill(&mut self, elem: T) {
+ self.kill.insert(elem);
+ self.gen.remove(elem);
+ }
+}
+
+impl<T: Idx> GenKill<T> for BitSet<T> {
+ fn gen(&mut self, elem: T) {
+ self.insert(elem);
+ }
+
+ fn kill(&mut self, elem: T) {
+ self.remove(elem);
+ }
+}
+
+#[cfg(test)]
+mod tests;
diff --git a/src/librustc_mir/dataflow/generic/tests.rs b/src/librustc_mir/dataflow/generic/tests.rs
new file mode 100644
index 0000000..50d4bdb
--- /dev/null
+++ b/src/librustc_mir/dataflow/generic/tests.rs
@@ -0,0 +1,332 @@
+//! A test for the logic that updates the state in a `ResultsCursor` during seek.
+
+use rustc::mir::{self, BasicBlock, Location};
+use rustc::ty;
+use rustc_index::bit_set::BitSet;
+use rustc_index::vec::IndexVec;
+use rustc_span::DUMMY_SP;
+
+use super::*;
+use crate::dataflow::BottomValue;
+
+/// Returns `true` if the given location points to a `Call` terminator that can return
+/// successfully.
+fn is_call_terminator_non_diverging(body: &mir::Body<'_>, loc: Location) -> bool {
+ loc == body.terminator_loc(loc.block)
+ && matches!(
+ body[loc.block].terminator().kind,
+ mir::TerminatorKind::Call { destination: Some(_), .. }
+ )
+}
+
+/// Creates a `mir::Body` with a few disconnected basic blocks.
+///
+/// This is the `Body` that will be used by the `MockAnalysis` below. The shape of its CFG is not
+/// important.
+fn mock_body() -> mir::Body<'static> {
+ let source_info = mir::SourceInfo { scope: mir::OUTERMOST_SOURCE_SCOPE, span: DUMMY_SP };
+
+ let mut blocks = IndexVec::new();
+ let mut block = |n, kind| {
+ let nop = mir::Statement { source_info, kind: mir::StatementKind::Nop };
+
+ blocks.push(mir::BasicBlockData {
+ statements: std::iter::repeat(&nop).cloned().take(n).collect(),
+ terminator: Some(mir::Terminator { source_info, kind }),
+ is_cleanup: false,
+ })
+ };
+
+ let dummy_place = mir::Place { local: mir::RETURN_PLACE, projection: ty::List::empty() };
+
+ block(4, mir::TerminatorKind::Return);
+ block(1, mir::TerminatorKind::Return);
+ block(
+ 2,
+ mir::TerminatorKind::Call {
+ func: mir::Operand::Copy(dummy_place.clone()),
+ args: vec![],
+ destination: Some((dummy_place.clone(), mir::START_BLOCK)),
+ cleanup: None,
+ from_hir_call: false,
+ },
+ );
+ block(3, mir::TerminatorKind::Return);
+ block(0, mir::TerminatorKind::Return);
+ block(
+ 4,
+ mir::TerminatorKind::Call {
+ func: mir::Operand::Copy(dummy_place.clone()),
+ args: vec![],
+ destination: Some((dummy_place.clone(), mir::START_BLOCK)),
+ cleanup: None,
+ from_hir_call: false,
+ },
+ );
+
+ mir::Body::new_cfg_only(blocks)
+}
+
+/// A dataflow analysis whose state is unique at every possible `SeekTarget`.
+///
+/// Uniqueness is achieved by having a *locally* unique effect before and after each statement and
+/// terminator (see `effect_at_target`) while ensuring that the entry set for each block is
+/// *globally* unique (see `mock_entry_set`).
+///
+/// For example, a `BasicBlock` with ID `2` and a `Call` terminator has the following state at each
+/// location ("+x" indicates that "x" is added to the state).
+///
+/// | Location | Before | After |
+/// |------------------------|-------------------|--------|
+/// | (on_entry) | {102} ||
+/// | Statement 0 | +0 | +1 |
+/// | statement 1 | +2 | +3 |
+/// | `Call` terminator | +4 | +5 |
+/// | (on unwind) | {102,0,1,2,3,4,5} ||
+/// | (on successful return) | +6 ||
+///
+/// The `102` in the block's entry set is derived from the basic block index and ensures that the
+/// expected state is unique across all basic blocks. Remember, it is generated by
+/// `mock_entry_sets`, not from actually running `MockAnalysis` to fixpoint.
+struct MockAnalysis<'tcx> {
+ body: &'tcx mir::Body<'tcx>,
+}
+
+impl MockAnalysis<'tcx> {
+ const BASIC_BLOCK_OFFSET: usize = 100;
+
+ /// The entry set for each `BasicBlock` is the ID of that block offset by a fixed amount to
+ /// avoid colliding with the statement/terminator effects.
+ fn mock_entry_set(&self, bb: BasicBlock) -> BitSet<usize> {
+ let mut ret = BitSet::new_empty(self.bits_per_block(self.body));
+ ret.insert(Self::BASIC_BLOCK_OFFSET + bb.index());
+ ret
+ }
+
+ fn mock_entry_sets(&self) -> IndexVec<BasicBlock, BitSet<usize>> {
+ let empty = BitSet::new_empty(self.bits_per_block(self.body));
+ let mut ret = IndexVec::from_elem(empty, &self.body.basic_blocks());
+
+ for (bb, _) in self.body.basic_blocks().iter_enumerated() {
+ ret[bb] = self.mock_entry_set(bb);
+ }
+
+ ret
+ }
+
+ /// Returns the index that should be added to the dataflow state at the given target.
+ ///
+ /// This index is only unique within a given basic block. `SeekAfter` and
+ /// `SeekAfterAssumeCallReturns` have the same effect unless `target` is a `Call` terminator.
+ fn effect_at_target(&self, target: SeekTarget) -> Option<usize> {
+ use SeekTarget::*;
+
+ let idx = match target {
+ BlockStart(_) => return None,
+
+ AfterAssumeCallReturns(loc) if is_call_terminator_non_diverging(self.body, loc) => {
+ loc.statement_index * 2 + 2
+ }
+
+ Before(loc) => loc.statement_index * 2,
+ After(loc) | AfterAssumeCallReturns(loc) => loc.statement_index * 2 + 1,
+ };
+
+ assert!(idx < Self::BASIC_BLOCK_OFFSET, "Too many statements in basic block");
+ Some(idx)
+ }
+
+ /// Returns the expected state at the given `SeekTarget`.
+ ///
+ /// This is the union of index of the target basic block, the index assigned to the
+ /// target statement or terminator, and the indices of all preceding statements in the target
+ /// basic block.
+ ///
+ /// For example, the expected state when calling
+ /// `seek_before(Location { block: 2, statement_index: 2 })` would be `[102, 0, 1, 2, 3, 4]`.
+ fn expected_state_at_target(&self, target: SeekTarget) -> BitSet<usize> {
+ let mut ret = BitSet::new_empty(self.bits_per_block(self.body));
+ ret.insert(Self::BASIC_BLOCK_OFFSET + target.block().index());
+
+ if let Some(target_effect) = self.effect_at_target(target) {
+ for i in 0..=target_effect {
+ ret.insert(i);
+ }
+ }
+
+ ret
+ }
+}
+
+impl BottomValue for MockAnalysis<'tcx> {
+ const BOTTOM_VALUE: bool = false;
+}
+
+impl AnalysisDomain<'tcx> for MockAnalysis<'tcx> {
+ type Idx = usize;
+
+ const NAME: &'static str = "mock";
+
+ fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize {
+ Self::BASIC_BLOCK_OFFSET + body.basic_blocks().len()
+ }
+
+ fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut BitSet<Self::Idx>) {
+ unimplemented!("This is never called since `MockAnalysis` is never iterated to fixpoint");
+ }
+}
+
+impl Analysis<'tcx> for MockAnalysis<'tcx> {
+ fn apply_statement_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ _statement: &mir::Statement<'tcx>,
+ location: Location,
+ ) {
+ let idx = self.effect_at_target(SeekTarget::After(location)).unwrap();
+ assert!(state.insert(idx));
+ }
+
+ fn apply_before_statement_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ _statement: &mir::Statement<'tcx>,
+ location: Location,
+ ) {
+ let idx = self.effect_at_target(SeekTarget::Before(location)).unwrap();
+ assert!(state.insert(idx));
+ }
+
+ fn apply_terminator_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ _terminator: &mir::Terminator<'tcx>,
+ location: Location,
+ ) {
+ let idx = self.effect_at_target(SeekTarget::After(location)).unwrap();
+ assert!(state.insert(idx));
+ }
+
+ fn apply_before_terminator_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ _terminator: &mir::Terminator<'tcx>,
+ location: Location,
+ ) {
+ let idx = self.effect_at_target(SeekTarget::Before(location)).unwrap();
+ assert!(state.insert(idx));
+ }
+
+ fn apply_call_return_effect(
+ &self,
+ state: &mut BitSet<Self::Idx>,
+ block: BasicBlock,
+ _func: &mir::Operand<'tcx>,
+ _args: &[mir::Operand<'tcx>],
+ _return_place: &mir::Place<'tcx>,
+ ) {
+ let location = self.body.terminator_loc(block);
+ let idx = self.effect_at_target(SeekTarget::AfterAssumeCallReturns(location)).unwrap();
+ assert!(state.insert(idx));
+ }
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+enum SeekTarget {
+ BlockStart(BasicBlock),
+ Before(Location),
+ After(Location),
+ AfterAssumeCallReturns(Location),
+}
+
+impl SeekTarget {
+ fn block(&self) -> BasicBlock {
+ use SeekTarget::*;
+
+ match *self {
+ BlockStart(block) => block,
+ Before(loc) | After(loc) | AfterAssumeCallReturns(loc) => loc.block,
+ }
+ }
+
+ /// An iterator over all possible `SeekTarget`s in a given block in order, starting with
+ /// `BlockStart`.
+ ///
+ /// This includes both `After` and `AfterAssumeCallReturns` for every `Location`.
+ fn iter_in_block(body: &mir::Body<'_>, block: BasicBlock) -> impl Iterator<Item = Self> {
+ let statements_and_terminator = (0..=body[block].statements.len())
+ .flat_map(|i| (0..3).map(move |j| (i, j)))
+ .map(move |(i, kind)| {
+ let loc = Location { block, statement_index: i };
+ match kind {
+ 0 => SeekTarget::Before(loc),
+ 1 => SeekTarget::After(loc),
+ 2 => SeekTarget::AfterAssumeCallReturns(loc),
+ _ => unreachable!(),
+ }
+ });
+
+ std::iter::once(SeekTarget::BlockStart(block)).chain(statements_and_terminator)
+ }
+}
+
+#[test]
+fn cursor_seek() {
+ let body = mock_body();
+ let body = &body;
+ let analysis = MockAnalysis { body };
+
+ let mut cursor =
+ Results { entry_sets: analysis.mock_entry_sets(), analysis }.into_results_cursor(body);
+
+ // Sanity check: the mock call return effect is unique and actually being applied.
+ let call_terminator_loc = Location { block: BasicBlock::from_usize(2), statement_index: 2 };
+ assert!(is_call_terminator_non_diverging(body, call_terminator_loc));
+
+ let call_return_effect = cursor
+ .analysis()
+ .effect_at_target(SeekTarget::AfterAssumeCallReturns(call_terminator_loc))
+ .unwrap();
+ assert_ne!(
+ call_return_effect,
+ cursor.analysis().effect_at_target(SeekTarget::After(call_terminator_loc)).unwrap()
+ );
+
+ cursor.seek_after(call_terminator_loc);
+ assert!(!cursor.get().contains(call_return_effect));
+ cursor.seek_after_assume_call_returns(call_terminator_loc);
+ assert!(cursor.get().contains(call_return_effect));
+
+ let every_target = || {
+ body.basic_blocks()
+ .iter_enumerated()
+ .flat_map(|(bb, _)| SeekTarget::iter_in_block(body, bb))
+ };
+
+ let mut seek_to_target = |targ| {
+ use SeekTarget::*;
+
+ match targ {
+ BlockStart(block) => cursor.seek_to_block_start(block),
+ Before(loc) => cursor.seek_before(loc),
+ After(loc) => cursor.seek_after(loc),
+ AfterAssumeCallReturns(loc) => cursor.seek_after_assume_call_returns(loc),
+ }
+
+ assert_eq!(cursor.get(), &cursor.analysis().expected_state_at_target(targ));
+ };
+
+ // Seek *to* every possible `SeekTarget` *from* every possible `SeekTarget`.
+ //
+ // By resetting the cursor to `from` each time it changes, we end up checking some edges twice.
+ // What we really want is an Eulerian cycle for the complete digraph over all possible
+ // `SeekTarget`s, but it's not worth spending the time to compute it.
+ for from in every_target() {
+ seek_to_target(from);
+
+ for to in every_target() {
+ seek_to_target(to);
+ seek_to_target(from);
+ }
+ }
+}
diff --git a/src/librustc_mir/transform/check_consts/resolver.rs b/src/librustc_mir/transform/check_consts/resolver.rs
index c445568..2cd2495 100644
--- a/src/librustc_mir/transform/check_consts/resolver.rs
+++ b/src/librustc_mir/transform/check_consts/resolver.rs
@@ -158,7 +158,7 @@
const BOTTOM_VALUE: bool = false;
}
-impl<Q> dataflow::Analysis<'tcx> for FlowSensitiveAnalysis<'_, '_, 'tcx, Q>
+impl<Q> dataflow::AnalysisDomain<'tcx> for FlowSensitiveAnalysis<'_, '_, 'tcx, Q>
where
Q: Qualif,
{
@@ -173,7 +173,12 @@
fn initialize_start_block(&self, _body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
self.transfer_function(state).initialize_state();
}
+}
+impl<Q> dataflow::Analysis<'tcx> for FlowSensitiveAnalysis<'_, '_, 'tcx, Q>
+where
+ Q: Qualif,
+{
fn apply_statement_effect(
&self,
state: &mut BitSet<Self::Idx>,
diff --git a/src/librustc_mir/transform/check_consts/validation.rs b/src/librustc_mir/transform/check_consts/validation.rs
index 1d5fb33..44b2a90 100644
--- a/src/librustc_mir/transform/check_consts/validation.rs
+++ b/src/librustc_mir/transform/check_consts/validation.rs
@@ -32,11 +32,10 @@
}
impl<Q: Qualif> QualifCursor<'a, 'mir, 'tcx, Q> {
- pub fn new(q: Q, item: &'a Item<'mir, 'tcx>, dead_unwinds: &BitSet<BasicBlock>) -> Self {
+ pub fn new(q: Q, item: &'a Item<'mir, 'tcx>) -> Self {
let analysis = FlowSensitiveAnalysis::new(q, item);
- let results =
- dataflow::Engine::new(item.tcx, &item.body, item.def_id, dead_unwinds, analysis)
- .iterate_to_fixpoint();
+ let results = dataflow::Engine::new_generic(item.tcx, &item.body, item.def_id, analysis)
+ .iterate_to_fixpoint();
let cursor = dataflow::ResultsCursor::new(*item.body, results);
let mut in_any_value_of_ty = BitSet::new_empty(item.body.local_decls.len());
@@ -145,12 +144,10 @@
impl Validator<'a, 'mir, 'tcx> {
pub fn new(item: &'a Item<'mir, 'tcx>) -> Self {
+ let needs_drop = QualifCursor::new(NeedsDrop, item);
+ let has_mut_interior = QualifCursor::new(HasMutInterior, item);
+
let dead_unwinds = BitSet::new_empty(item.body.basic_blocks().len());
-
- let needs_drop = QualifCursor::new(NeedsDrop, item, &dead_unwinds);
-
- let has_mut_interior = QualifCursor::new(HasMutInterior, item, &dead_unwinds);
-
let indirectly_mutable = old_dataflow::do_dataflow(
item.tcx,
&*item.body,
diff --git a/src/librustc_span/symbol.rs b/src/librustc_span/symbol.rs
index 889f609..e4f8b5a 100644
--- a/src/librustc_span/symbol.rs
+++ b/src/librustc_span/symbol.rs
@@ -167,6 +167,7 @@
bindings_after_at,
block,
bool,
+ borrowck_graphviz_format,
borrowck_graphviz_postflow,
borrowck_graphviz_preflow,
box_patterns,
@@ -337,6 +338,7 @@
FxHashSet,
FxHashMap,
gen_future,
+ gen_kill,
generators,
generic_associated_types,
generic_param_attrs,
@@ -735,6 +737,7 @@
try_trait,
tt,
tuple_indexing,
+ two_phase,
Ty,
ty,
type_alias_impl_trait,
