]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
1 | //! Polymorphization Analysis |
2 | //! ========================= | |
3 | //! | |
4 | //! This module implements an analysis of functions, methods and closures to determine which | |
5 | //! generic parameters are unused (and eventually, in what ways generic parameters are used - only | |
6 | //! for their size, offset of a field, etc.). | |
7 | ||
5869c6ff | 8 | use rustc_hir::{def::DefKind, def_id::DefId, ConstContext}; |
3dfed10e XL |
9 | use rustc_index::bit_set::FiniteBitSet; |
10 | use rustc_middle::mir::{ | |
11 | visit::{TyContext, Visitor}, | |
12 | Local, LocalDecl, Location, | |
13 | }; | |
14 | use rustc_middle::ty::{ | |
15 | self, | |
16 | fold::{TypeFoldable, TypeVisitor}, | |
17 | query::Providers, | |
18 | subst::SubstsRef, | |
19 | Const, Ty, TyCtxt, | |
20 | }; | |
21 | use rustc_span::symbol::sym; | |
22 | use std::convert::TryInto; | |
29967ef6 | 23 | use std::ops::ControlFlow; |
3dfed10e XL |
24 | |
25 | /// Provide implementations of queries relating to polymorphization analysis. | |
26 | pub fn provide(providers: &mut Providers) { | |
27 | providers.unused_generic_params = unused_generic_params; | |
28 | } | |
29 | ||
c295e0f8 XL |
30 | /// Determine which generic parameters are used by the instance. |
31 | /// | |
32 | /// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all | |
33 | /// parameters are used). | |
34 | #[instrument(level = "debug", skip(tcx))] | |
35 | fn unused_generic_params<'tcx>( | |
36 | tcx: TyCtxt<'tcx>, | |
37 | instance: ty::InstanceDef<'tcx>, | |
38 | ) -> FiniteBitSet<u32> { | |
3dfed10e XL |
39 | if !tcx.sess.opts.debugging_opts.polymorphize { |
40 | // If polymorphization disabled, then all parameters are used. | |
41 | return FiniteBitSet::new_empty(); | |
42 | } | |
43 | ||
c295e0f8 XL |
44 | let def_id = instance.def_id(); |
45 | // Exit early if this instance should not be polymorphized. | |
46 | if !should_polymorphize(tcx, def_id, instance) { | |
3dfed10e XL |
47 | return FiniteBitSet::new_empty(); |
48 | } | |
49 | ||
50 | let generics = tcx.generics_of(def_id); | |
6a06907d | 51 | debug!(?generics); |
3dfed10e XL |
52 | |
53 | // Exit early when there are no parameters to be unused. | |
54 | if generics.count() == 0 { | |
55 | return FiniteBitSet::new_empty(); | |
56 | } | |
57 | ||
3dfed10e XL |
58 | // Create a bitset with N rightmost ones for each parameter. |
59 | let generics_count: u32 = | |
60 | generics.count().try_into().expect("more generic parameters than can fit into a `u32`"); | |
61 | let mut unused_parameters = FiniteBitSet::<u32>::new_empty(); | |
62 | unused_parameters.set_range(0..generics_count); | |
6a06907d | 63 | debug!(?unused_parameters, "(start)"); |
c295e0f8 | 64 | |
3dfed10e | 65 | mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters); |
6a06907d | 66 | debug!(?unused_parameters, "(after default)"); |
3dfed10e XL |
67 | |
68 | // Visit MIR and accumululate used generic parameters. | |
c295e0f8 | 69 | let body = match tcx.hir().body_const_context(def_id.expect_local()) { |
5869c6ff | 70 | // Const functions are actually called and should thus be considered for polymorphization |
c295e0f8 | 71 | // via their runtime MIR. |
5869c6ff XL |
72 | Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id), |
73 | Some(_) => tcx.mir_for_ctfe(def_id), | |
74 | }; | |
3dfed10e XL |
75 | let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters }; |
76 | vis.visit_body(body); | |
6a06907d | 77 | debug!(?unused_parameters, "(end)"); |
3dfed10e XL |
78 | |
79 | // Emit errors for debugging and testing if enabled. | |
80 | if !unused_parameters.is_empty() { | |
81 | emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters); | |
82 | } | |
83 | ||
84 | unused_parameters | |
85 | } | |
86 | ||
c295e0f8 XL |
87 | /// Returns `true` if the instance should be polymorphized. |
88 | fn should_polymorphize<'tcx>( | |
89 | tcx: TyCtxt<'tcx>, | |
90 | def_id: DefId, | |
91 | instance: ty::InstanceDef<'tcx>, | |
92 | ) -> bool { | |
93 | // If an instance's MIR body is not polymorphic then the modified substitutions that are | |
94 | // derived from polymorphization's result won't make any difference. | |
95 | if !instance.has_polymorphic_mir_body() { | |
96 | return false; | |
97 | } | |
98 | ||
99 | // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic. | |
100 | if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) { | |
101 | return false; | |
102 | } | |
103 | ||
104 | // Polymorphization results are stored in cross-crate metadata only when there are unused | |
105 | // parameters, so assume that non-local items must have only used parameters (else this query | |
106 | // would not be invoked, and the cross-crate metadata used instead). | |
107 | if !def_id.is_local() { | |
108 | return false; | |
109 | } | |
110 | ||
111 | // Foreign items have no bodies to analyze. | |
112 | if tcx.is_foreign_item(def_id) { | |
113 | return false; | |
114 | } | |
115 | ||
116 | // Make sure there is MIR available. | |
117 | match tcx.hir().body_const_context(def_id.expect_local()) { | |
118 | Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => { | |
119 | debug!("no mir available"); | |
120 | return false; | |
121 | } | |
122 | Some(_) if !tcx.is_ctfe_mir_available(def_id) => { | |
123 | debug!("no ctfe mir available"); | |
124 | return false; | |
125 | } | |
126 | _ => true, | |
127 | } | |
128 | } | |
129 | ||
3dfed10e XL |
130 | /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy |
131 | /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should | |
132 | /// be `true` if the item that `unused_generic_params` was invoked on is a closure. | |
c295e0f8 | 133 | #[instrument(level = "debug", skip(tcx, def_id, generics, unused_parameters))] |
3dfed10e XL |
134 | fn mark_used_by_default_parameters<'tcx>( |
135 | tcx: TyCtxt<'tcx>, | |
136 | def_id: DefId, | |
137 | generics: &'tcx ty::Generics, | |
138 | unused_parameters: &mut FiniteBitSet<u32>, | |
139 | ) { | |
6a06907d XL |
140 | match tcx.def_kind(def_id) { |
141 | DefKind::Closure | DefKind::Generator => { | |
142 | for param in &generics.params { | |
143 | debug!(?param, "(closure/gen)"); | |
3dfed10e XL |
144 | unused_parameters.clear(param.index); |
145 | } | |
146 | } | |
6a06907d XL |
147 | DefKind::Mod |
148 | | DefKind::Struct | |
149 | | DefKind::Union | |
150 | | DefKind::Enum | |
151 | | DefKind::Variant | |
152 | | DefKind::Trait | |
153 | | DefKind::TyAlias | |
154 | | DefKind::ForeignTy | |
155 | | DefKind::TraitAlias | |
156 | | DefKind::AssocTy | |
157 | | DefKind::TyParam | |
158 | | DefKind::Fn | |
159 | | DefKind::Const | |
160 | | DefKind::ConstParam | |
161 | | DefKind::Static | |
162 | | DefKind::Ctor(_, _) | |
163 | | DefKind::AssocFn | |
164 | | DefKind::AssocConst | |
165 | | DefKind::Macro(_) | |
166 | | DefKind::ExternCrate | |
167 | | DefKind::Use | |
168 | | DefKind::ForeignMod | |
169 | | DefKind::AnonConst | |
3c0e092e | 170 | | DefKind::InlineConst |
6a06907d XL |
171 | | DefKind::OpaqueTy |
172 | | DefKind::Field | |
173 | | DefKind::LifetimeParam | |
174 | | DefKind::GlobalAsm | |
175 | | DefKind::Impl => { | |
176 | for param in &generics.params { | |
177 | debug!(?param, "(other)"); | |
178 | if let ty::GenericParamDefKind::Lifetime = param.kind { | |
179 | unused_parameters.clear(param.index); | |
180 | } | |
181 | } | |
182 | } | |
3dfed10e XL |
183 | } |
184 | ||
185 | if let Some(parent) = generics.parent { | |
186 | mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters); | |
187 | } | |
188 | } | |
189 | ||
3dfed10e XL |
190 | /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic |
191 | /// parameter which was unused. | |
c295e0f8 | 192 | #[instrument(level = "debug", skip(tcx, generics))] |
3dfed10e XL |
193 | fn emit_unused_generic_params_error<'tcx>( |
194 | tcx: TyCtxt<'tcx>, | |
195 | def_id: DefId, | |
196 | generics: &'tcx ty::Generics, | |
197 | unused_parameters: &FiniteBitSet<u32>, | |
198 | ) { | |
3c0e092e | 199 | let base_def_id = tcx.typeck_root_def_id(def_id); |
94222f64 | 200 | if !tcx.get_attrs(base_def_id).iter().any(|a| a.has_name(sym::rustc_polymorphize_error)) { |
3dfed10e XL |
201 | return; |
202 | } | |
203 | ||
3dfed10e XL |
204 | let fn_span = match tcx.opt_item_name(def_id) { |
205 | Some(ident) => ident.span, | |
206 | _ => tcx.def_span(def_id), | |
207 | }; | |
208 | ||
209 | let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters"); | |
210 | ||
211 | let mut next_generics = Some(generics); | |
212 | while let Some(generics) = next_generics { | |
213 | for param in &generics.params { | |
214 | if unused_parameters.contains(param.index).unwrap_or(false) { | |
6a06907d | 215 | debug!(?param); |
3dfed10e XL |
216 | let def_span = tcx.def_span(param.def_id); |
217 | err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name)); | |
218 | } | |
219 | } | |
220 | ||
221 | next_generics = generics.parent.map(|did| tcx.generics_of(did)); | |
222 | } | |
223 | ||
224 | err.emit(); | |
225 | } | |
226 | ||
227 | /// Visitor used to aggregate generic parameter uses. | |
228 | struct MarkUsedGenericParams<'a, 'tcx> { | |
229 | tcx: TyCtxt<'tcx>, | |
230 | def_id: DefId, | |
231 | unused_parameters: &'a mut FiniteBitSet<u32>, | |
232 | } | |
233 | ||
234 | impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> { | |
235 | /// Invoke `unused_generic_params` on a body contained within the current item (e.g. | |
236 | /// a closure, generator or constant). | |
c295e0f8 | 237 | #[instrument(level = "debug", skip(self, def_id, substs))] |
3dfed10e | 238 | fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) { |
c295e0f8 XL |
239 | let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)); |
240 | let unused = self.tcx.unused_generic_params(instance); | |
6a06907d | 241 | debug!(?self.unused_parameters, ?unused); |
3dfed10e XL |
242 | for (i, arg) in substs.iter().enumerate() { |
243 | let i = i.try_into().unwrap(); | |
244 | if !unused.contains(i).unwrap_or(false) { | |
245 | arg.visit_with(self); | |
246 | } | |
247 | } | |
6a06907d | 248 | debug!(?self.unused_parameters); |
3dfed10e XL |
249 | } |
250 | } | |
251 | ||
252 | impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { | |
c295e0f8 | 253 | #[instrument(level = "debug", skip(self, local))] |
3dfed10e | 254 | fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) { |
3dfed10e XL |
255 | if local == Local::from_usize(1) { |
256 | let def_kind = self.tcx.def_kind(self.def_id); | |
257 | if matches!(def_kind, DefKind::Closure | DefKind::Generator) { | |
258 | // Skip visiting the closure/generator that is currently being processed. This only | |
259 | // happens because the first argument to the closure is a reference to itself and | |
260 | // that will call `visit_substs`, resulting in each generic parameter captured being | |
261 | // considered used by default. | |
6a06907d | 262 | debug!("skipping closure substs"); |
3dfed10e XL |
263 | return; |
264 | } | |
265 | } | |
266 | ||
267 | self.super_local_decl(local, local_decl); | |
268 | } | |
269 | ||
5099ac24 | 270 | fn visit_const(&mut self, c: Const<'tcx>, _: Location) { |
3dfed10e XL |
271 | c.visit_with(self); |
272 | } | |
273 | ||
274 | fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) { | |
275 | ty.visit_with(self); | |
276 | } | |
277 | } | |
278 | ||
279 | impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { | |
c295e0f8 | 280 | #[instrument(level = "debug", skip(self))] |
5099ac24 FG |
281 | fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
282 | if !c.has_param_types_or_consts() { | |
29967ef6 | 283 | return ControlFlow::CONTINUE; |
3dfed10e XL |
284 | } |
285 | ||
5099ac24 | 286 | match c.val() { |
3dfed10e | 287 | ty::ConstKind::Param(param) => { |
6a06907d | 288 | debug!(?param); |
3dfed10e | 289 | self.unused_parameters.clear(param.index); |
29967ef6 | 290 | ControlFlow::CONTINUE |
3dfed10e | 291 | } |
5099ac24 | 292 | ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs: _, promoted: Some(p)}) |
3dfed10e XL |
293 | // Avoid considering `T` unused when constants are of the form: |
294 | // `<Self as Foo<T>>::foo::promoted[p]` | |
295 | if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self => | |
296 | { | |
297 | // If there is a promoted, don't look at the substs - since it will always contain | |
298 | // the generic parameters, instead, traverse the promoted MIR. | |
299 | let promoted = self.tcx.promoted_mir(def.did); | |
300 | self.visit_body(&promoted[p]); | |
29967ef6 | 301 | ControlFlow::CONTINUE |
3dfed10e | 302 | } |
94222f64 | 303 | ty::ConstKind::Unevaluated(uv) |
3c0e092e | 304 | if matches!(self.tcx.def_kind(uv.def.did), DefKind::AnonConst | DefKind::InlineConst) => |
3dfed10e | 305 | { |
5099ac24 | 306 | self.visit_child_body(uv.def.did, uv.substs); |
29967ef6 | 307 | ControlFlow::CONTINUE |
3dfed10e XL |
308 | } |
309 | _ => c.super_visit_with(self), | |
310 | } | |
311 | } | |
312 | ||
c295e0f8 | 313 | #[instrument(level = "debug", skip(self))] |
fc512014 | 314 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
5099ac24 | 315 | if !ty.has_param_types_or_consts() { |
29967ef6 | 316 | return ControlFlow::CONTINUE; |
3dfed10e XL |
317 | } |
318 | ||
1b1a35ee | 319 | match *ty.kind() { |
3dfed10e | 320 | ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => { |
6a06907d | 321 | debug!(?def_id); |
3dfed10e XL |
322 | // Avoid cycle errors with generators. |
323 | if def_id == self.def_id { | |
29967ef6 | 324 | return ControlFlow::CONTINUE; |
3dfed10e XL |
325 | } |
326 | ||
327 | // Consider any generic parameters used by any closures/generators as used in the | |
328 | // parent. | |
329 | self.visit_child_body(def_id, substs); | |
29967ef6 | 330 | ControlFlow::CONTINUE |
3dfed10e XL |
331 | } |
332 | ty::Param(param) => { | |
6a06907d | 333 | debug!(?param); |
3dfed10e | 334 | self.unused_parameters.clear(param.index); |
29967ef6 | 335 | ControlFlow::CONTINUE |
3dfed10e XL |
336 | } |
337 | _ => ty.super_visit_with(self), | |
338 | } | |
339 | } | |
340 | } | |
341 | ||
342 | /// Visitor used to check if a generic parameter is used. | |
5099ac24 | 343 | struct HasUsedGenericParams<'a> { |
3dfed10e XL |
344 | unused_parameters: &'a FiniteBitSet<u32>, |
345 | } | |
346 | ||
5099ac24 | 347 | impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> { |
fc512014 XL |
348 | type BreakTy = (); |
349 | ||
c295e0f8 | 350 | #[instrument(level = "debug", skip(self))] |
5099ac24 FG |
351 | fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
352 | if !c.has_param_types_or_consts() { | |
29967ef6 | 353 | return ControlFlow::CONTINUE; |
3dfed10e XL |
354 | } |
355 | ||
5099ac24 | 356 | match c.val() { |
3dfed10e | 357 | ty::ConstKind::Param(param) => { |
29967ef6 XL |
358 | if self.unused_parameters.contains(param.index).unwrap_or(false) { |
359 | ControlFlow::CONTINUE | |
360 | } else { | |
361 | ControlFlow::BREAK | |
362 | } | |
3dfed10e XL |
363 | } |
364 | _ => c.super_visit_with(self), | |
365 | } | |
366 | } | |
367 | ||
c295e0f8 | 368 | #[instrument(level = "debug", skip(self))] |
fc512014 | 369 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
5099ac24 | 370 | if !ty.has_param_types_or_consts() { |
29967ef6 | 371 | return ControlFlow::CONTINUE; |
3dfed10e XL |
372 | } |
373 | ||
1b1a35ee | 374 | match ty.kind() { |
29967ef6 XL |
375 | ty::Param(param) => { |
376 | if self.unused_parameters.contains(param.index).unwrap_or(false) { | |
377 | ControlFlow::CONTINUE | |
378 | } else { | |
379 | ControlFlow::BREAK | |
380 | } | |
381 | } | |
3dfed10e XL |
382 | _ => ty.super_visit_with(self), |
383 | } | |
384 | } | |
385 | } |