summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_mir_dataflow
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/rustc_mir_dataflow')
-rw-r--r--compiler/rustc_mir_dataflow/Cargo.toml1
-rw-r--r--compiler/rustc_mir_dataflow/locales/en-US.ftl29
-rw-r--r--compiler/rustc_mir_dataflow/src/drop_flag_effects.rs13
-rw-r--r--compiler/rustc_mir_dataflow/src/elaborate_drops.rs2
-rw-r--r--compiler/rustc_mir_dataflow/src/framework/direction.rs31
-rw-r--r--compiler/rustc_mir_dataflow/src/framework/engine.rs32
-rw-r--r--compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs4
-rw-r--r--compiler/rustc_mir_dataflow/src/impls/liveness.rs9
-rw-r--r--compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs1
-rw-r--r--compiler/rustc_mir_dataflow/src/lib.rs5
-rw-r--r--compiler/rustc_mir_dataflow/src/move_paths/builder.rs18
-rw-r--r--compiler/rustc_mir_dataflow/src/value_analysis.rs286
12 files changed, 287 insertions, 144 deletions
diff --git a/compiler/rustc_mir_dataflow/Cargo.toml b/compiler/rustc_mir_dataflow/Cargo.toml
index 324644b67..68c61a18d 100644
--- a/compiler/rustc_mir_dataflow/Cargo.toml
+++ b/compiler/rustc_mir_dataflow/Cargo.toml
@@ -19,6 +19,5 @@ rustc_index = { path = "../rustc_index" }
rustc_macros = { path = "../rustc_macros" }
rustc_middle = { path = "../rustc_middle" }
rustc_serialize = { path = "../rustc_serialize" }
-rustc_session = { path = "../rustc_session" }
rustc_target = { path = "../rustc_target" }
rustc_span = { path = "../rustc_span" }
diff --git a/compiler/rustc_mir_dataflow/locales/en-US.ftl b/compiler/rustc_mir_dataflow/locales/en-US.ftl
new file mode 100644
index 000000000..988541525
--- /dev/null
+++ b/compiler/rustc_mir_dataflow/locales/en-US.ftl
@@ -0,0 +1,29 @@
+mir_dataflow_path_must_end_in_filename =
+ path must end in a filename
+
+mir_dataflow_unknown_formatter =
+ unknown formatter
+
+mir_dataflow_duplicate_values_for =
+ duplicate values for `{$name}`
+
+mir_dataflow_requires_an_argument =
+ `{$name}` requires an argument
+
+mir_dataflow_stop_after_dataflow_ended_compilation =
+ stop_after_dataflow ended compilation
+
+mir_dataflow_peek_must_be_place_or_ref_place =
+ rustc_peek: argument expression must be either `place` or `&place`
+
+mir_dataflow_peek_must_be_not_temporary =
+ dataflow::sanity_check cannot feed a non-temp to rustc_peek
+
+mir_dataflow_peek_bit_not_set =
+ rustc_peek: bit not set
+
+mir_dataflow_peek_argument_not_a_local =
+ rustc_peek: argument was not a local
+
+mir_dataflow_peek_argument_untracked =
+ rustc_peek: argument untracked
diff --git a/compiler/rustc_mir_dataflow/src/drop_flag_effects.rs b/compiler/rustc_mir_dataflow/src/drop_flag_effects.rs
index 3224e13f7..0d466bbe5 100644
--- a/compiler/rustc_mir_dataflow/src/drop_flag_effects.rs
+++ b/compiler/rustc_mir_dataflow/src/drop_flag_effects.rs
@@ -1,5 +1,5 @@
use crate::elaborate_drops::DropFlagState;
-use rustc_middle::mir::{self, Body, Location};
+use rustc_middle::mir::{self, Body, Location, Terminator, TerminatorKind};
use rustc_middle::ty::{self, TyCtxt};
use rustc_target::abi::VariantIdx;
@@ -194,6 +194,17 @@ pub fn drop_flag_effects_for_location<'tcx, F>(
on_all_children_bits(tcx, body, move_data, path, |mpi| callback(mpi, DropFlagState::Absent))
}
+ // Drop does not count as a move but we should still consider the variable uninitialized.
+ if let Some(Terminator { kind: TerminatorKind::Drop { place, .. }, .. }) =
+ body.stmt_at(loc).right()
+ {
+ if let LookupResult::Exact(mpi) = move_data.rev_lookup.find(place.as_ref()) {
+ on_all_children_bits(tcx, body, move_data, mpi, |mpi| {
+ callback(mpi, DropFlagState::Absent)
+ })
+ }
+ }
+
debug!("drop_flag_effects: assignment for location({:?})", loc);
for_location_inits(tcx, body, move_data, loc, |mpi| callback(mpi, DropFlagState::Present));
diff --git a/compiler/rustc_mir_dataflow/src/elaborate_drops.rs b/compiler/rustc_mir_dataflow/src/elaborate_drops.rs
index 7836ae2e7..bd1208762 100644
--- a/compiler/rustc_mir_dataflow/src/elaborate_drops.rs
+++ b/compiler/rustc_mir_dataflow/src/elaborate_drops.rs
@@ -890,7 +890,7 @@ where
}
ty::Dynamic(..) => self.complete_drop(self.succ, self.unwind),
ty::Array(ety, size) => {
- let size = size.try_eval_usize(self.tcx(), self.elaborator.param_env());
+ let size = size.try_eval_target_usize(self.tcx(), self.elaborator.param_env());
self.open_drop_for_array(*ety, size)
}
ty::Slice(ety) => self.open_drop_for_array(*ety, None),
diff --git a/compiler/rustc_mir_dataflow/src/framework/direction.rs b/compiler/rustc_mir_dataflow/src/framework/direction.rs
index 077a21fc8..2ae3ae02f 100644
--- a/compiler/rustc_mir_dataflow/src/framework/direction.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/direction.rs
@@ -1,4 +1,3 @@
-use rustc_index::bit_set::BitSet;
use rustc_middle::mir::{self, BasicBlock, Location, SwitchTargets};
use rustc_middle::ty::TyCtxt;
use std::ops::RangeInclusive;
@@ -54,7 +53,6 @@ pub trait Direction {
analysis: &A,
tcx: TyCtxt<'tcx>,
body: &mir::Body<'tcx>,
- dead_unwinds: Option<&BitSet<BasicBlock>>,
exit_state: &mut A::Domain,
block: (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
propagate: impl FnMut(BasicBlock, &A::Domain),
@@ -221,7 +219,6 @@ impl Direction for Backward {
analysis: &A,
_tcx: TyCtxt<'tcx>,
body: &mir::Body<'tcx>,
- dead_unwinds: Option<&BitSet<BasicBlock>>,
exit_state: &mut A::Domain,
(bb, _bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
mut propagate: impl FnMut(BasicBlock, &A::Domain),
@@ -278,20 +275,6 @@ impl Direction for Backward {
}
}
- // Ignore dead unwinds.
- mir::TerminatorKind::Call { cleanup: Some(unwind), .. }
- | mir::TerminatorKind::Assert { cleanup: Some(unwind), .. }
- | mir::TerminatorKind::Drop { unwind: Some(unwind), .. }
- | mir::TerminatorKind::DropAndReplace { unwind: Some(unwind), .. }
- | mir::TerminatorKind::FalseUnwind { unwind: Some(unwind), .. }
- | mir::TerminatorKind::InlineAsm { cleanup: Some(unwind), .. }
- if unwind == bb =>
- {
- if dead_unwinds.map_or(true, |dead| !dead.contains(pred)) {
- propagate(pred, exit_state);
- }
- }
-
_ => propagate(pred, exit_state),
}
}
@@ -304,7 +287,6 @@ struct BackwardSwitchIntEdgeEffectsApplier<'a, 'tcx, D, F> {
exit_state: &'a mut D,
bb: BasicBlock,
propagate: &'a mut F,
-
effects_applied: bool,
}
@@ -484,7 +466,6 @@ impl Direction for Forward {
analysis: &A,
_tcx: TyCtxt<'tcx>,
_body: &mir::Body<'tcx>,
- dead_unwinds: Option<&BitSet<BasicBlock>>,
exit_state: &mut A::Domain,
(bb, bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
mut propagate: impl FnMut(BasicBlock, &A::Domain),
@@ -502,9 +483,7 @@ impl Direction for Forward {
| DropAndReplace { target, unwind, value: _, place: _ }
| FalseUnwind { real_target: target, unwind } => {
if let Some(unwind) = unwind {
- if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
- propagate(unwind, exit_state);
- }
+ propagate(unwind, exit_state);
}
propagate(target, exit_state);
@@ -534,9 +513,7 @@ impl Direction for Forward {
fn_span: _,
} => {
if let Some(unwind) = cleanup {
- if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
- propagate(unwind, exit_state);
- }
+ propagate(unwind, exit_state);
}
if let Some(target) = target {
@@ -560,9 +537,7 @@ impl Direction for Forward {
cleanup,
} => {
if let Some(unwind) = cleanup {
- if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
- propagate(unwind, exit_state);
- }
+ propagate(unwind, exit_state);
}
if let Some(target) = destination {
diff --git a/compiler/rustc_mir_dataflow/src/framework/engine.rs b/compiler/rustc_mir_dataflow/src/framework/engine.rs
index 6ddbe69e1..91c3bf0ad 100644
--- a/compiler/rustc_mir_dataflow/src/framework/engine.rs
+++ b/compiler/rustc_mir_dataflow/src/framework/engine.rs
@@ -12,7 +12,6 @@ use rustc_ast as ast;
use rustc_data_structures::work_queue::WorkQueue;
use rustc_graphviz as dot;
use rustc_hir::def_id::DefId;
-use rustc_index::bit_set::BitSet;
use rustc_index::vec::{Idx, IndexVec};
use rustc_middle::mir::{self, traversal, BasicBlock};
use rustc_middle::mir::{create_dump_file, dump_enabled};
@@ -78,7 +77,6 @@ where
{
tcx: TyCtxt<'tcx>,
body: &'a mir::Body<'tcx>,
- dead_unwinds: Option<&'a BitSet<BasicBlock>>,
entry_sets: IndexVec<BasicBlock, A::Domain>,
pass_name: Option<&'static str>,
analysis: A,
@@ -154,25 +152,7 @@ where
bug!("`initialize_start_block` is not yet supported for backward dataflow analyses");
}
- Engine {
- analysis,
- tcx,
- body,
- dead_unwinds: None,
- pass_name: None,
- entry_sets,
- apply_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
+ Engine { analysis, tcx, body, pass_name: None, entry_sets, apply_trans_for_block }
}
/// Adds an identifier to the graphviz output for this particular run of a dataflow analysis.
@@ -190,14 +170,7 @@ where
A::Domain: DebugWithContext<A>,
{
let Engine {
- analysis,
- body,
- dead_unwinds,
- mut entry_sets,
- tcx,
- apply_trans_for_block,
- pass_name,
- ..
+ analysis, body, mut entry_sets, tcx, apply_trans_for_block, pass_name, ..
} = self;
let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks.len());
@@ -236,7 +209,6 @@ where
&analysis,
tcx,
body,
- dead_unwinds,
&mut state,
(bb, bb_data),
|target: BasicBlock, state: &A::Domain| {
diff --git a/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs b/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs
index 0f8e86d1d..6f4e7fd46 100644
--- a/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs
@@ -121,7 +121,9 @@ where
// for now. See discussion on [#61069].
//
// [#61069]: https://github.com/rust-lang/rust/pull/61069
- self.trans.gen(dropped_place.local);
+ if !dropped_place.is_indirect() {
+ self.trans.gen(dropped_place.local);
+ }
}
TerminatorKind::Abort
diff --git a/compiler/rustc_mir_dataflow/src/impls/liveness.rs b/compiler/rustc_mir_dataflow/src/impls/liveness.rs
index 923dc16c1..633a5674f 100644
--- a/compiler/rustc_mir_dataflow/src/impls/liveness.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/liveness.rs
@@ -254,13 +254,7 @@ impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
) {
// Compute the place that we are storing to, if any
let destination = match &statement.kind {
- StatementKind::Assign(assign) => {
- if assign.1.is_safe_to_remove() {
- Some(assign.0)
- } else {
- None
- }
- }
+ StatementKind::Assign(assign) => assign.1.is_safe_to_remove().then_some(assign.0),
StatementKind::SetDiscriminant { place, .. } | StatementKind::Deinit(place) => {
Some(**place)
}
@@ -271,6 +265,7 @@ impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
| StatementKind::AscribeUserType(..)
| StatementKind::Coverage(..)
| StatementKind::Intrinsic(..)
+ | StatementKind::ConstEvalCounter
| StatementKind::Nop => None,
};
if let Some(destination) = destination {
diff --git a/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs b/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs
index 8d379b90a..fcf0ce9d8 100644
--- a/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs
@@ -141,6 +141,7 @@ impl<'mir, 'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'mir, 'tc
StatementKind::AscribeUserType(..)
| StatementKind::Coverage(..)
| StatementKind::FakeRead(..)
+ | StatementKind::ConstEvalCounter
| StatementKind::Nop
| StatementKind::Retag(..)
| StatementKind::Intrinsic(..)
diff --git a/compiler/rustc_mir_dataflow/src/lib.rs b/compiler/rustc_mir_dataflow/src/lib.rs
index 7f40cfca3..b1e03faff 100644
--- a/compiler/rustc_mir_dataflow/src/lib.rs
+++ b/compiler/rustc_mir_dataflow/src/lib.rs
@@ -1,6 +1,7 @@
#![feature(associated_type_defaults)]
#![feature(box_patterns)]
#![feature(exact_size_is_empty)]
+#![feature(let_chains)]
#![feature(min_specialization)]
#![feature(once_cell)]
#![feature(stmt_expr_attributes)]
@@ -15,7 +16,9 @@ extern crate tracing;
extern crate rustc_middle;
use rustc_ast::MetaItem;
+use rustc_errors::{DiagnosticMessage, SubdiagnosticMessage};
use rustc_hir::def_id::DefId;
+use rustc_macros::fluent_messages;
use rustc_middle::ty::{self, TyCtxt};
use rustc_span::symbol::{sym, Symbol};
@@ -43,6 +46,8 @@ pub mod storage;
pub mod un_derefer;
pub mod value_analysis;
+fluent_messages! { "../locales/en-US.ftl" }
+
pub(crate) mod indexes {
pub(crate) use super::move_paths::MovePathIndex;
}
diff --git a/compiler/rustc_mir_dataflow/src/move_paths/builder.rs b/compiler/rustc_mir_dataflow/src/move_paths/builder.rs
index f46fd118b..4a163028f 100644
--- a/compiler/rustc_mir_dataflow/src/move_paths/builder.rs
+++ b/compiler/rustc_mir_dataflow/src/move_paths/builder.rs
@@ -126,7 +126,7 @@ impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> {
BorrowedContent {
target_place: Place {
local: place.local,
- projection: tcx.intern_place_elems(proj),
+ projection: tcx.mk_place_elems(proj),
},
},
));
@@ -165,7 +165,7 @@ impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> {
if union_path.is_none() {
base = self.add_move_path(base, elem, |tcx| Place {
local: place.local,
- projection: tcx.intern_place_elems(&place.projection[..i + 1]),
+ projection: tcx.mk_place_elems(&place.projection[..i + 1]),
});
}
}
@@ -331,6 +331,7 @@ impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> {
| StatementKind::AscribeUserType(..)
| StatementKind::Coverage(..)
| StatementKind::Intrinsic(..)
+ | StatementKind::ConstEvalCounter
| StatementKind::Nop => {}
}
}
@@ -375,7 +376,8 @@ impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> {
| TerminatorKind::Resume
| TerminatorKind::Abort
| TerminatorKind::GeneratorDrop
- | TerminatorKind::Unreachable => {}
+ | TerminatorKind::Unreachable
+ | TerminatorKind::Drop { .. } => {}
TerminatorKind::Assert { ref cond, .. } => {
self.gather_operand(cond);
@@ -390,10 +392,6 @@ impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> {
self.create_move_path(place);
self.gather_init(place.as_ref(), InitKind::Deep);
}
-
- TerminatorKind::Drop { place, target: _, unwind: _ } => {
- self.gather_move(place);
- }
TerminatorKind::DropAndReplace { place, ref value, .. } => {
self.create_move_path(place);
self.gather_operand(value);
@@ -478,7 +476,7 @@ impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> {
// `ConstIndex` patterns. This is done to ensure that all move paths
// are disjoint, which is expected by drop elaboration.
let base_place =
- Place { local: place.local, projection: self.builder.tcx.intern_place_elems(base) };
+ Place { local: place.local, projection: self.builder.tcx.mk_place_elems(base) };
let base_path = match self.move_path_for(base_place) {
Ok(path) => path,
Err(MoveError::UnionMove { path }) => {
@@ -492,7 +490,9 @@ impl<'b, 'a, 'tcx> Gatherer<'b, 'a, 'tcx> {
};
let base_ty = base_place.ty(self.builder.body, self.builder.tcx).ty;
let len: u64 = match base_ty.kind() {
- ty::Array(_, size) => size.eval_usize(self.builder.tcx, self.builder.param_env),
+ ty::Array(_, size) => {
+ size.eval_target_usize(self.builder.tcx, self.builder.param_env)
+ }
_ => bug!("from_end: false slice pattern of non-array type"),
};
for offset in from..to {
diff --git a/compiler/rustc_mir_dataflow/src/value_analysis.rs b/compiler/rustc_mir_dataflow/src/value_analysis.rs
index 0522c6579..401db890a 100644
--- a/compiler/rustc_mir_dataflow/src/value_analysis.rs
+++ b/compiler/rustc_mir_dataflow/src/value_analysis.rs
@@ -24,7 +24,7 @@
//! - The bottom state denotes uninitialized memory. Because we are only doing a sound approximation
//! of the actual execution, we can also use this state for places where access would be UB.
//!
-//! - The assignment logic in `State::assign_place_idx` assumes that the places are non-overlapping,
+//! - The assignment logic in `State::insert_place_idx` assumes that the places are non-overlapping,
//! or identical. Note that this refers to place expressions, not memory locations.
//!
//! - Currently, places that have their reference taken cannot be tracked. Although this would be
@@ -35,6 +35,7 @@
use std::fmt::{Debug, Formatter};
use rustc_data_structures::fx::FxHashMap;
+use rustc_index::bit_set::BitSet;
use rustc_index::vec::IndexVec;
use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
use rustc_middle::mir::*;
@@ -64,10 +65,8 @@ pub trait ValueAnalysis<'tcx> {
StatementKind::Assign(box (place, rvalue)) => {
self.handle_assign(*place, rvalue, state);
}
- StatementKind::SetDiscriminant { .. } => {
- // Could treat this as writing a constant to a pseudo-place.
- // But discriminants are currently not tracked, so we do nothing.
- // Related: https://github.com/rust-lang/unsafe-code-guidelines/issues/84
+ StatementKind::SetDiscriminant { box ref place, .. } => {
+ state.flood_discr(place.as_ref(), self.map());
}
StatementKind::Intrinsic(box intrinsic) => {
self.handle_intrinsic(intrinsic, state);
@@ -84,7 +83,8 @@ pub trait ValueAnalysis<'tcx> {
StatementKind::Retag(..) => {
// We don't track references.
}
- StatementKind::Nop
+ StatementKind::ConstEvalCounter
+ | StatementKind::Nop
| StatementKind::FakeRead(..)
| StatementKind::Coverage(..)
| StatementKind::AscribeUserType(..) => (),
@@ -222,13 +222,13 @@ pub trait ValueAnalysis<'tcx> {
self.super_terminator(terminator, state)
}
- fn super_terminator(&self, terminator: &Terminator<'tcx>, _state: &mut State<Self::Value>) {
+ fn super_terminator(&self, terminator: &Terminator<'tcx>, state: &mut State<Self::Value>) {
match &terminator.kind {
TerminatorKind::Call { .. } | TerminatorKind::InlineAsm { .. } => {
// Effect is applied by `handle_call_return`.
}
- TerminatorKind::Drop { .. } => {
- // We don't track dropped places.
+ TerminatorKind::Drop { place, .. } => {
+ state.flood_with(place.as_ref(), self.map(), Self::Value::bottom());
}
TerminatorKind::DropAndReplace { .. } | TerminatorKind::Yield { .. } => {
// They would have an effect, but are not allowed in this phase.
@@ -445,26 +445,51 @@ impl<V: Clone + HasTop + HasBottom> State<V> {
}
pub fn flood_with(&mut self, place: PlaceRef<'_>, map: &Map, value: V) {
- if let Some(root) = map.find(place) {
- self.flood_idx_with(root, map, value);
- }
+ let StateData::Reachable(values) = &mut self.0 else { return };
+ map.for_each_aliasing_place(place, None, &mut |place| {
+ if let Some(vi) = map.places[place].value_index {
+ values[vi] = value.clone();
+ }
+ });
}
pub fn flood(&mut self, place: PlaceRef<'_>, map: &Map) {
self.flood_with(place, map, V::top())
}
- pub fn flood_idx_with(&mut self, place: PlaceIndex, map: &Map, value: V) {
+ pub fn flood_discr_with(&mut self, place: PlaceRef<'_>, map: &Map, value: V) {
let StateData::Reachable(values) = &mut self.0 else { return };
- map.preorder_invoke(place, &mut |place| {
+ map.for_each_aliasing_place(place, Some(TrackElem::Discriminant), &mut |place| {
if let Some(vi) = map.places[place].value_index {
values[vi] = value.clone();
}
});
}
- pub fn flood_idx(&mut self, place: PlaceIndex, map: &Map) {
- self.flood_idx_with(place, map, V::top())
+ pub fn flood_discr(&mut self, place: PlaceRef<'_>, map: &Map) {
+ self.flood_discr_with(place, map, V::top())
+ }
+
+ /// Low-level method that assigns to a place.
+ /// This does nothing if the place is not tracked.
+ ///
+ /// The target place must have been flooded before calling this method.
+ pub fn insert_idx(&mut self, target: PlaceIndex, result: ValueOrPlace<V>, map: &Map) {
+ match result {
+ ValueOrPlace::Value(value) => self.insert_value_idx(target, value, map),
+ ValueOrPlace::Place(source) => self.insert_place_idx(target, source, map),
+ }
+ }
+
+ /// Low-level method that assigns a value to a place.
+ /// This does nothing if the place is not tracked.
+ ///
+ /// The target place must have been flooded before calling this method.
+ pub fn insert_value_idx(&mut self, target: PlaceIndex, value: V, map: &Map) {
+ let StateData::Reachable(values) = &mut self.0 else { return };
+ if let Some(value_index) = map.places[target].value_index {
+ values[value_index] = value;
+ }
}
/// Copies `source` to `target`, including all tracked places beneath.
@@ -472,50 +497,41 @@ impl<V: Clone + HasTop + HasBottom> State<V> {
/// If `target` contains a place that is not contained in `source`, it will be overwritten with
/// Top. Also, because this will copy all entries one after another, it may only be used for
/// places that are non-overlapping or identical.
- pub fn assign_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map) {
+ ///
+ /// The target place must have been flooded before calling this method.
+ fn insert_place_idx(&mut self, target: PlaceIndex, source: PlaceIndex, map: &Map) {
let StateData::Reachable(values) = &mut self.0 else { return };
- // If both places are tracked, we copy the value to the target. If the target is tracked,
- // but the source is not, we have to invalidate the value in target. If the target is not
- // tracked, then we don't have to do anything.
+ // If both places are tracked, we copy the value to the target.
+ // If the target is tracked, but the source is not, we do nothing, as invalidation has
+ // already been performed.
if let Some(target_value) = map.places[target].value_index {
if let Some(source_value) = map.places[source].value_index {
values[target_value] = values[source_value].clone();
- } else {
- values[target_value] = V::top();
}
}
for target_child in map.children(target) {
// Try to find corresponding child and recurse. Reasoning is similar as above.
let projection = map.places[target_child].proj_elem.unwrap();
if let Some(source_child) = map.projections.get(&(source, projection)) {
- self.assign_place_idx(target_child, *source_child, map);
- } else {
- self.flood_idx(target_child, map);
+ self.insert_place_idx(target_child, *source_child, map);
}
}
}
+ /// Helper method to interpret `target = result`.
pub fn assign(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map) {
+ self.flood(target, map);
if let Some(target) = map.find(target) {
- self.assign_idx(target, result, map);
- } else {
- // We don't track this place nor any projections, assignment can be ignored.
+ self.insert_idx(target, result, map);
}
}
- pub fn assign_idx(&mut self, target: PlaceIndex, result: ValueOrPlace<V>, map: &Map) {
- match result {
- ValueOrPlace::Value(value) => {
- // First flood the target place in case we also track any projections (although
- // this scenario is currently not well-supported by the API).
- self.flood_idx(target, map);
- let StateData::Reachable(values) = &mut self.0 else { return };
- if let Some(value_index) = map.places[target].value_index {
- values[value_index] = value;
- }
- }
- ValueOrPlace::Place(source) => self.assign_place_idx(target, source, map),
+ /// Helper method for assignments to a discriminant.
+ pub fn assign_discr(&mut self, target: PlaceRef<'_>, result: ValueOrPlace<V>, map: &Map) {
+ self.flood_discr(target, map);
+ if let Some(target) = map.find_discr(target) {
+ self.insert_idx(target, result, map);
}
}
@@ -524,6 +540,14 @@ impl<V: Clone + HasTop + HasBottom> State<V> {
map.find(place).map(|place| self.get_idx(place, map)).unwrap_or(V::top())
}
+ /// Retrieve the value stored for a place, or ⊤ if it is not tracked.
+ pub fn get_discr(&self, place: PlaceRef<'_>, map: &Map) -> V {
+ match map.find_discr(place) {
+ Some(place) => self.get_idx(place, map),
+ None => V::top(),
+ }
+ }
+
/// Retrieve the value stored for a place index, or ⊤ if it is not tracked.
pub fn get_idx(&self, place: PlaceIndex, map: &Map) -> V {
match &self.0 {
@@ -580,15 +604,15 @@ impl Map {
/// This is currently the only way to create a [`Map`]. The way in which the tracked places are
/// chosen is an implementation detail and may not be relied upon (other than that their type
/// passes the filter).
- #[instrument(skip_all, level = "debug")]
pub fn from_filter<'tcx>(
tcx: TyCtxt<'tcx>,
body: &Body<'tcx>,
filter: impl FnMut(Ty<'tcx>) -> bool,
+ place_limit: Option<usize>,
) -> Self {
let mut map = Self::new();
let exclude = excluded_locals(body);
- map.register_with_filter(tcx, body, filter, &exclude);
+ map.register_with_filter(tcx, body, filter, exclude, place_limit);
debug!("registered {} places ({} nodes in total)", map.value_count, map.places.len());
map
}
@@ -599,20 +623,28 @@ impl Map {
tcx: TyCtxt<'tcx>,
body: &Body<'tcx>,
mut filter: impl FnMut(Ty<'tcx>) -> bool,
- exclude: &IndexVec<Local, bool>,
+ exclude: BitSet<Local>,
+ place_limit: Option<usize>,
) {
// We use this vector as stack, pushing and popping projections.
let mut projection = Vec::new();
for (local, decl) in body.local_decls.iter_enumerated() {
- if !exclude[local] {
- self.register_with_filter_rec(tcx, local, &mut projection, decl.ty, &mut filter);
+ if !exclude.contains(local) {
+ self.register_with_filter_rec(
+ tcx,
+ local,
+ &mut projection,
+ decl.ty,
+ &mut filter,
+ place_limit,
+ );
}
}
}
/// Potentially register the (local, projection) place and its fields, recursively.
///
- /// Invariant: The projection must only contain fields.
+ /// Invariant: The projection must only contain trackable elements.
fn register_with_filter_rec<'tcx>(
&mut self,
tcx: TyCtxt<'tcx>,
@@ -620,27 +652,56 @@ impl Map {
projection: &mut Vec<PlaceElem<'tcx>>,
ty: Ty<'tcx>,
filter: &mut impl FnMut(Ty<'tcx>) -> bool,
+ place_limit: Option<usize>,
) {
- // Note: The framework supports only scalars for now.
- if filter(ty) && ty.is_scalar() {
- // We know that the projection only contains trackable elements.
- let place = self.make_place(local, projection).unwrap();
+ if let Some(place_limit) = place_limit && self.value_count >= place_limit {
+ return
+ }
- // Allocate a value slot if it doesn't have one.
- if self.places[place].value_index.is_none() {
- self.places[place].value_index = Some(self.value_count.into());
- self.value_count += 1;
+ // We know that the projection only contains trackable elements.
+ let place = self.make_place(local, projection).unwrap();
+
+ // Allocate a value slot if it doesn't have one, and the user requested one.
+ if self.places[place].value_index.is_none() && filter(ty) {
+ self.places[place].value_index = Some(self.value_count.into());
+ self.value_count += 1;
+ }
+
+ if ty.is_enum() {
+ let discr_ty = ty.discriminant_ty(tcx);
+ if filter(discr_ty) {
+ let discr = *self
+ .projections
+ .entry((place, TrackElem::Discriminant))
+ .or_insert_with(|| {
+ // Prepend new child to the linked list.
+ let next = self.places.push(PlaceInfo::new(Some(TrackElem::Discriminant)));
+ self.places[next].next_sibling = self.places[place].first_child;
+ self.places[place].first_child = Some(next);
+ next
+ });
+
+ // Allocate a value slot if it doesn't have one.
+ if self.places[discr].value_index.is_none() {
+ self.places[discr].value_index = Some(self.value_count.into());
+ self.value_count += 1;
+ }
}
}
// Recurse with all fields of this place.
iter_fields(ty, tcx, |variant, field, ty| {
- if variant.is_some() {
- // Downcasts are currently not supported.
+ if let Some(variant) = variant {
+ projection.push(PlaceElem::Downcast(None, variant));
+ let _ = self.make_place(local, projection);
+ projection.push(PlaceElem::Field(field, ty));
+ self.register_with_filter_rec(tcx, local, projection, ty, filter, place_limit);
+ projection.pop();
+ projection.pop();
return;
}
projection.push(PlaceElem::Field(field, ty));
- self.register_with_filter_rec(tcx, local, projection, ty, filter);
+ self.register_with_filter_rec(tcx, local, projection, ty, filter, place_limit);
projection.pop();
});
}
@@ -683,23 +744,105 @@ impl Map {
}
/// Locates the given place, if it exists in the tree.
- pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
+ pub fn find_extra(
+ &self,
+ place: PlaceRef<'_>,
+ extra: impl IntoIterator<Item = TrackElem>,
+ ) -> Option<PlaceIndex> {
let mut index = *self.locals.get(place.local)?.as_ref()?;
for &elem in place.projection {
index = self.apply(index, elem.try_into().ok()?)?;
}
+ for elem in extra {
+ index = self.apply(index, elem)?;
+ }
Some(index)
}
+ /// Locates the given place, if it exists in the tree.
+ pub fn find(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
+ self.find_extra(place, [])
+ }
+
+ /// Locates the given place and applies `Discriminant`, if it exists in the tree.
+ pub fn find_discr(&self, place: PlaceRef<'_>) -> Option<PlaceIndex> {
+ self.find_extra(place, [TrackElem::Discriminant])
+ }
+
/// Iterate over all direct children.
pub fn children(&self, parent: PlaceIndex) -> impl Iterator<Item = PlaceIndex> + '_ {
Children::new(self, parent)
}
+ /// Invoke a function on the given place and all places that may alias it.
+ ///
+ /// In particular, when the given place has a variant downcast, we invoke the function on all
+ /// the other variants.
+ ///
+ /// `tail_elem` allows to support discriminants that are not a place in MIR, but that we track
+ /// as such.
+ pub fn for_each_aliasing_place(
+ &self,
+ place: PlaceRef<'_>,
+ tail_elem: Option<TrackElem>,
+ f: &mut impl FnMut(PlaceIndex),
+ ) {
+ if place.is_indirect() {
+ // We do not track indirect places.
+ return;
+ }
+ let Some(&Some(mut index)) = self.locals.get(place.local) else {
+ // The local is not tracked at all, so it does not alias anything.
+ return;
+ };
+ let elems = place
+ .projection
+ .iter()
+ .map(|&elem| elem.try_into())
+ .chain(tail_elem.map(Ok).into_iter());
+ for elem in elems {
+ // A field aliases the parent place.
+ f(index);
+
+ let Ok(elem) = elem else { return };
+ let sub = self.apply(index, elem);
+ if let TrackElem::Variant(..) | TrackElem::Discriminant = elem {
+ // Enum variant fields and enum discriminants alias each another.
+ self.for_each_variant_sibling(index, sub, f);
+ }
+ if let Some(sub) = sub {
+ index = sub
+ } else {
+ return;
+ }
+ }
+ self.preorder_invoke(index, f);
+ }
+
+ /// Invoke the given function on all the descendants of the given place, except one branch.
+ fn for_each_variant_sibling(
+ &self,
+ parent: PlaceIndex,
+ preserved_child: Option<PlaceIndex>,
+ f: &mut impl FnMut(PlaceIndex),
+ ) {
+ for sibling in self.children(parent) {
+ let elem = self.places[sibling].proj_elem;
+ // Only invalidate variants and discriminant. Fields (for generators) are not
+ // invalidated by assignment to a variant.
+ if let Some(TrackElem::Variant(..) | TrackElem::Discriminant) = elem
+ // Only invalidate the other variants, the current one is fine.
+ && Some(sibling) != preserved_child
+ {
+ self.preorder_invoke(sibling, f);
+ }
+ }
+ }
+
/// Invoke a function on the given place and all descendants.
- pub fn preorder_invoke(&self, root: PlaceIndex, f: &mut impl FnMut(PlaceIndex)) {
+ fn preorder_invoke(&self, root: PlaceIndex, f: &mut impl FnMut(PlaceIndex)) {
f(root);
for child in self.children(root) {
self.preorder_invoke(child, f);
@@ -758,6 +901,7 @@ impl<'a> Iterator for Children<'a> {
}
/// Used as the result of an operand or r-value.
+#[derive(Debug)]
pub enum ValueOrPlace<V> {
Value(V),
Place(PlaceIndex),
@@ -775,6 +919,8 @@ impl<V: HasTop> ValueOrPlace<V> {
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum TrackElem {
Field(Field),
+ Variant(VariantIdx),
+ Discriminant,
}
impl<V, T> TryFrom<ProjectionElem<V, T>> for TrackElem {
@@ -783,13 +929,14 @@ impl<V, T> TryFrom<ProjectionElem<V, T>> for TrackElem {
fn try_from(value: ProjectionElem<V, T>) -> Result<Self, Self::Error> {
match value {
ProjectionElem::Field(field, _) => Ok(TrackElem::Field(field)),
+ ProjectionElem::Downcast(_, idx) => Ok(TrackElem::Variant(idx)),
_ => Err(()),
}
}
}
/// Invokes `f` on all direct fields of `ty`.
-fn iter_fields<'tcx>(
+pub fn iter_fields<'tcx>(
ty: Ty<'tcx>,
tcx: TyCtxt<'tcx>,
mut f: impl FnMut(Option<VariantIdx>, Field, Ty<'tcx>),
@@ -823,26 +970,27 @@ fn iter_fields<'tcx>(
}
/// Returns all locals with projections that have their reference or address taken.
-fn excluded_locals(body: &Body<'_>) -> IndexVec<Local, bool> {
+pub fn excluded_locals(body: &Body<'_>) -> BitSet<Local> {
struct Collector {
- result: IndexVec<Local, bool>,
+ result: BitSet<Local>,
}
impl<'tcx> Visitor<'tcx> for Collector {
fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, _location: Location) {
- if context.is_borrow()
+ if (context.is_borrow()
|| context.is_address_of()
|| context.is_drop()
- || context == PlaceContext::MutatingUse(MutatingUseContext::AsmOutput)
+ || context == PlaceContext::MutatingUse(MutatingUseContext::AsmOutput))
+ && !place.is_indirect()
{
// A pointer to a place could be used to access other places with the same local,
// hence we have to exclude the local completely.
- self.result[place.local] = true;
+ self.result.insert(place.local);
}
}
}
- let mut collector = Collector { result: IndexVec::from_elem(false, &body.local_decls) };
+ let mut collector = Collector { result: BitSet::new_empty(body.local_decls.len()) };
collector.visit_body(body);
collector.result
}
@@ -898,6 +1046,12 @@ fn debug_with_context_rec<V: Debug + Eq>(
for child in map.children(place) {
let info_elem = map.places[child].proj_elem.unwrap();
let child_place_str = match info_elem {
+ TrackElem::Discriminant => {
+ format!("discriminant({})", place_str)
+ }
+ TrackElem::Variant(idx) => {
+ format!("({} as {:?})", place_str, idx)
+ }
TrackElem::Field(field) => {
if place_str.starts_with('*') {
format!("({}).{}", place_str, field.index())
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-03 09:31:33 +0000