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 {
19 sess.mir_opt_level() >= 4
22 fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
23 // early returns for edge cases of highly unrolled functions
24 if body.basic_blocks.len() > MAX_NUM_BLOCKS {
27 if body.local_decls.len() > MAX_NUM_LOCALS {
30 normalize_array_len_calls(tcx, body)
34 pub fn normalize_array_len_calls<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
35 // We don't ever touch terminators, so no need to invalidate the CFG cache
36 let basic_blocks = body.basic_blocks.as_mut_preserves_cfg();
37 let local_decls = &mut body.local_decls;
39 // do a preliminary analysis to see if we ever have locals of type `[T;N]` or `&[T;N]`
40 let mut interesting_locals = BitSet::new_empty(local_decls.len());
41 for (local, decl) in local_decls.iter_enumerated() {
42 match decl.ty.kind() {
44 interesting_locals.insert(local);
46 ty::Ref(.., ty, Mutability::Not) => match ty.kind() {
48 interesting_locals.insert(local);
55 if interesting_locals.is_empty() {
56 // we have found nothing to analyze
59 let num_intesting_locals = interesting_locals.count();
60 let mut state = FxIndexMap::with_capacity_and_hasher(num_intesting_locals, Default::default());
61 let mut patches_scratchpad =
62 FxIndexMap::with_capacity_and_hasher(num_intesting_locals, Default::default());
63 let mut replacements_scratchpad =
64 FxIndexMap::with_capacity_and_hasher(num_intesting_locals, Default::default());
65 for block in basic_blocks {
66 // make length calls for arrays [T; N] not to decay into length calls for &[T]
67 // that forbids constant propagation
68 normalize_array_len_call(
74 &mut patches_scratchpad,
75 &mut replacements_scratchpad,
78 patches_scratchpad.clear();
79 replacements_scratchpad.clear();
83 struct Patcher<'a, 'tcx> {
85 patches_scratchpad: &'a FxIndexMap<usize, usize>,
86 replacements_scratchpad: &'a mut FxIndexMap<usize, Local>,
87 local_decls: &'a mut IndexVec<Local, LocalDecl<'tcx>>,
91 impl<'tcx> Patcher<'_, 'tcx> {
92 fn patch_expand_statement(
94 statement: &mut Statement<'tcx>,
95 ) -> Option<std::vec::IntoIter<Statement<'tcx>>> {
96 let idx = self.statement_idx;
97 if let Some(len_statemnt_idx) = self.patches_scratchpad.get(&idx).copied() {
98 let mut statements = Vec::with_capacity(2);
100 // we are at statement that performs a cast. The only sound way is
101 // to create another local that performs a similar copy without a cast and then
102 // use this copy in the Len operation
104 match &statement.kind {
105 StatementKind::Assign(box (
108 CastKind::Pointer(ty::adjustment::PointerCast::Unsize),
114 Operand::Copy(place) | Operand::Move(place) => {
116 let ty = operand.ty(self.local_decls, self.tcx);
117 let local_decl = LocalDecl::with_source_info(ty, statement.source_info);
118 let local = self.local_decls.push(local_decl);
120 let mut make_live_statement = statement.clone();
121 make_live_statement.kind = StatementKind::StorageLive(local);
122 statements.push(make_live_statement);
125 let operand = Operand::Copy(*place);
126 let mut make_copy_statement = statement.clone();
127 let assign_to = Place::from(local);
128 let rvalue = Rvalue::Use(operand);
129 make_copy_statement.kind =
130 StatementKind::Assign(Box::new((assign_to, rvalue)));
131 statements.push(make_copy_statement);
133 // to reorder we have to copy and make NOP
134 statements.push(statement.clone());
135 statement.make_nop();
137 self.replacements_scratchpad.insert(len_statemnt_idx, local);
140 unreachable!("it's a bug in the implementation")
145 unreachable!("it's a bug in the implementation")
149 self.statement_idx += 1;
151 Some(statements.into_iter())
152 } else if let Some(local) = self.replacements_scratchpad.get(&idx).copied() {
153 let mut statements = Vec::with_capacity(2);
155 match &statement.kind {
156 StatementKind::Assign(box (into, Rvalue::Len(place))) => {
157 let add_deref = if let Some(..) = place.as_local() {
159 } else if let Some(..) = place.local_or_deref_local() {
162 unreachable!("it's a bug in the implementation")
164 // replace len statement
165 let mut len_statement = statement.clone();
166 let mut place = Place::from(local);
168 place = self.tcx.mk_place_deref(place);
171 StatementKind::Assign(Box::new((*into, Rvalue::Len(place))));
172 statements.push(len_statement);
174 // make temporary dead
175 let mut make_dead_statement = statement.clone();
176 make_dead_statement.kind = StatementKind::StorageDead(local);
177 statements.push(make_dead_statement);
179 // make original statement NOP
180 statement.make_nop();
183 unreachable!("it's a bug in the implementation")
187 self.statement_idx += 1;
189 Some(statements.into_iter())
191 self.statement_idx += 1;
197 fn normalize_array_len_call<'tcx>(
199 block: &mut BasicBlockData<'tcx>,
200 local_decls: &mut IndexVec<Local, LocalDecl<'tcx>>,
201 interesting_locals: &BitSet<Local>,
202 state: &mut FxIndexMap<Local, usize>,
203 patches_scratchpad: &mut FxIndexMap<usize, usize>,
204 replacements_scratchpad: &mut FxIndexMap<usize, Local>,
206 for (statement_idx, statement) in block.statements.iter_mut().enumerate() {
207 match &mut statement.kind {
208 StatementKind::Assign(box (place, rvalue)) => {
211 CastKind::Pointer(ty::adjustment::PointerCast::Unsize),
215 let Some(local) = place.as_local() else { return };
217 Operand::Copy(place) | Operand::Move(place) => {
218 let Some(operand_local) = place.local_or_deref_local() else { return; };
219 if !interesting_locals.contains(operand_local) {
222 let operand_ty = local_decls[operand_local].ty;
223 match (operand_ty.kind(), cast_ty.kind()) {
224 (ty::Array(of_ty_src, ..), ty::Slice(of_ty_dst)) => {
225 if of_ty_src == of_ty_dst {
226 // this is a cast from [T; N] into [T], so we are good
227 state.insert(local, statement_idx);
230 // current way of patching doesn't allow to work with `mut`
233 Region(Interned(ReErased, _)),
238 Region(Interned(ReErased, _)),
243 match (operand_ty.kind(), cast_ty.kind()) {
244 // current way of patching doesn't allow to work with `mut`
245 (ty::Array(of_ty_src, ..), ty::Slice(of_ty_dst)) => {
246 if of_ty_src == of_ty_dst {
247 // this is a cast from [T; N] into [T], so we are good
248 state.insert(local, statement_idx);
260 Rvalue::Len(place) => {
261 let Some(local) = place.local_or_deref_local() else {
264 if let Some(cast_statement_idx) = state.get(&local).copied() {
265 patches_scratchpad.insert(cast_statement_idx, statement_idx);
270 state.remove(&place.local);
278 let mut patcher = Patcher {
280 patches_scratchpad: &*patches_scratchpad,
281 replacements_scratchpad,
286 block.expand_statements(|st| patcher.patch_expand_statement(st));