1 //! This pass eliminates casting of arrays into slices when their length
2 //! is taken using `.len()` method. Handy to preserve information in MIR for const prop
5 use rustc_data_structures::fx::FxIndexMap;
6 use rustc_data_structures::intern::Interned;
7 use rustc_index::bit_set::BitSet;
8 use rustc_index::vec::IndexVec;
9 use rustc_middle::mir::*;
10 use rustc_middle::ty::{self, ReErased, Region, TyCtxt};
12 const MAX_NUM_BLOCKS: usize = 800;
13 const MAX_NUM_LOCALS: usize = 3000;
15 pub struct NormalizeArrayLen;
17 impl<'tcx> MirPass<'tcx> for NormalizeArrayLen {
18 fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
20 sess.mir_opt_level() >= 4 && sess.opts.unstable_opts.unsound_mir_opts
23 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
24 // early returns for edge cases of highly unrolled functions
25 if body.basic_blocks.len() > MAX_NUM_BLOCKS {
28 if body.local_decls.len() > MAX_NUM_LOCALS {
31 normalize_array_len_calls(tcx, body)
35 pub fn normalize_array_len_calls<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
36 // We don't ever touch terminators, so no need to invalidate the CFG cache
37 let basic_blocks = body.basic_blocks.as_mut_preserves_cfg();
38 let local_decls = &mut body.local_decls;
40 // do a preliminary analysis to see if we ever have locals of type `[T;N]` or `&[T;N]`
41 let mut interesting_locals = BitSet::new_empty(local_decls.len());
42 for (local, decl) in local_decls.iter_enumerated() {
43 match decl.ty.kind() {
45 interesting_locals.insert(local);
47 ty::Ref(.., ty, Mutability::Not) => match ty.kind() {
49 interesting_locals.insert(local);
56 if interesting_locals.is_empty() {
57 // we have found nothing to analyze
60 let num_intesting_locals = interesting_locals.count();
61 let mut state = FxIndexMap::with_capacity_and_hasher(num_intesting_locals, Default::default());
62 let mut patches_scratchpad =
63 FxIndexMap::with_capacity_and_hasher(num_intesting_locals, Default::default());
64 let mut replacements_scratchpad =
65 FxIndexMap::with_capacity_and_hasher(num_intesting_locals, Default::default());
66 for block in basic_blocks {
67 // make length calls for arrays [T; N] not to decay into length calls for &[T]
68 // that forbids constant propagation
69 normalize_array_len_call(
75 &mut patches_scratchpad,
76 &mut replacements_scratchpad,
79 patches_scratchpad.clear();
80 replacements_scratchpad.clear();
84 struct Patcher<'a, 'tcx> {
86 patches_scratchpad: &'a FxIndexMap<usize, usize>,
87 replacements_scratchpad: &'a mut FxIndexMap<usize, Local>,
88 local_decls: &'a mut IndexVec<Local, LocalDecl<'tcx>>,
92 impl<'tcx> Patcher<'_, 'tcx> {
93 fn patch_expand_statement(
95 statement: &mut Statement<'tcx>,
96 ) -> Option<std::vec::IntoIter<Statement<'tcx>>> {
97 let idx = self.statement_idx;
98 if let Some(len_statemnt_idx) = self.patches_scratchpad.get(&idx).copied() {
99 let mut statements = Vec::with_capacity(2);
101 // we are at statement that performs a cast. The only sound way is
102 // to create another local that performs a similar copy without a cast and then
103 // use this copy in the Len operation
105 match &statement.kind {
106 StatementKind::Assign(box (
109 CastKind::Pointer(ty::adjustment::PointerCast::Unsize),
115 Operand::Copy(place) | Operand::Move(place) => {
117 let ty = operand.ty(self.local_decls, self.tcx);
118 let local_decl = LocalDecl::with_source_info(ty, statement.source_info);
119 let local = self.local_decls.push(local_decl);
121 let mut make_live_statement = statement.clone();
122 make_live_statement.kind = StatementKind::StorageLive(local);
123 statements.push(make_live_statement);
126 let operand = Operand::Copy(*place);
127 let mut make_copy_statement = statement.clone();
128 let assign_to = Place::from(local);
129 let rvalue = Rvalue::Use(operand);
130 make_copy_statement.kind =
131 StatementKind::Assign(Box::new((assign_to, rvalue)));
132 statements.push(make_copy_statement);
134 // to reorder we have to copy and make NOP
135 statements.push(statement.clone());
136 statement.make_nop();
138 self.replacements_scratchpad.insert(len_statemnt_idx, local);
141 unreachable!("it's a bug in the implementation")
146 unreachable!("it's a bug in the implementation")
150 self.statement_idx += 1;
152 Some(statements.into_iter())
153 } else if let Some(local) = self.replacements_scratchpad.get(&idx).copied() {
154 let mut statements = Vec::with_capacity(2);
156 match &statement.kind {
157 StatementKind::Assign(box (into, Rvalue::Len(place))) => {
158 let add_deref = if let Some(..) = place.as_local() {
160 } else if let Some(..) = place.local_or_deref_local() {
163 unreachable!("it's a bug in the implementation")
165 // replace len statement
166 let mut len_statement = statement.clone();
167 let mut place = Place::from(local);
169 place = self.tcx.mk_place_deref(place);
172 StatementKind::Assign(Box::new((*into, Rvalue::Len(place))));
173 statements.push(len_statement);
175 // make temporary dead
176 let mut make_dead_statement = statement.clone();
177 make_dead_statement.kind = StatementKind::StorageDead(local);
178 statements.push(make_dead_statement);
180 // make original statement NOP
181 statement.make_nop();
184 unreachable!("it's a bug in the implementation")
188 self.statement_idx += 1;
190 Some(statements.into_iter())
192 self.statement_idx += 1;
198 fn normalize_array_len_call<'tcx>(
200 block: &mut BasicBlockData<'tcx>,
201 local_decls: &mut IndexVec<Local, LocalDecl<'tcx>>,
202 interesting_locals: &BitSet<Local>,
203 state: &mut FxIndexMap<Local, usize>,
204 patches_scratchpad: &mut FxIndexMap<usize, usize>,
205 replacements_scratchpad: &mut FxIndexMap<usize, Local>,
207 for (statement_idx, statement) in block.statements.iter_mut().enumerate() {
208 match &mut statement.kind {
209 StatementKind::Assign(box (place, rvalue)) => {
212 CastKind::Pointer(ty::adjustment::PointerCast::Unsize),
216 let Some(local) = place.as_local() else { return };
218 Operand::Copy(place) | Operand::Move(place) => {
219 let Some(operand_local) = place.local_or_deref_local() else { return; };
220 if !interesting_locals.contains(operand_local) {
223 let operand_ty = local_decls[operand_local].ty;
224 match (operand_ty.kind(), cast_ty.kind()) {
225 (ty::Array(of_ty_src, ..), ty::Slice(of_ty_dst)) => {
226 if of_ty_src == of_ty_dst {
227 // this is a cast from [T; N] into [T], so we are good
228 state.insert(local, statement_idx);
231 // current way of patching doesn't allow to work with `mut`
234 Region(Interned(ReErased, _)),
239 Region(Interned(ReErased, _)),
244 match (operand_ty.kind(), cast_ty.kind()) {
245 // current way of patching doesn't allow to work with `mut`
246 (ty::Array(of_ty_src, ..), ty::Slice(of_ty_dst)) => {
247 if of_ty_src == of_ty_dst {
248 // this is a cast from [T; N] into [T], so we are good
249 state.insert(local, statement_idx);
261 Rvalue::Len(place) => {
262 let Some(local) = place.local_or_deref_local() else {
265 if let Some(cast_statement_idx) = state.get(&local).copied() {
266 patches_scratchpad.insert(cast_statement_idx, statement_idx);
271 state.remove(&place.local);
279 let mut patcher = Patcher {
281 patches_scratchpad: &*patches_scratchpad,
282 replacements_scratchpad,
287 block.expand_statements(|st| patcher.patch_expand_statement(st));