]>
Commit | Line | Data |
---|---|---|
487cf647 FG |
1 | //! A constant propagation optimization pass based on dataflow analysis. |
2 | //! | |
3 | //! Currently, this pass only propagates scalar values. | |
4 | ||
e8be2606 FG |
5 | use rustc_const_eval::const_eval::{throw_machine_stop_str, DummyMachine}; |
6 | use rustc_const_eval::interpret::{ImmTy, Immediate, InterpCx, OpTy, PlaceTy, Projectable}; | |
487cf647 | 7 | use rustc_data_structures::fx::FxHashMap; |
9ffffee4 | 8 | use rustc_hir::def::DefKind; |
e8be2606 | 9 | use rustc_middle::mir::interpret::{InterpResult, Scalar}; |
781aab86 | 10 | use rustc_middle::mir::visit::{MutVisitor, PlaceContext, Visitor}; |
487cf647 | 11 | use rustc_middle::mir::*; |
e8be2606 | 12 | use rustc_middle::ty::layout::LayoutOf; |
487cf647 | 13 | use rustc_middle::ty::{self, Ty, TyCtxt}; |
fe692bf9 | 14 | use rustc_mir_dataflow::value_analysis::{ |
781aab86 | 15 | Map, PlaceIndex, State, TrackElem, ValueAnalysis, ValueAnalysisWrapper, ValueOrPlace, |
fe692bf9 | 16 | }; |
add651ee | 17 | use rustc_mir_dataflow::{lattice::FlatSet, Analysis, Results, ResultsVisitor}; |
487cf647 | 18 | use rustc_span::DUMMY_SP; |
ed00b5ec | 19 | use rustc_target::abi::{Abi, FieldIdx, Size, VariantIdx, FIRST_VARIANT}; |
487cf647 | 20 | |
487cf647 FG |
21 | // These constants are somewhat random guesses and have not been optimized. |
22 | // If `tcx.sess.mir_opt_level() >= 4`, we ignore the limits (this can become very expensive). | |
23 | const BLOCK_LIMIT: usize = 100; | |
24 | const PLACE_LIMIT: usize = 100; | |
25 | ||
26 | pub struct DataflowConstProp; | |
27 | ||
28 | impl<'tcx> MirPass<'tcx> for DataflowConstProp { | |
29 | fn is_enabled(&self, sess: &rustc_session::Session) -> bool { | |
30 | sess.mir_opt_level() >= 3 | |
31 | } | |
32 | ||
33 | #[instrument(skip_all level = "debug")] | |
34 | fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { | |
9ffffee4 | 35 | debug!(def_id = ?body.source.def_id()); |
487cf647 FG |
36 | if tcx.sess.mir_opt_level() < 4 && body.basic_blocks.len() > BLOCK_LIMIT { |
37 | debug!("aborted dataflow const prop due too many basic blocks"); | |
38 | return; | |
39 | } | |
40 | ||
487cf647 FG |
41 | // We want to have a somewhat linear runtime w.r.t. the number of statements/terminators. |
42 | // Let's call this number `n`. Dataflow analysis has `O(h*n)` transfer function | |
43 | // applications, where `h` is the height of the lattice. Because the height of our lattice | |
44 | // is linear w.r.t. the number of tracked places, this is `O(tracked_places * n)`. However, | |
45 | // because every transfer function application could traverse the whole map, this becomes | |
46 | // `O(num_nodes * tracked_places * n)` in terms of time complexity. Since the number of | |
47 | // map nodes is strongly correlated to the number of tracked places, this becomes more or | |
48 | // less `O(n)` if we place a constant limit on the number of tracked places. | |
9ffffee4 FG |
49 | let place_limit = if tcx.sess.mir_opt_level() < 4 { Some(PLACE_LIMIT) } else { None }; |
50 | ||
51 | // Decide which places to track during the analysis. | |
781aab86 | 52 | let map = Map::new(tcx, body, place_limit); |
487cf647 FG |
53 | |
54 | // Perform the actual dataflow analysis. | |
55 | let analysis = ConstAnalysis::new(tcx, body, map); | |
fe692bf9 | 56 | let mut results = debug_span!("analyze") |
487cf647 FG |
57 | .in_scope(|| analysis.wrap().into_engine(tcx, body).iterate_to_fixpoint()); |
58 | ||
59 | // Collect results and patch the body afterwards. | |
781aab86 | 60 | let mut visitor = Collector::new(tcx, &body.local_decls); |
487cf647 | 61 | debug_span!("collect").in_scope(|| results.visit_reachable_with(body, &mut visitor)); |
781aab86 FG |
62 | let mut patch = visitor.patch; |
63 | debug_span!("patch").in_scope(|| patch.visit_body_preserves_cfg(body)); | |
487cf647 FG |
64 | } |
65 | } | |
66 | ||
9ffffee4 | 67 | struct ConstAnalysis<'a, 'tcx> { |
487cf647 FG |
68 | map: Map, |
69 | tcx: TyCtxt<'tcx>, | |
9ffffee4 | 70 | local_decls: &'a LocalDecls<'tcx>, |
487cf647 FG |
71 | ecx: InterpCx<'tcx, 'tcx, DummyMachine>, |
72 | param_env: ty::ParamEnv<'tcx>, | |
73 | } | |
74 | ||
9ffffee4 | 75 | impl<'tcx> ValueAnalysis<'tcx> for ConstAnalysis<'_, 'tcx> { |
781aab86 | 76 | type Value = FlatSet<Scalar>; |
487cf647 FG |
77 | |
78 | const NAME: &'static str = "ConstAnalysis"; | |
79 | ||
80 | fn map(&self) -> &Map { | |
81 | &self.map | |
82 | } | |
83 | ||
49aad941 FG |
84 | fn handle_set_discriminant( |
85 | &self, | |
86 | place: Place<'tcx>, | |
87 | variant_index: VariantIdx, | |
88 | state: &mut State<Self::Value>, | |
89 | ) { | |
90 | state.flood_discr(place.as_ref(), &self.map); | |
91 | if self.map.find_discr(place.as_ref()).is_some() { | |
92 | let enum_ty = place.ty(self.local_decls, self.tcx).ty; | |
93 | if let Some(discr) = self.eval_discriminant(enum_ty, variant_index) { | |
94 | state.assign_discr( | |
95 | place.as_ref(), | |
96 | ValueOrPlace::Value(FlatSet::Elem(discr)), | |
97 | &self.map, | |
98 | ); | |
9ffffee4 | 99 | } |
9ffffee4 FG |
100 | } |
101 | } | |
102 | ||
487cf647 FG |
103 | fn handle_assign( |
104 | &self, | |
105 | target: Place<'tcx>, | |
106 | rvalue: &Rvalue<'tcx>, | |
107 | state: &mut State<Self::Value>, | |
108 | ) { | |
109 | match rvalue { | |
781aab86 FG |
110 | Rvalue::Use(operand) => { |
111 | state.flood(target.as_ref(), self.map()); | |
112 | if let Some(target) = self.map.find(target.as_ref()) { | |
113 | self.assign_operand(state, target, operand); | |
114 | } | |
115 | } | |
116 | Rvalue::CopyForDeref(rhs) => { | |
117 | state.flood(target.as_ref(), self.map()); | |
118 | if let Some(target) = self.map.find(target.as_ref()) { | |
119 | self.assign_operand(state, target, &Operand::Copy(*rhs)); | |
120 | } | |
121 | } | |
9ffffee4 FG |
122 | Rvalue::Aggregate(kind, operands) => { |
123 | // If we assign `target = Enum::Variant#0(operand)`, | |
124 | // we must make sure that all `target as Variant#i` are `Top`. | |
125 | state.flood(target.as_ref(), self.map()); | |
126 | ||
49aad941 FG |
127 | let Some(target_idx) = self.map().find(target.as_ref()) else { return }; |
128 | ||
129 | let (variant_target, variant_index) = match **kind { | |
130 | AggregateKind::Tuple | AggregateKind::Closure(..) => (Some(target_idx), None), | |
131 | AggregateKind::Adt(def_id, variant_index, ..) => { | |
132 | match self.tcx.def_kind(def_id) { | |
133 | DefKind::Struct => (Some(target_idx), None), | |
134 | DefKind::Enum => ( | |
135 | self.map.apply(target_idx, TrackElem::Variant(variant_index)), | |
136 | Some(variant_index), | |
137 | ), | |
138 | _ => return, | |
9ffffee4 FG |
139 | } |
140 | } | |
49aad941 FG |
141 | _ => return, |
142 | }; | |
143 | if let Some(variant_target_idx) = variant_target { | |
144 | for (field_index, operand) in operands.iter().enumerate() { | |
145 | if let Some(field) = self.map().apply( | |
146 | variant_target_idx, | |
147 | TrackElem::Field(FieldIdx::from_usize(field_index)), | |
148 | ) { | |
781aab86 | 149 | self.assign_operand(state, field, operand); |
9ffffee4 FG |
150 | } |
151 | } | |
152 | } | |
49aad941 FG |
153 | if let Some(variant_index) = variant_index |
154 | && let Some(discr_idx) = self.map().apply(target_idx, TrackElem::Discriminant) | |
155 | { | |
156 | // We are assigning the discriminant as part of an aggregate. | |
157 | // This discriminant can only alias a variant field's value if the operand | |
158 | // had an invalid value for that type. | |
159 | // Using invalid values is UB, so we are allowed to perform the assignment | |
160 | // without extra flooding. | |
161 | let enum_ty = target.ty(self.local_decls, self.tcx).ty; | |
162 | if let Some(discr_val) = self.eval_discriminant(enum_ty, variant_index) { | |
163 | state.insert_value_idx(discr_idx, FlatSet::Elem(discr_val), &self.map); | |
164 | } | |
165 | } | |
9ffffee4 | 166 | } |
487cf647 | 167 | Rvalue::CheckedBinaryOp(op, box (left, right)) => { |
9ffffee4 FG |
168 | // Flood everything now, so we can use `insert_value_idx` directly later. |
169 | state.flood(target.as_ref(), self.map()); | |
170 | ||
49aad941 | 171 | let Some(target) = self.map().find(target.as_ref()) else { return }; |
487cf647 | 172 | |
49aad941 FG |
173 | let value_target = self.map().apply(target, TrackElem::Field(0_u32.into())); |
174 | let overflow_target = self.map().apply(target, TrackElem::Field(1_u32.into())); | |
487cf647 FG |
175 | |
176 | if value_target.is_some() || overflow_target.is_some() { | |
177 | let (val, overflow) = self.binary_op(state, *op, left, right); | |
178 | ||
179 | if let Some(value_target) = value_target { | |
9ffffee4 FG |
180 | // We have flooded `target` earlier. |
181 | state.insert_value_idx(value_target, val, self.map()); | |
487cf647 FG |
182 | } |
183 | if let Some(overflow_target) = overflow_target { | |
184 | let overflow = match overflow { | |
185 | FlatSet::Top => FlatSet::Top, | |
781aab86 | 186 | FlatSet::Elem(overflow) => FlatSet::Elem(Scalar::from_bool(overflow)), |
487cf647 FG |
187 | FlatSet::Bottom => FlatSet::Bottom, |
188 | }; | |
9ffffee4 FG |
189 | // We have flooded `target` earlier. |
190 | state.insert_value_idx(overflow_target, overflow, self.map()); | |
487cf647 FG |
191 | } |
192 | } | |
193 | } | |
781aab86 FG |
194 | Rvalue::Cast( |
195 | CastKind::PointerCoercion(ty::adjustment::PointerCoercion::Unsize), | |
196 | operand, | |
197 | _, | |
198 | ) => { | |
199 | let pointer = self.handle_operand(operand, state); | |
200 | state.assign(target.as_ref(), pointer, self.map()); | |
201 | ||
202 | if let Some(target_len) = self.map().find_len(target.as_ref()) | |
203 | && let operand_ty = operand.ty(self.local_decls, self.tcx) | |
204 | && let Some(operand_ty) = operand_ty.builtin_deref(true) | |
205 | && let ty::Array(_, len) = operand_ty.ty.kind() | |
206 | && let Some(len) = Const::Ty(*len).try_eval_scalar_int(self.tcx, self.param_env) | |
207 | { | |
208 | state.insert_value_idx(target_len, FlatSet::Elem(len.into()), self.map()); | |
209 | } | |
210 | } | |
487cf647 FG |
211 | _ => self.super_assign(target, rvalue, state), |
212 | } | |
213 | } | |
214 | ||
215 | fn handle_rvalue( | |
216 | &self, | |
217 | rvalue: &Rvalue<'tcx>, | |
218 | state: &mut State<Self::Value>, | |
219 | ) -> ValueOrPlace<Self::Value> { | |
781aab86 FG |
220 | let val = match rvalue { |
221 | Rvalue::Len(place) => { | |
222 | let place_ty = place.ty(self.local_decls, self.tcx); | |
223 | if let ty::Array(_, len) = place_ty.ty.kind() { | |
224 | Const::Ty(*len) | |
225 | .try_eval_scalar(self.tcx, self.param_env) | |
226 | .map_or(FlatSet::Top, FlatSet::Elem) | |
227 | } else if let [ProjectionElem::Deref] = place.projection[..] { | |
228 | state.get_len(place.local.into(), self.map()) | |
229 | } else { | |
230 | FlatSet::Top | |
487cf647 | 231 | } |
781aab86 FG |
232 | } |
233 | Rvalue::Cast(CastKind::IntToInt | CastKind::IntToFloat, operand, ty) => { | |
234 | let Ok(layout) = self.tcx.layout_of(self.param_env.and(*ty)) else { | |
235 | return ValueOrPlace::Value(FlatSet::Top); | |
236 | }; | |
237 | match self.eval_operand(operand, state) { | |
238 | FlatSet::Elem(op) => self | |
239 | .ecx | |
240 | .int_to_int_or_float(&op, layout) | |
241 | .map_or(FlatSet::Top, |result| self.wrap_immediate(*result)), | |
242 | FlatSet::Bottom => FlatSet::Bottom, | |
243 | FlatSet::Top => FlatSet::Top, | |
244 | } | |
245 | } | |
246 | Rvalue::Cast(CastKind::FloatToInt | CastKind::FloatToFloat, operand, ty) => { | |
247 | let Ok(layout) = self.tcx.layout_of(self.param_env.and(*ty)) else { | |
248 | return ValueOrPlace::Value(FlatSet::Top); | |
249 | }; | |
250 | match self.eval_operand(operand, state) { | |
251 | FlatSet::Elem(op) => self | |
252 | .ecx | |
253 | .float_to_float_or_int(&op, layout) | |
254 | .map_or(FlatSet::Top, |result| self.wrap_immediate(*result)), | |
255 | FlatSet::Bottom => FlatSet::Bottom, | |
256 | FlatSet::Top => FlatSet::Top, | |
257 | } | |
258 | } | |
259 | Rvalue::Cast(CastKind::Transmute, operand, _) => { | |
260 | match self.eval_operand(operand, state) { | |
261 | FlatSet::Elem(op) => self.wrap_immediate(*op), | |
262 | FlatSet::Bottom => FlatSet::Bottom, | |
263 | FlatSet::Top => FlatSet::Top, | |
264 | } | |
265 | } | |
487cf647 FG |
266 | Rvalue::BinaryOp(op, box (left, right)) => { |
267 | // Overflows must be ignored here. | |
268 | let (val, _overflow) = self.binary_op(state, *op, left, right); | |
781aab86 | 269 | val |
487cf647 FG |
270 | } |
271 | Rvalue::UnaryOp(op, operand) => match self.eval_operand(operand, state) { | |
272 | FlatSet::Elem(value) => self | |
273 | .ecx | |
781aab86 FG |
274 | .wrapping_unary_op(*op, &value) |
275 | .map_or(FlatSet::Top, |val| self.wrap_immediate(*val)), | |
276 | FlatSet::Bottom => FlatSet::Bottom, | |
277 | FlatSet::Top => FlatSet::Top, | |
487cf647 | 278 | }, |
781aab86 FG |
279 | Rvalue::NullaryOp(null_op, ty) => { |
280 | let Ok(layout) = self.tcx.layout_of(self.param_env.and(*ty)) else { | |
281 | return ValueOrPlace::Value(FlatSet::Top); | |
282 | }; | |
283 | let val = match null_op { | |
284 | NullOp::SizeOf if layout.is_sized() => layout.size.bytes(), | |
285 | NullOp::AlignOf if layout.is_sized() => layout.align.abi.bytes(), | |
ed00b5ec FG |
286 | NullOp::OffsetOf(fields) => { |
287 | layout.offset_of_subfield(&self.ecx, fields.iter()).bytes() | |
288 | } | |
781aab86 FG |
289 | _ => return ValueOrPlace::Value(FlatSet::Top), |
290 | }; | |
291 | FlatSet::Elem(Scalar::from_target_usize(val, &self.tcx)) | |
9ffffee4 | 292 | } |
781aab86 FG |
293 | Rvalue::Discriminant(place) => state.get_discr(place.as_ref(), self.map()), |
294 | _ => return self.super_rvalue(rvalue, state), | |
295 | }; | |
296 | ValueOrPlace::Value(val) | |
487cf647 FG |
297 | } |
298 | ||
299 | fn handle_constant( | |
300 | &self, | |
781aab86 | 301 | constant: &ConstOperand<'tcx>, |
487cf647 FG |
302 | _state: &mut State<Self::Value>, |
303 | ) -> Self::Value { | |
304 | constant | |
781aab86 FG |
305 | .const_ |
306 | .try_eval_scalar(self.tcx, self.param_env) | |
307 | .map_or(FlatSet::Top, FlatSet::Elem) | |
487cf647 FG |
308 | } |
309 | ||
add651ee | 310 | fn handle_switch_int<'mir>( |
487cf647 | 311 | &self, |
add651ee FG |
312 | discr: &'mir Operand<'tcx>, |
313 | targets: &'mir SwitchTargets, | |
314 | state: &mut State<Self::Value>, | |
315 | ) -> TerminatorEdges<'mir, 'tcx> { | |
316 | let value = match self.handle_operand(discr, state) { | |
317 | ValueOrPlace::Value(value) => value, | |
318 | ValueOrPlace::Place(place) => state.get_idx(place, self.map()), | |
319 | }; | |
320 | match value { | |
321 | // We are branching on uninitialized data, this is UB, treat it as unreachable. | |
322 | // This allows the set of visited edges to grow monotonically with the lattice. | |
323 | FlatSet::Bottom => TerminatorEdges::None, | |
781aab86 FG |
324 | FlatSet::Elem(scalar) => { |
325 | let choice = scalar.assert_bits(scalar.size()); | |
add651ee | 326 | TerminatorEdges::Single(targets.target_for_value(choice)) |
487cf647 | 327 | } |
add651ee FG |
328 | FlatSet::Top => TerminatorEdges::SwitchInt { discr, targets }, |
329 | } | |
487cf647 FG |
330 | } |
331 | } | |
332 | ||
9ffffee4 FG |
333 | impl<'a, 'tcx> ConstAnalysis<'a, 'tcx> { |
334 | pub fn new(tcx: TyCtxt<'tcx>, body: &'a Body<'tcx>, map: Map) -> Self { | |
49aad941 | 335 | let param_env = tcx.param_env_reveal_all_normalized(body.source.def_id()); |
487cf647 FG |
336 | Self { |
337 | map, | |
338 | tcx, | |
9ffffee4 | 339 | local_decls: &body.local_decls, |
487cf647 FG |
340 | ecx: InterpCx::new(tcx, DUMMY_SP, param_env, DummyMachine), |
341 | param_env: param_env, | |
342 | } | |
343 | } | |
344 | ||
781aab86 FG |
345 | /// The caller must have flooded `place`. |
346 | fn assign_operand( | |
347 | &self, | |
348 | state: &mut State<FlatSet<Scalar>>, | |
349 | place: PlaceIndex, | |
350 | operand: &Operand<'tcx>, | |
351 | ) { | |
352 | match operand { | |
353 | Operand::Copy(rhs) | Operand::Move(rhs) => { | |
354 | if let Some(rhs) = self.map.find(rhs.as_ref()) { | |
355 | state.insert_place_idx(place, rhs, &self.map); | |
356 | } else if rhs.projection.first() == Some(&PlaceElem::Deref) | |
357 | && let FlatSet::Elem(pointer) = state.get(rhs.local.into(), &self.map) | |
358 | && let rhs_ty = self.local_decls[rhs.local].ty | |
359 | && let Ok(rhs_layout) = self.tcx.layout_of(self.param_env.and(rhs_ty)) | |
360 | { | |
361 | let op = ImmTy::from_scalar(pointer, rhs_layout).into(); | |
4b012472 | 362 | self.assign_constant(state, place, op, rhs.projection); |
781aab86 FG |
363 | } |
364 | } | |
365 | Operand::Constant(box constant) => { | |
c620b35d | 366 | if let Ok(constant) = |
e8be2606 | 367 | self.ecx.eval_mir_constant(&constant.const_, constant.span, None) |
c620b35d | 368 | { |
781aab86 FG |
369 | self.assign_constant(state, place, constant, &[]); |
370 | } | |
371 | } | |
372 | } | |
373 | } | |
374 | ||
375 | /// The caller must have flooded `place`. | |
376 | /// | |
377 | /// Perform: `place = operand.projection`. | |
378 | #[instrument(level = "trace", skip(self, state))] | |
379 | fn assign_constant( | |
380 | &self, | |
381 | state: &mut State<FlatSet<Scalar>>, | |
382 | place: PlaceIndex, | |
383 | mut operand: OpTy<'tcx>, | |
384 | projection: &[PlaceElem<'tcx>], | |
385 | ) -> Option<!> { | |
386 | for &(mut proj_elem) in projection { | |
387 | if let PlaceElem::Index(index) = proj_elem { | |
388 | if let FlatSet::Elem(index) = state.get(index.into(), &self.map) | |
389 | && let Ok(offset) = index.to_target_usize(&self.tcx) | |
390 | && let Some(min_length) = offset.checked_add(1) | |
391 | { | |
392 | proj_elem = PlaceElem::ConstantIndex { offset, min_length, from_end: false }; | |
393 | } else { | |
394 | return None; | |
395 | } | |
396 | } | |
397 | operand = self.ecx.project(&operand, proj_elem).ok()?; | |
398 | } | |
399 | ||
400 | self.map.for_each_projection_value( | |
401 | place, | |
402 | operand, | |
403 | &mut |elem, op| match elem { | |
404 | TrackElem::Field(idx) => self.ecx.project_field(op, idx.as_usize()).ok(), | |
405 | TrackElem::Variant(idx) => self.ecx.project_downcast(op, idx).ok(), | |
406 | TrackElem::Discriminant => { | |
407 | let variant = self.ecx.read_discriminant(op).ok()?; | |
ed00b5ec FG |
408 | let discr_value = |
409 | self.ecx.discriminant_for_variant(op.layout.ty, variant).ok()?; | |
781aab86 FG |
410 | Some(discr_value.into()) |
411 | } | |
412 | TrackElem::DerefLen => { | |
413 | let op: OpTy<'_> = self.ecx.deref_pointer(op).ok()?.into(); | |
414 | let len_usize = op.len(&self.ecx).ok()?; | |
415 | let layout = | |
416 | self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).unwrap(); | |
417 | Some(ImmTy::from_uint(len_usize, layout).into()) | |
418 | } | |
419 | }, | |
420 | &mut |place, op| { | |
421 | if let Ok(imm) = self.ecx.read_immediate_raw(op) | |
422 | && let Some(imm) = imm.right() | |
423 | { | |
424 | let elem = self.wrap_immediate(*imm); | |
425 | state.insert_value_idx(place, elem, &self.map); | |
426 | } | |
427 | }, | |
428 | ); | |
429 | ||
430 | None | |
431 | } | |
432 | ||
487cf647 FG |
433 | fn binary_op( |
434 | &self, | |
781aab86 | 435 | state: &mut State<FlatSet<Scalar>>, |
487cf647 FG |
436 | op: BinOp, |
437 | left: &Operand<'tcx>, | |
438 | right: &Operand<'tcx>, | |
781aab86 | 439 | ) -> (FlatSet<Scalar>, FlatSet<bool>) { |
487cf647 FG |
440 | let left = self.eval_operand(left, state); |
441 | let right = self.eval_operand(right, state); | |
781aab86 | 442 | |
487cf647 | 443 | match (left, right) { |
781aab86 FG |
444 | (FlatSet::Bottom, _) | (_, FlatSet::Bottom) => (FlatSet::Bottom, FlatSet::Bottom), |
445 | // Both sides are known, do the actual computation. | |
487cf647 FG |
446 | (FlatSet::Elem(left), FlatSet::Elem(right)) => { |
447 | match self.ecx.overflowing_binary_op(op, &left, &right) { | |
781aab86 FG |
448 | Ok((val, overflow)) => { |
449 | (FlatSet::Elem(val.to_scalar()), FlatSet::Elem(overflow)) | |
450 | } | |
487cf647 FG |
451 | _ => (FlatSet::Top, FlatSet::Top), |
452 | } | |
453 | } | |
781aab86 FG |
454 | // Exactly one side is known, attempt some algebraic simplifications. |
455 | (FlatSet::Elem(const_arg), _) | (_, FlatSet::Elem(const_arg)) => { | |
456 | let layout = const_arg.layout; | |
457 | if !matches!(layout.abi, rustc_target::abi::Abi::Scalar(..)) { | |
458 | return (FlatSet::Top, FlatSet::Top); | |
459 | } | |
460 | ||
461 | let arg_scalar = const_arg.to_scalar(); | |
462 | let Ok(arg_value) = arg_scalar.to_bits(layout.size) else { | |
463 | return (FlatSet::Top, FlatSet::Top); | |
464 | }; | |
465 | ||
466 | match op { | |
467 | BinOp::BitAnd if arg_value == 0 => (FlatSet::Elem(arg_scalar), FlatSet::Bottom), | |
468 | BinOp::BitOr | |
469 | if arg_value == layout.size.truncate(u128::MAX) | |
470 | || (layout.ty.is_bool() && arg_value == 1) => | |
471 | { | |
472 | (FlatSet::Elem(arg_scalar), FlatSet::Bottom) | |
473 | } | |
474 | BinOp::Mul if layout.ty.is_integral() && arg_value == 0 => { | |
475 | (FlatSet::Elem(arg_scalar), FlatSet::Elem(false)) | |
476 | } | |
477 | _ => (FlatSet::Top, FlatSet::Top), | |
478 | } | |
487cf647 | 479 | } |
781aab86 | 480 | (FlatSet::Top, FlatSet::Top) => (FlatSet::Top, FlatSet::Top), |
487cf647 FG |
481 | } |
482 | } | |
483 | ||
484 | fn eval_operand( | |
485 | &self, | |
486 | op: &Operand<'tcx>, | |
781aab86 | 487 | state: &mut State<FlatSet<Scalar>>, |
487cf647 FG |
488 | ) -> FlatSet<ImmTy<'tcx>> { |
489 | let value = match self.handle_operand(op, state) { | |
490 | ValueOrPlace::Value(value) => value, | |
491 | ValueOrPlace::Place(place) => state.get_idx(place, &self.map), | |
492 | }; | |
493 | match value { | |
494 | FlatSet::Top => FlatSet::Top, | |
781aab86 FG |
495 | FlatSet::Elem(scalar) => { |
496 | let ty = op.ty(self.local_decls, self.tcx); | |
497 | self.tcx.layout_of(self.param_env.and(ty)).map_or(FlatSet::Top, |layout| { | |
4b012472 | 498 | FlatSet::Elem(ImmTy::from_scalar(scalar, layout)) |
781aab86 FG |
499 | }) |
500 | } | |
487cf647 FG |
501 | FlatSet::Bottom => FlatSet::Bottom, |
502 | } | |
503 | } | |
504 | ||
781aab86 | 505 | fn eval_discriminant(&self, enum_ty: Ty<'tcx>, variant_index: VariantIdx) -> Option<Scalar> { |
49aad941 FG |
506 | if !enum_ty.is_enum() { |
507 | return None; | |
508 | } | |
781aab86 | 509 | let enum_ty_layout = self.tcx.layout_of(self.param_env.and(enum_ty)).ok()?; |
ed00b5ec FG |
510 | let discr_value = |
511 | self.ecx.discriminant_for_variant(enum_ty_layout.ty, variant_index).ok()?; | |
781aab86 | 512 | Some(discr_value.to_scalar()) |
487cf647 FG |
513 | } |
514 | ||
781aab86 | 515 | fn wrap_immediate(&self, imm: Immediate) -> FlatSet<Scalar> { |
487cf647 | 516 | match imm { |
781aab86 FG |
517 | Immediate::Scalar(scalar) => FlatSet::Elem(scalar), |
518 | Immediate::Uninit => FlatSet::Bottom, | |
487cf647 FG |
519 | _ => FlatSet::Top, |
520 | } | |
521 | } | |
487cf647 FG |
522 | } |
523 | ||
781aab86 | 524 | pub(crate) struct Patch<'tcx> { |
487cf647 | 525 | tcx: TyCtxt<'tcx>, |
487cf647 FG |
526 | |
527 | /// For a given MIR location, this stores the values of the operands used by that location. In | |
528 | /// particular, this is before the effect, such that the operands of `_1 = _1 + _2` are | |
529 | /// properly captured. (This may become UB soon, but it is currently emitted even by safe code.) | |
781aab86 | 530 | pub(crate) before_effect: FxHashMap<(Location, Place<'tcx>), Const<'tcx>>, |
487cf647 FG |
531 | |
532 | /// Stores the assigned values for assignments where the Rvalue is constant. | |
781aab86 | 533 | pub(crate) assignments: FxHashMap<Location, Const<'tcx>>, |
487cf647 FG |
534 | } |
535 | ||
781aab86 FG |
536 | impl<'tcx> Patch<'tcx> { |
537 | pub(crate) fn new(tcx: TyCtxt<'tcx>) -> Self { | |
fe692bf9 | 538 | Self { tcx, before_effect: FxHashMap::default(), assignments: FxHashMap::default() } |
487cf647 FG |
539 | } |
540 | ||
781aab86 FG |
541 | fn make_operand(&self, const_: Const<'tcx>) -> Operand<'tcx> { |
542 | Operand::Constant(Box::new(ConstOperand { span: DUMMY_SP, user_ty: None, const_ })) | |
543 | } | |
544 | } | |
545 | ||
546 | struct Collector<'tcx, 'locals> { | |
547 | patch: Patch<'tcx>, | |
548 | local_decls: &'locals LocalDecls<'tcx>, | |
549 | } | |
550 | ||
551 | impl<'tcx, 'locals> Collector<'tcx, 'locals> { | |
552 | pub(crate) fn new(tcx: TyCtxt<'tcx>, local_decls: &'locals LocalDecls<'tcx>) -> Self { | |
553 | Self { patch: Patch::new(tcx), local_decls } | |
554 | } | |
555 | ||
556 | fn try_make_constant( | |
557 | &self, | |
ed00b5ec | 558 | ecx: &mut InterpCx<'tcx, 'tcx, DummyMachine>, |
781aab86 FG |
559 | place: Place<'tcx>, |
560 | state: &State<FlatSet<Scalar>>, | |
561 | map: &Map, | |
562 | ) -> Option<Const<'tcx>> { | |
781aab86 | 563 | let ty = place.ty(self.local_decls, self.patch.tcx).ty; |
ed00b5ec FG |
564 | let layout = ecx.layout_of(ty).ok()?; |
565 | ||
566 | if layout.is_zst() { | |
567 | return Some(Const::zero_sized(ty)); | |
568 | } | |
569 | ||
570 | if layout.is_unsized() { | |
571 | return None; | |
572 | } | |
573 | ||
574 | let place = map.find(place.as_ref())?; | |
575 | if layout.abi.is_scalar() | |
576 | && let Some(value) = propagatable_scalar(place, state, map) | |
577 | { | |
578 | return Some(Const::Val(ConstValue::Scalar(value), ty)); | |
579 | } | |
580 | ||
581 | if matches!(layout.abi, Abi::Scalar(..) | Abi::ScalarPair(..)) { | |
582 | let alloc_id = ecx | |
583 | .intern_with_temp_alloc(layout, |ecx, dest| { | |
584 | try_write_constant(ecx, dest, place, ty, state, map) | |
585 | }) | |
586 | .ok()?; | |
587 | return Some(Const::Val(ConstValue::Indirect { alloc_id, offset: Size::ZERO }, ty)); | |
588 | } | |
589 | ||
590 | None | |
591 | } | |
592 | } | |
593 | ||
594 | fn propagatable_scalar( | |
595 | place: PlaceIndex, | |
596 | state: &State<FlatSet<Scalar>>, | |
597 | map: &Map, | |
598 | ) -> Option<Scalar> { | |
4b012472 FG |
599 | if let FlatSet::Elem(value) = state.get_idx(place, map) |
600 | && value.try_to_int().is_ok() | |
601 | { | |
ed00b5ec FG |
602 | // Do not attempt to propagate pointers, as we may fail to preserve their identity. |
603 | Some(value) | |
604 | } else { | |
605 | None | |
606 | } | |
607 | } | |
608 | ||
609 | #[instrument(level = "trace", skip(ecx, state, map))] | |
610 | fn try_write_constant<'tcx>( | |
611 | ecx: &mut InterpCx<'_, 'tcx, DummyMachine>, | |
612 | dest: &PlaceTy<'tcx>, | |
613 | place: PlaceIndex, | |
614 | ty: Ty<'tcx>, | |
615 | state: &State<FlatSet<Scalar>>, | |
616 | map: &Map, | |
617 | ) -> InterpResult<'tcx> { | |
618 | let layout = ecx.layout_of(ty)?; | |
619 | ||
620 | // Fast path for ZSTs. | |
621 | if layout.is_zst() { | |
622 | return Ok(()); | |
623 | } | |
624 | ||
625 | // Fast path for scalars. | |
626 | if layout.abi.is_scalar() | |
627 | && let Some(value) = propagatable_scalar(place, state, map) | |
628 | { | |
629 | return ecx.write_immediate(Immediate::Scalar(value), dest); | |
630 | } | |
631 | ||
632 | match ty.kind() { | |
633 | // ZSTs. Nothing to do. | |
634 | ty::FnDef(..) => {} | |
635 | ||
636 | // Those are scalars, must be handled above. | |
637 | ty::Bool | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Char => throw_machine_stop_str!("primitive type with provenance"), | |
638 | ||
639 | ty::Tuple(elem_tys) => { | |
640 | for (i, elem) in elem_tys.iter().enumerate() { | |
641 | let Some(field) = map.apply(place, TrackElem::Field(FieldIdx::from_usize(i))) else { | |
642 | throw_machine_stop_str!("missing field in tuple") | |
643 | }; | |
644 | let field_dest = ecx.project_field(dest, i)?; | |
645 | try_write_constant(ecx, &field_dest, field, elem, state, map)?; | |
646 | } | |
647 | } | |
648 | ||
649 | ty::Adt(def, args) => { | |
650 | if def.is_union() { | |
651 | throw_machine_stop_str!("cannot propagate unions") | |
652 | } | |
653 | ||
654 | let (variant_idx, variant_def, variant_place, variant_dest) = if def.is_enum() { | |
655 | let Some(discr) = map.apply(place, TrackElem::Discriminant) else { | |
656 | throw_machine_stop_str!("missing discriminant for enum") | |
657 | }; | |
658 | let FlatSet::Elem(Scalar::Int(discr)) = state.get_idx(discr, map) else { | |
659 | throw_machine_stop_str!("discriminant with provenance") | |
660 | }; | |
661 | let discr_bits = discr.assert_bits(discr.size()); | |
662 | let Some((variant, _)) = def.discriminants(*ecx.tcx).find(|(_, var)| discr_bits == var.val) else { | |
663 | throw_machine_stop_str!("illegal discriminant for enum") | |
664 | }; | |
665 | let Some(variant_place) = map.apply(place, TrackElem::Variant(variant)) else { | |
666 | throw_machine_stop_str!("missing variant for enum") | |
667 | }; | |
668 | let variant_dest = ecx.project_downcast(dest, variant)?; | |
669 | (variant, def.variant(variant), variant_place, variant_dest) | |
670 | } else { | |
671 | (FIRST_VARIANT, def.non_enum_variant(), place, dest.clone()) | |
672 | }; | |
673 | ||
674 | for (i, field) in variant_def.fields.iter_enumerated() { | |
675 | let ty = field.ty(*ecx.tcx, args); | |
676 | let Some(field) = map.apply(variant_place, TrackElem::Field(i)) else { | |
677 | throw_machine_stop_str!("missing field in ADT") | |
678 | }; | |
679 | let field_dest = ecx.project_field(&variant_dest, i.as_usize())?; | |
680 | try_write_constant(ecx, &field_dest, field, ty, state, map)?; | |
681 | } | |
682 | ecx.write_discriminant(variant_idx, dest)?; | |
683 | } | |
684 | ||
685 | // Unsupported for now. | |
686 | ty::Array(_, _) | |
e8be2606 | 687 | | ty::Pat(_, _) |
ed00b5ec FG |
688 | |
689 | // Do not attempt to support indirection in constants. | |
690 | | ty::Ref(..) | ty::RawPtr(..) | ty::FnPtr(..) | ty::Str | ty::Slice(_) | |
691 | ||
692 | | ty::Never | |
693 | | ty::Foreign(..) | |
694 | | ty::Alias(..) | |
695 | | ty::Param(_) | |
696 | | ty::Bound(..) | |
697 | | ty::Placeholder(..) | |
698 | | ty::Closure(..) | |
c620b35d | 699 | | ty::CoroutineClosure(..) |
ed00b5ec FG |
700 | | ty::Coroutine(..) |
701 | | ty::Dynamic(..) => throw_machine_stop_str!("unsupported type"), | |
702 | ||
703 | ty::Error(_) | ty::Infer(..) | ty::CoroutineWitness(..) => bug!(), | |
487cf647 | 704 | } |
ed00b5ec FG |
705 | |
706 | Ok(()) | |
487cf647 FG |
707 | } |
708 | ||
fe692bf9 FG |
709 | impl<'mir, 'tcx> |
710 | ResultsVisitor<'mir, 'tcx, Results<'tcx, ValueAnalysisWrapper<ConstAnalysis<'_, 'tcx>>>> | |
781aab86 | 711 | for Collector<'tcx, '_> |
fe692bf9 | 712 | { |
781aab86 | 713 | type FlowState = State<FlatSet<Scalar>>; |
487cf647 FG |
714 | |
715 | fn visit_statement_before_primary_effect( | |
716 | &mut self, | |
781aab86 | 717 | results: &mut Results<'tcx, ValueAnalysisWrapper<ConstAnalysis<'_, 'tcx>>>, |
487cf647 FG |
718 | state: &Self::FlowState, |
719 | statement: &'mir Statement<'tcx>, | |
720 | location: Location, | |
721 | ) { | |
722 | match &statement.kind { | |
723 | StatementKind::Assign(box (_, rvalue)) => { | |
ed00b5ec FG |
724 | OperandCollector { |
725 | state, | |
726 | visitor: self, | |
727 | ecx: &mut results.analysis.0.ecx, | |
728 | map: &results.analysis.0.map, | |
729 | } | |
730 | .visit_rvalue(rvalue, location); | |
487cf647 FG |
731 | } |
732 | _ => (), | |
733 | } | |
734 | } | |
735 | ||
736 | fn visit_statement_after_primary_effect( | |
737 | &mut self, | |
781aab86 | 738 | results: &mut Results<'tcx, ValueAnalysisWrapper<ConstAnalysis<'_, 'tcx>>>, |
487cf647 FG |
739 | state: &Self::FlowState, |
740 | statement: &'mir Statement<'tcx>, | |
741 | location: Location, | |
742 | ) { | |
743 | match statement.kind { | |
744 | StatementKind::Assign(box (_, Rvalue::Use(Operand::Constant(_)))) => { | |
745 | // Don't overwrite the assignment if it already uses a constant (to keep the span). | |
746 | } | |
fe692bf9 | 747 | StatementKind::Assign(box (place, _)) => { |
ed00b5ec FG |
748 | if let Some(value) = self.try_make_constant( |
749 | &mut results.analysis.0.ecx, | |
750 | place, | |
751 | state, | |
752 | &results.analysis.0.map, | |
753 | ) { | |
781aab86 | 754 | self.patch.assignments.insert(location, value); |
487cf647 | 755 | } |
fe692bf9 | 756 | } |
487cf647 FG |
757 | _ => (), |
758 | } | |
759 | } | |
760 | ||
761 | fn visit_terminator_before_primary_effect( | |
762 | &mut self, | |
781aab86 | 763 | results: &mut Results<'tcx, ValueAnalysisWrapper<ConstAnalysis<'_, 'tcx>>>, |
487cf647 FG |
764 | state: &Self::FlowState, |
765 | terminator: &'mir Terminator<'tcx>, | |
766 | location: Location, | |
767 | ) { | |
ed00b5ec FG |
768 | OperandCollector { |
769 | state, | |
770 | visitor: self, | |
771 | ecx: &mut results.analysis.0.ecx, | |
772 | map: &results.analysis.0.map, | |
773 | } | |
774 | .visit_terminator(terminator, location); | |
487cf647 FG |
775 | } |
776 | } | |
777 | ||
781aab86 FG |
778 | impl<'tcx> MutVisitor<'tcx> for Patch<'tcx> { |
779 | fn tcx(&self) -> TyCtxt<'tcx> { | |
487cf647 FG |
780 | self.tcx |
781 | } | |
782 | ||
783 | fn visit_statement(&mut self, statement: &mut Statement<'tcx>, location: Location) { | |
784 | if let Some(value) = self.assignments.get(&location) { | |
785 | match &mut statement.kind { | |
786 | StatementKind::Assign(box (_, rvalue)) => { | |
781aab86 | 787 | *rvalue = Rvalue::Use(self.make_operand(*value)); |
487cf647 FG |
788 | } |
789 | _ => bug!("found assignment info for non-assign statement"), | |
790 | } | |
791 | } else { | |
792 | self.super_statement(statement, location); | |
793 | } | |
794 | } | |
795 | ||
796 | fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) { | |
797 | match operand { | |
798 | Operand::Copy(place) | Operand::Move(place) => { | |
799 | if let Some(value) = self.before_effect.get(&(location, *place)) { | |
781aab86 FG |
800 | *operand = self.make_operand(*value); |
801 | } else if !place.projection.is_empty() { | |
802 | self.super_operand(operand, location) | |
487cf647 FG |
803 | } |
804 | } | |
781aab86 FG |
805 | Operand::Constant(_) => {} |
806 | } | |
807 | } | |
808 | ||
809 | fn process_projection_elem( | |
810 | &mut self, | |
811 | elem: PlaceElem<'tcx>, | |
812 | location: Location, | |
813 | ) -> Option<PlaceElem<'tcx>> { | |
814 | if let PlaceElem::Index(local) = elem { | |
815 | let offset = self.before_effect.get(&(location, local.into()))?; | |
816 | let offset = offset.try_to_scalar()?; | |
817 | let offset = offset.to_target_usize(&self.tcx).ok()?; | |
818 | let min_length = offset.checked_add(1)?; | |
819 | Some(PlaceElem::ConstantIndex { offset, min_length, from_end: false }) | |
820 | } else { | |
821 | None | |
487cf647 FG |
822 | } |
823 | } | |
824 | } | |
825 | ||
781aab86 FG |
826 | struct OperandCollector<'tcx, 'map, 'locals, 'a> { |
827 | state: &'a State<FlatSet<Scalar>>, | |
828 | visitor: &'a mut Collector<'tcx, 'locals>, | |
ed00b5ec | 829 | ecx: &'map mut InterpCx<'tcx, 'tcx, DummyMachine>, |
fe692bf9 | 830 | map: &'map Map, |
487cf647 FG |
831 | } |
832 | ||
781aab86 FG |
833 | impl<'tcx> Visitor<'tcx> for OperandCollector<'tcx, '_, '_, '_> { |
834 | fn visit_projection_elem( | |
835 | &mut self, | |
836 | _: PlaceRef<'tcx>, | |
837 | elem: PlaceElem<'tcx>, | |
838 | _: PlaceContext, | |
839 | location: Location, | |
840 | ) { | |
841 | if let PlaceElem::Index(local) = elem | |
4b012472 FG |
842 | && let Some(value) = |
843 | self.visitor.try_make_constant(self.ecx, local.into(), self.state, self.map) | |
781aab86 FG |
844 | { |
845 | self.visitor.patch.before_effect.insert((location, local.into()), value); | |
846 | } | |
847 | } | |
848 | ||
487cf647 | 849 | fn visit_operand(&mut self, operand: &Operand<'tcx>, location: Location) { |
781aab86 | 850 | if let Some(place) = operand.place() { |
ed00b5ec FG |
851 | if let Some(value) = |
852 | self.visitor.try_make_constant(self.ecx, place, self.state, self.map) | |
853 | { | |
781aab86 FG |
854 | self.visitor.patch.before_effect.insert((location, place), value); |
855 | } else if !place.projection.is_empty() { | |
856 | // Try to propagate into `Index` projections. | |
857 | self.super_operand(operand, location) | |
487cf647 | 858 | } |
487cf647 FG |
859 | } |
860 | } | |
861 | } |