]>
Commit | Line | Data |
---|---|---|
ff7c6d11 | 1 | //! Mono Item Collection |
60c5eb7d | 2 | //! ==================== |
7453a54e | 3 | //! |
f035d41b | 4 | //! This module is responsible for discovering all items that will contribute |
7453a54e SL |
5 | //! to code generation of the crate. The important part here is that it not only |
6 | //! needs to find syntax-level items (functions, structs, etc) but also all | |
7 | //! their monomorphized instantiations. Every non-generic, non-const function | |
8 | //! maps to one LLVM artifact. Every generic function can produce | |
9 | //! from zero to N artifacts, depending on the sets of type arguments it | |
10 | //! is instantiated with. | |
11 | //! This also applies to generic items from other crates: A generic definition | |
12 | //! in crate X might produce monomorphizations that are compiled into crate Y. | |
13 | //! We also have to collect these here. | |
14 | //! | |
ff7c6d11 | 15 | //! The following kinds of "mono items" are handled here: |
7453a54e SL |
16 | //! |
17 | //! - Functions | |
18 | //! - Methods | |
19 | //! - Closures | |
20 | //! - Statics | |
21 | //! - Drop glue | |
22 | //! | |
23 | //! The following things also result in LLVM artifacts, but are not collected | |
24 | //! here, since we instantiate them locally on demand when needed in a given | |
25 | //! codegen unit: | |
26 | //! | |
27 | //! - Constants | |
28 | //! - Vtables | |
29 | //! - Object Shims | |
30 | //! | |
31 | //! | |
32 | //! General Algorithm | |
33 | //! ----------------- | |
34 | //! Let's define some terms first: | |
35 | //! | |
ff7c6d11 XL |
36 | //! - A "mono item" is something that results in a function or global in |
37 | //! the LLVM IR of a codegen unit. Mono items do not stand on their | |
38 | //! own, they can reference other mono items. For example, if function | |
39 | //! `foo()` calls function `bar()` then the mono item for `foo()` | |
40 | //! references the mono item for function `bar()`. In general, the | |
41 | //! definition for mono item A referencing a mono item B is that | |
7453a54e SL |
42 | //! the LLVM artifact produced for A references the LLVM artifact produced |
43 | //! for B. | |
44 | //! | |
ff7c6d11 XL |
45 | //! - Mono items and the references between them form a directed graph, |
46 | //! where the mono items are the nodes and references form the edges. | |
47 | //! Let's call this graph the "mono item graph". | |
7453a54e | 48 | //! |
ff7c6d11 | 49 | //! - The mono item graph for a program contains all mono items |
7453a54e SL |
50 | //! that are needed in order to produce the complete LLVM IR of the program. |
51 | //! | |
52 | //! The purpose of the algorithm implemented in this module is to build the | |
ff7c6d11 | 53 | //! mono item graph for the current crate. It runs in two phases: |
7453a54e SL |
54 | //! |
55 | //! 1. Discover the roots of the graph by traversing the HIR of the crate. | |
56 | //! 2. Starting from the roots, find neighboring nodes by inspecting the MIR | |
57 | //! representation of the item corresponding to a given node, until no more | |
58 | //! new nodes are found. | |
59 | //! | |
60 | //! ### Discovering roots | |
61 | //! | |
ff7c6d11 | 62 | //! The roots of the mono item graph correspond to the non-generic |
7453a54e SL |
63 | //! syntactic items in the source code. We find them by walking the HIR of the |
64 | //! crate, and whenever we hit upon a function, method, or static item, we | |
ff7c6d11 | 65 | //! create a mono item consisting of the items DefId and, since we only |
7453a54e SL |
66 | //! consider non-generic items, an empty type-substitution set. |
67 | //! | |
68 | //! ### Finding neighbor nodes | |
ff7c6d11 | 69 | //! Given a mono item node, we can discover neighbors by inspecting its |
7453a54e | 70 | //! MIR. We walk the MIR and any time we hit upon something that signifies a |
ff7c6d11 XL |
71 | //! reference to another mono item, we have found a neighbor. Since the |
72 | //! mono item we are currently at is always monomorphic, we also know the | |
7453a54e SL |
73 | //! concrete type arguments of its neighbors, and so all neighbors again will be |
74 | //! monomorphic. The specific forms a reference to a neighboring node can take | |
75 | //! in MIR are quite diverse. Here is an overview: | |
76 | //! | |
77 | //! #### Calling Functions/Methods | |
ff7c6d11 | 78 | //! The most obvious form of one mono item referencing another is a |
7453a54e SL |
79 | //! function or method call (represented by a CALL terminator in MIR). But |
80 | //! calls are not the only thing that might introduce a reference between two | |
ff7c6d11 | 81 | //! function mono items, and as we will see below, they are just a |
f035d41b | 82 | //! specialization of the form described next, and consequently will not get any |
7453a54e SL |
83 | //! special treatment in the algorithm. |
84 | //! | |
85 | //! #### Taking a reference to a function or method | |
86 | //! A function does not need to actually be called in order to be a neighbor of | |
87 | //! another function. It suffices to just take a reference in order to introduce | |
88 | //! an edge. Consider the following example: | |
89 | //! | |
90 | //! ```rust | |
91 | //! fn print_val<T: Display>(x: T) { | |
92 | //! println!("{}", x); | |
93 | //! } | |
94 | //! | |
95 | //! fn call_fn(f: &Fn(i32), x: i32) { | |
96 | //! f(x); | |
97 | //! } | |
98 | //! | |
99 | //! fn main() { | |
100 | //! let print_i32 = print_val::<i32>; | |
101 | //! call_fn(&print_i32, 0); | |
102 | //! } | |
103 | //! ``` | |
104 | //! The MIR of none of these functions will contain an explicit call to | |
ff7c6d11 | 105 | //! `print_val::<i32>`. Nonetheless, in order to mono this program, we need |
7453a54e SL |
106 | //! an instance of this function. Thus, whenever we encounter a function or |
107 | //! method in operand position, we treat it as a neighbor of the current | |
ff7c6d11 | 108 | //! mono item. Calls are just a special case of that. |
7453a54e SL |
109 | //! |
110 | //! #### Closures | |
111 | //! In a way, closures are a simple case. Since every closure object needs to be | |
112 | //! constructed somewhere, we can reliably discover them by observing | |
113 | //! `RValue::Aggregate` expressions with `AggregateKind::Closure`. This is also | |
114 | //! true for closures inlined from other crates. | |
115 | //! | |
116 | //! #### Drop glue | |
ff7c6d11 XL |
117 | //! Drop glue mono items are introduced by MIR drop-statements. The |
118 | //! generated mono item will again have drop-glue item neighbors if the | |
7453a54e SL |
119 | //! type to be dropped contains nested values that also need to be dropped. It |
120 | //! might also have a function item neighbor for the explicit `Drop::drop` | |
121 | //! implementation of its type. | |
122 | //! | |
123 | //! #### Unsizing Casts | |
124 | //! A subtle way of introducing neighbor edges is by casting to a trait object. | |
125 | //! Since the resulting fat-pointer contains a reference to a vtable, we need to | |
126 | //! instantiate all object-save methods of the trait, as we need to store | |
127 | //! pointers to these functions even if they never get called anywhere. This can | |
128 | //! be seen as a special case of taking a function reference. | |
129 | //! | |
130 | //! #### Boxes | |
131 | //! Since `Box` expression have special compiler support, no explicit calls to | |
0731742a | 132 | //! `exchange_malloc()` and `box_free()` may show up in MIR, even if the |
7453a54e SL |
133 | //! compiler will generate them. We have to observe `Rvalue::Box` expressions |
134 | //! and Box-typed drop-statements for that purpose. | |
135 | //! | |
136 | //! | |
137 | //! Interaction with Cross-Crate Inlining | |
138 | //! ------------------------------------- | |
139 | //! The binary of a crate will not only contain machine code for the items | |
140 | //! defined in the source code of that crate. It will also contain monomorphic | |
141 | //! instantiations of any extern generic functions and of functions marked with | |
ff7c6d11 XL |
142 | //! `#[inline]`. |
143 | //! The collection algorithm handles this more or less mono. If it is | |
144 | //! about to create a mono item for something with an external `DefId`, | |
7453a54e | 145 | //! it will take a look if the MIR for that item is available, and if so just |
9e0c209e | 146 | //! proceed normally. If the MIR is not available, it assumes that the item is |
7453a54e SL |
147 | //! just linked to and no node is created; which is exactly what we want, since |
148 | //! no machine code should be generated in the current crate for such an item. | |
149 | //! | |
150 | //! Eager and Lazy Collection Mode | |
151 | //! ------------------------------ | |
ff7c6d11 | 152 | //! Mono item collection can be performed in one of two modes: |
7453a54e SL |
153 | //! |
154 | //! - Lazy mode means that items will only be instantiated when actually | |
155 | //! referenced. The goal is to produce the least amount of machine code | |
156 | //! possible. | |
157 | //! | |
158 | //! - Eager mode is meant to be used in conjunction with incremental compilation | |
ff7c6d11 | 159 | //! where a stable set of mono items is more important than a minimal |
7453a54e | 160 | //! one. Thus, eager mode will instantiate drop-glue for every drop-able type |
f035d41b | 161 | //! in the crate, even if no drop call for that type exists (yet). It will |
7453a54e SL |
162 | //! also instantiate default implementations of trait methods, something that |
163 | //! otherwise is only done on demand. | |
164 | //! | |
165 | //! | |
166 | //! Open Issues | |
167 | //! ----------- | |
168 | //! Some things are not yet fully implemented in the current version of this | |
169 | //! module. | |
170 | //! | |
7453a54e | 171 | //! ### Const Fns |
ff7c6d11 | 172 | //! Ideally, no mono item should be generated for const fns unless there |
7453a54e | 173 | //! is a call to them that cannot be evaluated at compile time. At the moment |
ff7c6d11 | 174 | //! this is not implemented however: a mono item will be produced |
7453a54e SL |
175 | //! regardless of whether it is actually needed or not. |
176 | ||
60c5eb7d XL |
177 | use crate::monomorphize; |
178 | ||
dfeec247 XL |
179 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
180 | use rustc_data_structures::sync::{par_iter, MTLock, MTRef, ParallelIterator}; | |
f035d41b | 181 | use rustc_errors::{ErrorReported, FatalError}; |
dfeec247 | 182 | use rustc_hir as hir; |
f9f354fc | 183 | use rustc_hir::def_id::{DefId, DefIdMap, LocalDefId, LOCAL_CRATE}; |
dfeec247 | 184 | use rustc_hir::itemlikevisit::ItemLikeVisitor; |
3dfed10e | 185 | use rustc_hir::lang_items::LangItem; |
e74abb32 | 186 | use rustc_index::bit_set::GrowableBitSet; |
ba9703b0 XL |
187 | use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags; |
188 | use rustc_middle::mir::interpret::{AllocId, ConstValue}; | |
189 | use rustc_middle::mir::interpret::{ErrorHandled, GlobalAlloc, Scalar}; | |
190 | use rustc_middle::mir::mono::{InstantiationMode, MonoItem}; | |
191 | use rustc_middle::mir::visit::Visitor as MirVisitor; | |
192 | use rustc_middle::mir::{self, Local, Location}; | |
193 | use rustc_middle::ty::adjustment::{CustomCoerceUnsized, PointerCast}; | |
ba9703b0 XL |
194 | use rustc_middle::ty::subst::{GenericArgKind, InternalSubsts}; |
195 | use rustc_middle::ty::{self, GenericParamDefKind, Instance, Ty, TyCtxt, TypeFoldable}; | |
196 | use rustc_session::config::EntryFnType; | |
f035d41b | 197 | use rustc_span::source_map::{dummy_spanned, respan, Span, Spanned, DUMMY_SP}; |
dfeec247 | 198 | use smallvec::SmallVec; |
532ac7d7 | 199 | use std::iter; |
29967ef6 | 200 | use std::ops::Range; |
1b1a35ee | 201 | use std::path::PathBuf; |
532ac7d7 | 202 | |
e74abb32 | 203 | #[derive(PartialEq)] |
ff7c6d11 | 204 | pub enum MonoItemCollectionMode { |
7453a54e | 205 | Eager, |
dfeec247 | 206 | Lazy, |
7453a54e SL |
207 | } |
208 | ||
ff7c6d11 | 209 | /// Maps every mono item to all mono items it references in its |
a7813a04 XL |
210 | /// body. |
211 | pub struct InliningMap<'tcx> { | |
ff7c6d11 | 212 | // Maps a source mono item to the range of mono items |
3b2f2976 | 213 | // accessed by it. |
29967ef6 XL |
214 | // The range selects elements within the `targets` vecs. |
215 | index: FxHashMap<MonoItem<'tcx>, Range<usize>>, | |
ff7c6d11 | 216 | targets: Vec<MonoItem<'tcx>>, |
3b2f2976 | 217 | |
ff7c6d11 XL |
218 | // Contains one bit per mono item in the `targets` field. That bit |
219 | // is true if that mono item needs to be inlined into every CGU. | |
0bf4aa26 | 220 | inlines: GrowableBitSet<usize>, |
7453a54e SL |
221 | } |
222 | ||
a7813a04 | 223 | impl<'tcx> InliningMap<'tcx> { |
a7813a04 XL |
224 | fn new() -> InliningMap<'tcx> { |
225 | InliningMap { | |
0bf4aa26 | 226 | index: FxHashMap::default(), |
a7813a04 | 227 | targets: Vec::new(), |
0bf4aa26 | 228 | inlines: GrowableBitSet::with_capacity(1024), |
a7813a04 XL |
229 | } |
230 | } | |
231 | ||
dfeec247 | 232 | fn record_accesses(&mut self, source: MonoItem<'tcx>, new_targets: &[(MonoItem<'tcx>, bool)]) { |
a7813a04 | 233 | let start_index = self.targets.len(); |
3b2f2976 XL |
234 | let new_items_count = new_targets.len(); |
235 | let new_items_count_total = new_items_count + self.targets.len(); | |
236 | ||
237 | self.targets.reserve(new_items_count); | |
0bf4aa26 | 238 | self.inlines.ensure(new_items_count_total); |
3b2f2976 | 239 | |
dfeec247 XL |
240 | for (i, (target, inline)) in new_targets.iter().enumerate() { |
241 | self.targets.push(*target); | |
242 | if *inline { | |
3b2f2976 XL |
243 | self.inlines.insert(i + start_index); |
244 | } | |
245 | } | |
246 | ||
a7813a04 | 247 | let end_index = self.targets.len(); |
29967ef6 | 248 | assert!(self.index.insert(source, start_index..end_index).is_none()); |
a7813a04 XL |
249 | } |
250 | ||
251 | // Internally iterate over all items referenced by `source` which will be | |
252 | // made available for inlining. | |
ff7c6d11 | 253 | pub fn with_inlining_candidates<F>(&self, source: MonoItem<'tcx>, mut f: F) |
dfeec247 XL |
254 | where |
255 | F: FnMut(MonoItem<'tcx>), | |
3b2f2976 | 256 | { |
29967ef6 XL |
257 | if let Some(range) = self.index.get(&source) { |
258 | for (i, candidate) in self.targets[range.clone()].iter().enumerate() { | |
259 | if self.inlines.contains(range.start + i) { | |
3b2f2976 XL |
260 | f(*candidate); |
261 | } | |
7453a54e | 262 | } |
a7813a04 | 263 | } |
7453a54e | 264 | } |
3b2f2976 XL |
265 | |
266 | // Internally iterate over all items and the things each accesses. | |
267 | pub fn iter_accesses<F>(&self, mut f: F) | |
dfeec247 XL |
268 | where |
269 | F: FnMut(MonoItem<'tcx>, &[MonoItem<'tcx>]), | |
3b2f2976 | 270 | { |
29967ef6 XL |
271 | for (&accessor, range) in &self.index { |
272 | f(accessor, &self.targets[range.clone()]) | |
3b2f2976 XL |
273 | } |
274 | } | |
7453a54e SL |
275 | } |
276 | ||
416331ca XL |
277 | pub fn collect_crate_mono_items( |
278 | tcx: TyCtxt<'_>, | |
dc9dc135 | 279 | mode: MonoItemCollectionMode, |
416331ca | 280 | ) -> (FxHashSet<MonoItem<'_>>, InliningMap<'_>) { |
e74abb32 XL |
281 | let _prof_timer = tcx.prof.generic_activity("monomorphization_collector"); |
282 | ||
dfeec247 XL |
283 | let roots = |
284 | tcx.sess.time("monomorphization_collector_root_collections", || collect_roots(tcx, mode)); | |
ea8adc8c | 285 | |
416331ca | 286 | debug!("building mono item graph, beginning at roots"); |
94b46f34 | 287 | |
0bf4aa26 | 288 | let mut visited = MTLock::new(FxHashSet::default()); |
94b46f34 XL |
289 | let mut inlining_map = MTLock::new(InliningMap::new()); |
290 | ||
291 | { | |
292 | let visited: MTRef<'_, _> = &mut visited; | |
293 | let inlining_map: MTRef<'_, _> = &mut inlining_map; | |
294 | ||
dfeec247 | 295 | tcx.sess.time("monomorphization_collector_graph_walk", || { |
94b46f34 | 296 | par_iter(roots).for_each(|root| { |
a1dfa0c6 | 297 | let mut recursion_depths = DefIdMap::default(); |
f035d41b XL |
298 | collect_items_rec( |
299 | tcx, | |
300 | dummy_spanned(root), | |
301 | visited, | |
302 | &mut recursion_depths, | |
303 | inlining_map, | |
304 | ); | |
94b46f34 XL |
305 | }); |
306 | }); | |
ea8adc8c | 307 | } |
7453a54e | 308 | |
94b46f34 | 309 | (visited.into_inner(), inlining_map.into_inner()) |
7453a54e SL |
310 | } |
311 | ||
312 | // Find all non-generic items by walking the HIR. These items serve as roots to | |
313 | // start monomorphizing from. | |
416331ca XL |
314 | fn collect_roots(tcx: TyCtxt<'_>, mode: MonoItemCollectionMode) -> Vec<MonoItem<'_>> { |
315 | debug!("collecting roots"); | |
7453a54e SL |
316 | let mut roots = Vec::new(); |
317 | ||
318 | { | |
9fa01778 | 319 | let entry_fn = tcx.entry_fn(LOCAL_CRATE); |
abe05a73 | 320 | |
ff7c6d11 XL |
321 | debug!("collect_roots: entry_fn = {:?}", entry_fn); |
322 | ||
dfeec247 | 323 | let mut visitor = RootCollector { tcx, mode, entry_fn, output: &mut roots }; |
7453a54e | 324 | |
0731742a | 325 | tcx.hir().krate().visit_all_item_likes(&mut visitor); |
0531ce1d XL |
326 | |
327 | visitor.push_extra_entry_roots(); | |
7453a54e SL |
328 | } |
329 | ||
94b46f34 | 330 | // We can only codegen items that are instantiable - items all of |
041b39d2 | 331 | // whose predicates hold. Luckily, items that aren't instantiable |
94b46f34 | 332 | // can't actually be used, so we can just skip codegenning them. |
7453a54e | 333 | roots |
f035d41b XL |
334 | .into_iter() |
335 | .filter_map(|root| root.node.is_instantiable(tcx).then_some(root.node)) | |
336 | .collect() | |
7453a54e SL |
337 | } |
338 | ||
ff7c6d11 | 339 | // Collect all monomorphized items reachable from `starting_point` |
dc9dc135 XL |
340 | fn collect_items_rec<'tcx>( |
341 | tcx: TyCtxt<'tcx>, | |
f035d41b | 342 | starting_point: Spanned<MonoItem<'tcx>>, |
dc9dc135 XL |
343 | visited: MTRef<'_, MTLock<FxHashSet<MonoItem<'tcx>>>>, |
344 | recursion_depths: &mut DefIdMap<usize>, | |
345 | inlining_map: MTRef<'_, MTLock<InliningMap<'tcx>>>, | |
346 | ) { | |
f035d41b | 347 | if !visited.lock_mut().insert(starting_point.node) { |
7453a54e SL |
348 | // We've been here already, no need to search again. |
349 | return; | |
350 | } | |
1b1a35ee | 351 | debug!("BEGIN collect_items_rec({})", starting_point.node); |
7453a54e SL |
352 | |
353 | let mut neighbors = Vec::new(); | |
354 | let recursion_depth_reset; | |
355 | ||
f035d41b | 356 | match starting_point.node { |
0531ce1d | 357 | MonoItem::Static(def_id) => { |
ea8adc8c | 358 | let instance = Instance::mono(tcx, def_id); |
32a655c1 SL |
359 | |
360 | // Sanity check whether this ended up being collected accidentally | |
3dfed10e | 361 | debug_assert!(should_codegen_locally(tcx, &instance)); |
32a655c1 | 362 | |
3dfed10e | 363 | let ty = instance.ty(tcx, ty::ParamEnv::reveal_all()); |
f035d41b | 364 | visit_drop_use(tcx, ty, true, starting_point.span, &mut neighbors); |
a7813a04 | 365 | |
7453a54e | 366 | recursion_depth_reset = None; |
a7813a04 | 367 | |
1b1a35ee XL |
368 | if let Ok(alloc) = tcx.eval_static_initializer(def_id) { |
369 | for &((), id) in alloc.relocations().values() { | |
370 | collect_miri(tcx, id, &mut neighbors); | |
371 | } | |
0531ce1d | 372 | } |
7453a54e | 373 | } |
ff7c6d11 | 374 | MonoItem::Fn(instance) => { |
32a655c1 | 375 | // Sanity check whether this ended up being collected accidentally |
3dfed10e | 376 | debug_assert!(should_codegen_locally(tcx, &instance)); |
32a655c1 | 377 | |
7453a54e | 378 | // Keep track of the monomorphization recursion depth |
f035d41b XL |
379 | recursion_depth_reset = |
380 | Some(check_recursion_limit(tcx, instance, starting_point.span, recursion_depths)); | |
ea8adc8c | 381 | check_type_length_limit(tcx, instance); |
7453a54e | 382 | |
f9f354fc XL |
383 | rustc_data_structures::stack::ensure_sufficient_stack(|| { |
384 | collect_neighbours(tcx, instance, &mut neighbors); | |
385 | }); | |
7453a54e | 386 | } |
ff7c6d11 | 387 | MonoItem::GlobalAsm(..) => { |
cc61c64b XL |
388 | recursion_depth_reset = None; |
389 | } | |
7453a54e SL |
390 | } |
391 | ||
f035d41b | 392 | record_accesses(tcx, starting_point.node, neighbors.iter().map(|i| &i.node), inlining_map); |
a7813a04 | 393 | |
7453a54e | 394 | for neighbour in neighbors { |
ea8adc8c | 395 | collect_items_rec(tcx, neighbour, visited, recursion_depths, inlining_map); |
7453a54e SL |
396 | } |
397 | ||
398 | if let Some((def_id, depth)) = recursion_depth_reset { | |
399 | recursion_depths.insert(def_id, depth); | |
400 | } | |
401 | ||
1b1a35ee | 402 | debug!("END collect_items_rec({})", starting_point.node); |
7453a54e SL |
403 | } |
404 | ||
f035d41b | 405 | fn record_accesses<'a, 'tcx: 'a>( |
dc9dc135 XL |
406 | tcx: TyCtxt<'tcx>, |
407 | caller: MonoItem<'tcx>, | |
f035d41b | 408 | callees: impl Iterator<Item = &'a MonoItem<'tcx>>, |
dc9dc135 XL |
409 | inlining_map: MTRef<'_, MTLock<InliningMap<'tcx>>>, |
410 | ) { | |
ff7c6d11 XL |
411 | let is_inlining_candidate = |mono_item: &MonoItem<'tcx>| { |
412 | mono_item.instantiation_mode(tcx) == InstantiationMode::LocalCopy | |
a7813a04 XL |
413 | }; |
414 | ||
dfeec247 XL |
415 | // We collect this into a `SmallVec` to avoid calling `is_inlining_candidate` in the lock. |
416 | // FIXME: Call `is_inlining_candidate` when pushing to `neighbors` in `collect_items_rec` | |
417 | // instead to avoid creating this `SmallVec`. | |
74b04a01 | 418 | let accesses: SmallVec<[_; 128]> = |
f035d41b | 419 | callees.map(|mono_item| (*mono_item, is_inlining_candidate(mono_item))).collect(); |
a7813a04 | 420 | |
dfeec247 | 421 | inlining_map.lock_mut().record_accesses(caller, &accesses); |
a7813a04 XL |
422 | } |
423 | ||
1b1a35ee XL |
424 | /// Format instance name that is already known to be too long for rustc. |
425 | /// Show only the first and last 32 characters to avoid blasting | |
426 | /// the user's terminal with thousands of lines of type-name. | |
427 | /// | |
428 | /// If the type name is longer than before+after, it will be written to a file. | |
429 | fn shrunk_instance_name( | |
430 | tcx: TyCtxt<'tcx>, | |
431 | instance: &Instance<'tcx>, | |
432 | before: usize, | |
433 | after: usize, | |
434 | ) -> (String, Option<PathBuf>) { | |
435 | let s = instance.to_string(); | |
6c58768f XL |
436 | |
437 | // Only use the shrunk version if it's really shorter. | |
438 | // This also avoids the case where before and after slices overlap. | |
1b1a35ee XL |
439 | if s.chars().nth(before + after + 1).is_some() { |
440 | // An iterator of all byte positions including the end of the string. | |
441 | let positions = || s.char_indices().map(|(i, _)| i).chain(iter::once(s.len())); | |
442 | ||
443 | let shrunk = format!( | |
444 | "{before}...{after}", | |
445 | before = &s[..positions().nth(before).unwrap_or(s.len())], | |
446 | after = &s[positions().rev().nth(after).unwrap_or(0)..], | |
447 | ); | |
6c58768f | 448 | |
1b1a35ee XL |
449 | let path = tcx.output_filenames(LOCAL_CRATE).temp_path_ext("long-type.txt", None); |
450 | let written_to_path = std::fs::write(&path, s).ok().map(|_| path); | |
451 | ||
452 | (shrunk, written_to_path) | |
453 | } else { | |
454 | (s, None) | |
455 | } | |
6c58768f XL |
456 | } |
457 | ||
dc9dc135 XL |
458 | fn check_recursion_limit<'tcx>( |
459 | tcx: TyCtxt<'tcx>, | |
460 | instance: Instance<'tcx>, | |
f035d41b | 461 | span: Span, |
dc9dc135 XL |
462 | recursion_depths: &mut DefIdMap<usize>, |
463 | ) -> (DefId, usize) { | |
cc61c64b XL |
464 | let def_id = instance.def_id(); |
465 | let recursion_depth = recursion_depths.get(&def_id).cloned().unwrap_or(0); | |
7453a54e SL |
466 | debug!(" => recursion depth={}", recursion_depth); |
467 | ||
dfeec247 | 468 | let adjusted_recursion_depth = if Some(def_id) == tcx.lang_items().drop_in_place_fn() { |
cc61c64b XL |
469 | // HACK: drop_in_place creates tight monomorphization loops. Give |
470 | // it more margin. | |
471 | recursion_depth / 4 | |
472 | } else { | |
473 | recursion_depth | |
474 | }; | |
475 | ||
7453a54e SL |
476 | // Code that needs to instantiate the same function recursively |
477 | // more than the recursion limit is assumed to be causing an | |
478 | // infinite expansion. | |
f9f354fc | 479 | if !tcx.sess.recursion_limit().value_within_limit(adjusted_recursion_depth) { |
1b1a35ee XL |
480 | let (shrunk, written_to_path) = shrunk_instance_name(tcx, &instance, 32, 32); |
481 | let error = format!("reached the recursion limit while instantiating `{}`", shrunk); | |
f035d41b XL |
482 | let mut err = tcx.sess.struct_span_fatal(span, &error); |
483 | err.span_note( | |
484 | tcx.def_span(def_id), | |
485 | &format!("`{}` defined here", tcx.def_path_str(def_id)), | |
486 | ); | |
1b1a35ee XL |
487 | if let Some(path) = written_to_path { |
488 | err.note(&format!("the full type name has been written to '{}'", path.display())); | |
489 | } | |
f035d41b XL |
490 | err.emit(); |
491 | FatalError.raise(); | |
7453a54e SL |
492 | } |
493 | ||
cc61c64b | 494 | recursion_depths.insert(def_id, recursion_depth + 1); |
7453a54e | 495 | |
cc61c64b | 496 | (def_id, recursion_depth) |
7453a54e SL |
497 | } |
498 | ||
dc9dc135 | 499 | fn check_type_length_limit<'tcx>(tcx: TyCtxt<'tcx>, instance: Instance<'tcx>) { |
ba9703b0 XL |
500 | let type_length = instance |
501 | .substs | |
502 | .iter() | |
f9f354fc | 503 | .flat_map(|arg| arg.walk()) |
ba9703b0 XL |
504 | .filter(|arg| match arg.unpack() { |
505 | GenericArgKind::Type(_) | GenericArgKind::Const(_) => true, | |
506 | GenericArgKind::Lifetime(_) => false, | |
507 | }) | |
508 | .count(); | |
509 | debug!(" => type length={}", type_length); | |
476ff2be SL |
510 | |
511 | // Rust code can easily create exponentially-long types using only a | |
512 | // polynomial recursion depth. Even with the default recursion | |
513 | // depth, you can easily get cases that take >2^60 steps to run, | |
514 | // which means that rustc basically hangs. | |
515 | // | |
516 | // Bail out in these cases to avoid that bad user experience. | |
f9f354fc | 517 | if !tcx.sess.type_length_limit().value_within_limit(type_length) { |
1b1a35ee XL |
518 | let (shrunk, written_to_path) = shrunk_instance_name(tcx, &instance, 32, 32); |
519 | let msg = format!("reached the type-length limit while instantiating `{}`", shrunk); | |
532ac7d7 | 520 | let mut diag = tcx.sess.struct_span_fatal(tcx.def_span(instance.def_id()), &msg); |
1b1a35ee XL |
521 | if let Some(path) = written_to_path { |
522 | diag.note(&format!("the full type name has been written to '{}'", path.display())); | |
523 | } | |
524 | diag.help(&format!( | |
476ff2be | 525 | "consider adding a `#![type_length_limit=\"{}\"]` attribute to your crate", |
dfeec247 XL |
526 | type_length |
527 | )); | |
476ff2be SL |
528 | diag.emit(); |
529 | tcx.sess.abort_if_errors(); | |
530 | } | |
531 | } | |
532 | ||
dc9dc135 XL |
533 | struct MirNeighborCollector<'a, 'tcx> { |
534 | tcx: TyCtxt<'tcx>, | |
535 | body: &'a mir::Body<'tcx>, | |
f035d41b | 536 | output: &'a mut Vec<Spanned<MonoItem<'tcx>>>, |
ba9703b0 XL |
537 | instance: Instance<'tcx>, |
538 | } | |
539 | ||
540 | impl<'a, 'tcx> MirNeighborCollector<'a, 'tcx> { | |
541 | pub fn monomorphize<T>(&self, value: T) -> T | |
542 | where | |
543 | T: TypeFoldable<'tcx>, | |
544 | { | |
545 | debug!("monomorphize: self.instance={:?}", self.instance); | |
29967ef6 XL |
546 | self.instance.subst_mir_and_normalize_erasing_regions( |
547 | self.tcx, | |
548 | ty::ParamEnv::reveal_all(), | |
fc512014 | 549 | value, |
29967ef6 | 550 | ) |
ba9703b0 | 551 | } |
7453a54e SL |
552 | } |
553 | ||
554 | impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> { | |
9e0c209e | 555 | fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) { |
7453a54e SL |
556 | debug!("visiting rvalue {:?}", *rvalue); |
557 | ||
f035d41b XL |
558 | let span = self.body.source_info(location).span; |
559 | ||
7453a54e | 560 | match *rvalue { |
7453a54e SL |
561 | // When doing an cast from a regular pointer to a fat pointer, we |
562 | // have to instantiate all methods of the trait being cast to, so we | |
563 | // can build the appropriate vtable. | |
48663c56 | 564 | mir::Rvalue::Cast( |
dfeec247 XL |
565 | mir::CastKind::Pointer(PointerCast::Unsize), |
566 | ref operand, | |
567 | target_ty, | |
48663c56 | 568 | ) => { |
ba9703b0 | 569 | let target_ty = self.monomorphize(target_ty); |
dc9dc135 | 570 | let source_ty = operand.ty(self.body, self.tcx); |
ba9703b0 | 571 | let source_ty = self.monomorphize(source_ty); |
dfeec247 XL |
572 | let (source_ty, target_ty) = |
573 | find_vtable_types_for_unsizing(self.tcx, source_ty, target_ty); | |
7453a54e SL |
574 | // This could also be a different Unsize instruction, like |
575 | // from a fixed sized array to a slice. But we are only | |
576 | // interested in things that produce a vtable. | |
577 | if target_ty.is_trait() && !source_ty.is_trait() { | |
dfeec247 XL |
578 | create_mono_items_for_vtable_methods( |
579 | self.tcx, | |
580 | target_ty, | |
581 | source_ty, | |
f035d41b | 582 | span, |
dfeec247 XL |
583 | self.output, |
584 | ); | |
7453a54e SL |
585 | } |
586 | } | |
48663c56 | 587 | mir::Rvalue::Cast( |
dfeec247 XL |
588 | mir::CastKind::Pointer(PointerCast::ReifyFnPointer), |
589 | ref operand, | |
590 | _, | |
48663c56 | 591 | ) => { |
dc9dc135 | 592 | let fn_ty = operand.ty(self.body, self.tcx); |
ba9703b0 | 593 | let fn_ty = self.monomorphize(fn_ty); |
f035d41b | 594 | visit_fn_use(self.tcx, fn_ty, false, span, &mut self.output); |
cc61c64b | 595 | } |
48663c56 | 596 | mir::Rvalue::Cast( |
dfeec247 XL |
597 | mir::CastKind::Pointer(PointerCast::ClosureFnPointer(_)), |
598 | ref operand, | |
599 | _, | |
48663c56 | 600 | ) => { |
dc9dc135 | 601 | let source_ty = operand.ty(self.body, self.tcx); |
ba9703b0 | 602 | let source_ty = self.monomorphize(source_ty); |
1b1a35ee | 603 | match *source_ty.kind() { |
b7449926 | 604 | ty::Closure(def_id, substs) => { |
dc9dc135 | 605 | let instance = Instance::resolve_closure( |
dfeec247 XL |
606 | self.tcx, |
607 | def_id, | |
608 | substs, | |
609 | ty::ClosureKind::FnOnce, | |
610 | ); | |
3dfed10e XL |
611 | if should_codegen_locally(self.tcx, &instance) { |
612 | self.output.push(create_fn_mono_item(self.tcx, instance, span)); | |
83c7162d | 613 | } |
8bb4bdeb XL |
614 | } |
615 | _ => bug!(), | |
616 | } | |
617 | } | |
7cac9316 | 618 | mir::Rvalue::NullaryOp(mir::NullOp::Box, _) => { |
ea8adc8c | 619 | let tcx = self.tcx; |
f9f354fc | 620 | let exchange_malloc_fn_def_id = |
3dfed10e | 621 | tcx.require_lang_item(LangItem::ExchangeMalloc, None); |
cc61c64b | 622 | let instance = Instance::mono(tcx, exchange_malloc_fn_def_id); |
3dfed10e XL |
623 | if should_codegen_locally(tcx, &instance) { |
624 | self.output.push(create_fn_mono_item(self.tcx, instance, span)); | |
32a655c1 | 625 | } |
7453a54e | 626 | } |
f9f354fc XL |
627 | mir::Rvalue::ThreadLocalRef(def_id) => { |
628 | assert!(self.tcx.is_thread_local_static(def_id)); | |
629 | let instance = Instance::mono(self.tcx, def_id); | |
3dfed10e | 630 | if should_codegen_locally(self.tcx, &instance) { |
f9f354fc | 631 | trace!("collecting thread-local static {:?}", def_id); |
f035d41b | 632 | self.output.push(respan(span, MonoItem::Static(def_id))); |
f9f354fc XL |
633 | } |
634 | } | |
7453a54e SL |
635 | _ => { /* not interesting */ } |
636 | } | |
637 | ||
9e0c209e | 638 | self.super_rvalue(rvalue, location); |
7453a54e SL |
639 | } |
640 | ||
532ac7d7 | 641 | fn visit_const(&mut self, constant: &&'tcx ty::Const<'tcx>, location: Location) { |
ea8adc8c XL |
642 | debug!("visiting const {:?} @ {:?}", *constant, location); |
643 | ||
ba9703b0 XL |
644 | let substituted_constant = self.monomorphize(*constant); |
645 | let param_env = ty::ParamEnv::reveal_all(); | |
646 | ||
647 | match substituted_constant.val { | |
648 | ty::ConstKind::Value(val) => collect_const_value(self.tcx, val, self.output), | |
3dfed10e XL |
649 | ty::ConstKind::Unevaluated(def, substs, promoted) => { |
650 | match self.tcx.const_eval_resolve(param_env, def, substs, promoted, None) { | |
ba9703b0 XL |
651 | Ok(val) => collect_const_value(self.tcx, val, self.output), |
652 | Err(ErrorHandled::Reported(ErrorReported) | ErrorHandled::Linted) => {} | |
653 | Err(ErrorHandled::TooGeneric) => span_bug!( | |
3dfed10e XL |
654 | self.body.source_info(location).span, |
655 | "collection encountered polymorphic constant: {}", | |
656 | substituted_constant | |
ba9703b0 XL |
657 | ), |
658 | } | |
659 | } | |
660 | _ => {} | |
661 | } | |
7453a54e | 662 | |
ea8adc8c | 663 | self.super_const(constant); |
a7813a04 XL |
664 | } |
665 | ||
f035d41b XL |
666 | fn visit_terminator(&mut self, terminator: &mir::Terminator<'tcx>, location: Location) { |
667 | debug!("visiting terminator {:?} @ {:?}", terminator, location); | |
668 | let source = self.body.source_info(location).span; | |
7cac9316 | 669 | |
ea8adc8c | 670 | let tcx = self.tcx; |
f035d41b | 671 | match terminator.kind { |
cc61c64b | 672 | mir::TerminatorKind::Call { ref func, .. } => { |
dc9dc135 | 673 | let callee_ty = func.ty(self.body, tcx); |
ba9703b0 | 674 | let callee_ty = self.monomorphize(callee_ty); |
f035d41b | 675 | visit_fn_use(self.tcx, callee_ty, true, source, &mut self.output); |
a7813a04 | 676 | } |
f035d41b XL |
677 | mir::TerminatorKind::Drop { ref place, .. } |
678 | | mir::TerminatorKind::DropAndReplace { ref place, .. } => { | |
679 | let ty = place.ty(self.body, self.tcx).ty; | |
ba9703b0 | 680 | let ty = self.monomorphize(ty); |
f035d41b | 681 | visit_drop_use(self.tcx, ty, true, source, self.output); |
cc61c64b | 682 | } |
f9f354fc XL |
683 | mir::TerminatorKind::InlineAsm { ref operands, .. } => { |
684 | for op in operands { | |
f035d41b XL |
685 | match *op { |
686 | mir::InlineAsmOperand::SymFn { ref value } => { | |
6a06907d | 687 | let fn_ty = self.monomorphize(value.literal.ty()); |
f035d41b XL |
688 | visit_fn_use(self.tcx, fn_ty, false, source, &mut self.output); |
689 | } | |
690 | mir::InlineAsmOperand::SymStatic { def_id } => { | |
691 | let instance = Instance::mono(self.tcx, def_id); | |
3dfed10e | 692 | if should_codegen_locally(self.tcx, &instance) { |
f035d41b XL |
693 | trace!("collecting asm sym static {:?}", def_id); |
694 | self.output.push(respan(source, MonoItem::Static(def_id))); | |
695 | } | |
696 | } | |
697 | _ => {} | |
f9f354fc XL |
698 | } |
699 | } | |
700 | } | |
dfeec247 XL |
701 | mir::TerminatorKind::Goto { .. } |
702 | | mir::TerminatorKind::SwitchInt { .. } | |
703 | | mir::TerminatorKind::Resume | |
704 | | mir::TerminatorKind::Abort | |
705 | | mir::TerminatorKind::Return | |
706 | | mir::TerminatorKind::Unreachable | |
707 | | mir::TerminatorKind::Assert { .. } => {} | |
708 | mir::TerminatorKind::GeneratorDrop | |
709 | | mir::TerminatorKind::Yield { .. } | |
f035d41b | 710 | | mir::TerminatorKind::FalseEdge { .. } |
dfeec247 | 711 | | mir::TerminatorKind::FalseUnwind { .. } => bug!(), |
a7813a04 XL |
712 | } |
713 | ||
f035d41b | 714 | self.super_terminator(terminator, location); |
7453a54e | 715 | } |
3b2f2976 | 716 | |
f9f354fc | 717 | fn visit_local( |
dfeec247 XL |
718 | &mut self, |
719 | _place_local: &Local, | |
720 | _context: mir::visit::PlaceContext, | |
721 | _location: Location, | |
722 | ) { | |
3b2f2976 | 723 | } |
7453a54e SL |
724 | } |
725 | ||
dc9dc135 XL |
726 | fn visit_drop_use<'tcx>( |
727 | tcx: TyCtxt<'tcx>, | |
728 | ty: Ty<'tcx>, | |
729 | is_direct_call: bool, | |
f035d41b XL |
730 | source: Span, |
731 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, | |
dc9dc135 XL |
732 | ) { |
733 | let instance = Instance::resolve_drop_in_place(tcx, ty); | |
f035d41b | 734 | visit_instance_use(tcx, instance, is_direct_call, source, output); |
7453a54e SL |
735 | } |
736 | ||
dc9dc135 XL |
737 | fn visit_fn_use<'tcx>( |
738 | tcx: TyCtxt<'tcx>, | |
739 | ty: Ty<'tcx>, | |
740 | is_direct_call: bool, | |
f035d41b XL |
741 | source: Span, |
742 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, | |
dc9dc135 | 743 | ) { |
1b1a35ee | 744 | if let ty::FnDef(def_id, substs) = *ty.kind() { |
f9f354fc XL |
745 | let instance = if is_direct_call { |
746 | ty::Instance::resolve(tcx, ty::ParamEnv::reveal_all(), def_id, substs).unwrap().unwrap() | |
747 | } else { | |
748 | ty::Instance::resolve_for_fn_ptr(tcx, ty::ParamEnv::reveal_all(), def_id, substs) | |
749 | .unwrap() | |
750 | }; | |
f035d41b | 751 | visit_instance_use(tcx, instance, is_direct_call, source, output); |
7453a54e | 752 | } |
cc61c64b | 753 | } |
7453a54e | 754 | |
dc9dc135 XL |
755 | fn visit_instance_use<'tcx>( |
756 | tcx: TyCtxt<'tcx>, | |
757 | instance: ty::Instance<'tcx>, | |
758 | is_direct_call: bool, | |
f035d41b XL |
759 | source: Span, |
760 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, | |
dc9dc135 | 761 | ) { |
cc61c64b | 762 | debug!("visit_item_use({:?}, is_direct_call={:?})", instance, is_direct_call); |
3dfed10e | 763 | if !should_codegen_locally(tcx, &instance) { |
dfeec247 | 764 | return; |
7453a54e SL |
765 | } |
766 | ||
cc61c64b | 767 | match instance.def { |
dfeec247 | 768 | ty::InstanceDef::Virtual(..) | ty::InstanceDef::Intrinsic(_) => { |
cc61c64b | 769 | if !is_direct_call { |
60c5eb7d | 770 | bug!("{:?} being reified", instance); |
32a655c1 SL |
771 | } |
772 | } | |
cc61c64b | 773 | ty::InstanceDef::DropGlue(_, None) => { |
60c5eb7d | 774 | // Don't need to emit noop drop glue if we are calling directly. |
cc61c64b | 775 | if !is_direct_call { |
3dfed10e | 776 | output.push(create_fn_mono_item(tcx, instance, source)); |
7453a54e SL |
777 | } |
778 | } | |
dfeec247 XL |
779 | ty::InstanceDef::DropGlue(_, Some(_)) |
780 | | ty::InstanceDef::VtableShim(..) | |
781 | | ty::InstanceDef::ReifyShim(..) | |
782 | | ty::InstanceDef::ClosureOnceShim { .. } | |
783 | | ty::InstanceDef::Item(..) | |
784 | | ty::InstanceDef::FnPtrShim(..) | |
785 | | ty::InstanceDef::CloneShim(..) => { | |
3dfed10e | 786 | output.push(create_fn_mono_item(tcx, instance, source)); |
32a655c1 | 787 | } |
7453a54e SL |
788 | } |
789 | } | |
790 | ||
60c5eb7d XL |
791 | // Returns `true` if we should codegen an instance in the local crate. |
792 | // Returns `false` if we can just link to the upstream crate and therefore don't | |
ff7c6d11 | 793 | // need a mono item. |
3dfed10e | 794 | fn should_codegen_locally<'tcx>(tcx: TyCtxt<'tcx>, instance: &Instance<'tcx>) -> bool { |
cc61c64b | 795 | let def_id = match instance.def { |
3dfed10e XL |
796 | ty::InstanceDef::Item(def) => def.did, |
797 | ty::InstanceDef::DropGlue(def_id, Some(_)) => def_id, | |
dfeec247 XL |
798 | ty::InstanceDef::VtableShim(..) |
799 | | ty::InstanceDef::ReifyShim(..) | |
800 | | ty::InstanceDef::ClosureOnceShim { .. } | |
801 | | ty::InstanceDef::Virtual(..) | |
802 | | ty::InstanceDef::FnPtrShim(..) | |
803 | | ty::InstanceDef::DropGlue(..) | |
804 | | ty::InstanceDef::Intrinsic(_) | |
805 | | ty::InstanceDef::CloneShim(..) => return true, | |
cc61c64b | 806 | }; |
83c7162d | 807 | |
a1dfa0c6 | 808 | if tcx.is_foreign_item(def_id) { |
3dfed10e | 809 | // Foreign items are always linked against, there's no way of instantiating them. |
a1dfa0c6 XL |
810 | return false; |
811 | } | |
812 | ||
813 | if def_id.is_local() { | |
3dfed10e | 814 | // Local items cannot be referred to locally without monomorphizing them locally. |
a1dfa0c6 XL |
815 | return true; |
816 | } | |
817 | ||
3dfed10e XL |
818 | if tcx.is_reachable_non_generic(def_id) |
819 | || instance.polymorphize(tcx).upstream_monomorphization(tcx).is_some() | |
820 | { | |
821 | // We can link to the item in question, no instance needed in this crate. | |
a1dfa0c6 XL |
822 | return false; |
823 | } | |
824 | ||
825 | if !tcx.is_mir_available(def_id) { | |
5869c6ff | 826 | bug!("no MIR available for {:?}", def_id); |
a1dfa0c6 | 827 | } |
83c7162d | 828 | |
ba9703b0 | 829 | true |
7453a54e SL |
830 | } |
831 | ||
60c5eb7d | 832 | /// For a given pair of source and target type that occur in an unsizing coercion, |
7453a54e SL |
833 | /// this function finds the pair of types that determines the vtable linking |
834 | /// them. | |
835 | /// | |
836 | /// For example, the source type might be `&SomeStruct` and the target type\ | |
837 | /// might be `&SomeTrait` in a cast like: | |
838 | /// | |
839 | /// let src: &SomeStruct = ...; | |
840 | /// let target = src as &SomeTrait; | |
841 | /// | |
842 | /// Then the output of this function would be (SomeStruct, SomeTrait) since for | |
843 | /// constructing the `target` fat-pointer we need the vtable for that pair. | |
844 | /// | |
845 | /// Things can get more complicated though because there's also the case where | |
846 | /// the unsized type occurs as a field: | |
847 | /// | |
848 | /// ```rust | |
849 | /// struct ComplexStruct<T: ?Sized> { | |
850 | /// a: u32, | |
851 | /// b: f64, | |
852 | /// c: T | |
853 | /// } | |
854 | /// ``` | |
855 | /// | |
856 | /// In this case, if `T` is sized, `&ComplexStruct<T>` is a thin pointer. If `T` | |
857 | /// is unsized, `&SomeStruct` is a fat pointer, and the vtable it points to is | |
858 | /// for the pair of `T` (which is a trait) and the concrete type that `T` was | |
859 | /// originally coerced from: | |
860 | /// | |
861 | /// let src: &ComplexStruct<SomeStruct> = ...; | |
862 | /// let target = src as &ComplexStruct<SomeTrait>; | |
863 | /// | |
864 | /// Again, we want this `find_vtable_types_for_unsizing()` to provide the pair | |
865 | /// `(SomeStruct, SomeTrait)`. | |
866 | /// | |
0731742a | 867 | /// Finally, there is also the case of custom unsizing coercions, e.g., for |
7453a54e | 868 | /// smart pointers such as `Rc` and `Arc`. |
dc9dc135 XL |
869 | fn find_vtable_types_for_unsizing<'tcx>( |
870 | tcx: TyCtxt<'tcx>, | |
871 | source_ty: Ty<'tcx>, | |
872 | target_ty: Ty<'tcx>, | |
873 | ) -> (Ty<'tcx>, Ty<'tcx>) { | |
ea8adc8c | 874 | let ptr_vtable = |inner_source: Ty<'tcx>, inner_target: Ty<'tcx>| { |
416331ca | 875 | let param_env = ty::ParamEnv::reveal_all(); |
ff7c6d11 | 876 | let type_has_metadata = |ty: Ty<'tcx>| -> bool { |
416331ca | 877 | if ty.is_sized(tcx.at(DUMMY_SP), param_env) { |
ff7c6d11 XL |
878 | return false; |
879 | } | |
416331ca | 880 | let tail = tcx.struct_tail_erasing_lifetimes(ty, param_env); |
1b1a35ee | 881 | match tail.kind() { |
b7449926 XL |
882 | ty::Foreign(..) => false, |
883 | ty::Str | ty::Slice(..) | ty::Dynamic(..) => true, | |
532ac7d7 | 884 | _ => bug!("unexpected unsized tail: {:?}", tail), |
ff7c6d11 XL |
885 | } |
886 | }; | |
887 | if type_has_metadata(inner_source) { | |
32a655c1 SL |
888 | (inner_source, inner_target) |
889 | } else { | |
416331ca | 890 | tcx.struct_lockstep_tails_erasing_lifetimes(inner_source, inner_target, param_env) |
32a655c1 SL |
891 | } |
892 | }; | |
ff7c6d11 | 893 | |
1b1a35ee | 894 | match (&source_ty.kind(), &target_ty.kind()) { |
ba9703b0 | 895 | (&ty::Ref(_, a, _), &ty::Ref(_, b, _) | &ty::RawPtr(ty::TypeAndMut { ty: b, .. })) |
dfeec247 | 896 | | (&ty::RawPtr(ty::TypeAndMut { ty: a, .. }), &ty::RawPtr(ty::TypeAndMut { ty: b, .. })) => { |
32a655c1 SL |
897 | ptr_vtable(a, b) |
898 | } | |
b7449926 | 899 | (&ty::Adt(def_a, _), &ty::Adt(def_b, _)) if def_a.is_box() && def_b.is_box() => { |
32a655c1 | 900 | ptr_vtable(source_ty.boxed_ty(), target_ty.boxed_ty()) |
7453a54e SL |
901 | } |
902 | ||
dfeec247 | 903 | (&ty::Adt(source_adt_def, source_substs), &ty::Adt(target_adt_def, target_substs)) => { |
7453a54e SL |
904 | assert_eq!(source_adt_def, target_adt_def); |
905 | ||
74b04a01 XL |
906 | let CustomCoerceUnsized::Struct(coerce_index) = |
907 | monomorphize::custom_coerce_unsize_info(tcx, source_ty, target_ty); | |
7453a54e | 908 | |
2c00a5a8 XL |
909 | let source_fields = &source_adt_def.non_enum_variant().fields; |
910 | let target_fields = &target_adt_def.non_enum_variant().fields; | |
7453a54e | 911 | |
dfeec247 XL |
912 | assert!( |
913 | coerce_index < source_fields.len() && source_fields.len() == target_fields.len() | |
914 | ); | |
7453a54e | 915 | |
dfeec247 XL |
916 | find_vtable_types_for_unsizing( |
917 | tcx, | |
60c5eb7d | 918 | source_fields[coerce_index].ty(tcx, source_substs), |
dfeec247 | 919 | target_fields[coerce_index].ty(tcx, target_substs), |
60c5eb7d | 920 | ) |
7453a54e | 921 | } |
dfeec247 XL |
922 | _ => bug!( |
923 | "find_vtable_types_for_unsizing: invalid coercion {:?} -> {:?}", | |
924 | source_ty, | |
925 | target_ty | |
926 | ), | |
7453a54e SL |
927 | } |
928 | } | |
929 | ||
3dfed10e XL |
930 | fn create_fn_mono_item<'tcx>( |
931 | tcx: TyCtxt<'tcx>, | |
932 | instance: Instance<'tcx>, | |
933 | source: Span, | |
934 | ) -> Spanned<MonoItem<'tcx>> { | |
ff7c6d11 | 935 | debug!("create_fn_mono_item(instance={})", instance); |
3dfed10e | 936 | respan(source, MonoItem::Fn(instance.polymorphize(tcx))) |
7453a54e SL |
937 | } |
938 | ||
ff7c6d11 | 939 | /// Creates a `MonoItem` for each method that is referenced by the vtable for |
7453a54e | 940 | /// the given trait/impl pair. |
dc9dc135 XL |
941 | fn create_mono_items_for_vtable_methods<'tcx>( |
942 | tcx: TyCtxt<'tcx>, | |
943 | trait_ty: Ty<'tcx>, | |
944 | impl_ty: Ty<'tcx>, | |
f035d41b XL |
945 | source: Span, |
946 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, | |
dc9dc135 | 947 | ) { |
3dfed10e | 948 | assert!(!trait_ty.has_escaping_bound_vars() && !impl_ty.has_escaping_bound_vars()); |
7453a54e | 949 | |
1b1a35ee | 950 | if let ty::Dynamic(ref trait_ty, ..) = trait_ty.kind() { |
0731742a XL |
951 | if let Some(principal) = trait_ty.principal() { |
952 | let poly_trait_ref = principal.with_self_ty(tcx, impl_ty); | |
953 | assert!(!poly_trait_ref.has_escaping_bound_vars()); | |
954 | ||
955 | // Walk all methods of the trait, including those of its supertraits | |
956 | let methods = tcx.vtable_methods(poly_trait_ref); | |
dfeec247 XL |
957 | let methods = methods |
958 | .iter() | |
959 | .cloned() | |
960 | .filter_map(|method| method) | |
961 | .map(|(def_id, substs)| { | |
962 | ty::Instance::resolve_for_vtable( | |
963 | tcx, | |
964 | ty::ParamEnv::reveal_all(), | |
965 | def_id, | |
966 | substs, | |
967 | ) | |
968 | .unwrap() | |
969 | }) | |
3dfed10e XL |
970 | .filter(|&instance| should_codegen_locally(tcx, &instance)) |
971 | .map(|item| create_fn_mono_item(tcx, item, source)); | |
0731742a XL |
972 | output.extend(methods); |
973 | } | |
974 | ||
60c5eb7d | 975 | // Also add the destructor. |
f035d41b | 976 | visit_drop_use(tcx, impl_ty, false, source, output); |
7453a54e SL |
977 | } |
978 | } | |
979 | ||
980 | //=----------------------------------------------------------------------------- | |
981 | // Root Collection | |
982 | //=----------------------------------------------------------------------------- | |
983 | ||
dc9dc135 XL |
984 | struct RootCollector<'a, 'tcx> { |
985 | tcx: TyCtxt<'tcx>, | |
ff7c6d11 | 986 | mode: MonoItemCollectionMode, |
f035d41b | 987 | output: &'a mut Vec<Spanned<MonoItem<'tcx>>>, |
f9f354fc | 988 | entry_fn: Option<(LocalDefId, EntryFnType)>, |
7453a54e SL |
989 | } |
990 | ||
dc9dc135 | 991 | impl ItemLikeVisitor<'v> for RootCollector<'_, 'v> { |
dfeec247 | 992 | fn visit_item(&mut self, item: &'v hir::Item<'v>) { |
e74abb32 | 993 | match item.kind { |
dfeec247 XL |
994 | hir::ItemKind::ExternCrate(..) |
995 | | hir::ItemKind::Use(..) | |
fc512014 | 996 | | hir::ItemKind::ForeignMod { .. } |
dfeec247 XL |
997 | | hir::ItemKind::TyAlias(..) |
998 | | hir::ItemKind::Trait(..) | |
999 | | hir::ItemKind::TraitAlias(..) | |
1000 | | hir::ItemKind::OpaqueTy(..) | |
1001 | | hir::ItemKind::Mod(..) => { | |
60c5eb7d | 1002 | // Nothing to do, just keep recursing. |
7453a54e SL |
1003 | } |
1004 | ||
dfeec247 | 1005 | hir::ItemKind::Impl { .. } => { |
ff7c6d11 | 1006 | if self.mode == MonoItemCollectionMode::Eager { |
dfeec247 | 1007 | create_mono_items_for_default_impls(self.tcx, item, self.output); |
7453a54e SL |
1008 | } |
1009 | } | |
1010 | ||
dfeec247 XL |
1011 | hir::ItemKind::Enum(_, ref generics) |
1012 | | hir::ItemKind::Struct(_, ref generics) | |
1013 | | hir::ItemKind::Union(_, ref generics) => { | |
ff7c6d11 XL |
1014 | if generics.params.is_empty() { |
1015 | if self.mode == MonoItemCollectionMode::Eager { | |
dfeec247 XL |
1016 | debug!( |
1017 | "RootCollector: ADT drop-glue for {}", | |
6a06907d | 1018 | self.tcx.def_path_str(item.def_id.to_def_id()) |
dfeec247 | 1019 | ); |
7453a54e | 1020 | |
6a06907d | 1021 | let ty = Instance::new(item.def_id.to_def_id(), InternalSubsts::empty()) |
3dfed10e | 1022 | .ty(self.tcx, ty::ParamEnv::reveal_all()); |
f035d41b | 1023 | visit_drop_use(self.tcx, ty, true, DUMMY_SP, self.output); |
7453a54e SL |
1024 | } |
1025 | } | |
1026 | } | |
8faf50e0 | 1027 | hir::ItemKind::GlobalAsm(..) => { |
dfeec247 XL |
1028 | debug!( |
1029 | "RootCollector: ItemKind::GlobalAsm({})", | |
6a06907d | 1030 | self.tcx.def_path_str(item.def_id.to_def_id()) |
dfeec247 | 1031 | ); |
6a06907d | 1032 | self.output.push(dummy_spanned(MonoItem::GlobalAsm(item.item_id()))); |
cc61c64b | 1033 | } |
8faf50e0 | 1034 | hir::ItemKind::Static(..) => { |
6a06907d XL |
1035 | debug!( |
1036 | "RootCollector: ItemKind::Static({})", | |
1037 | self.tcx.def_path_str(item.def_id.to_def_id()) | |
1038 | ); | |
1039 | self.output.push(dummy_spanned(MonoItem::Static(item.def_id.to_def_id()))); | |
7453a54e | 1040 | } |
8faf50e0 | 1041 | hir::ItemKind::Const(..) => { |
ff7c6d11 | 1042 | // const items only generate mono items if they are |
5bcae85e | 1043 | // actually used somewhere. Just declaring them is insufficient. |
a1dfa0c6 XL |
1044 | |
1045 | // but even just declaring them must collect the items they refer to | |
6a06907d | 1046 | if let Ok(val) = self.tcx.const_eval_poly(item.def_id.to_def_id()) { |
74b04a01 | 1047 | collect_const_value(self.tcx, val, &mut self.output); |
a1dfa0c6 | 1048 | } |
5bcae85e | 1049 | } |
8faf50e0 | 1050 | hir::ItemKind::Fn(..) => { |
6a06907d | 1051 | self.push_if_root(item.def_id); |
7453a54e SL |
1052 | } |
1053 | } | |
7453a54e SL |
1054 | } |
1055 | ||
dfeec247 | 1056 | fn visit_trait_item(&mut self, _: &'v hir::TraitItem<'v>) { |
32a655c1 SL |
1057 | // Even if there's a default body with no explicit generics, |
1058 | // it's still generic over some `Self: Trait`, so not a root. | |
1059 | } | |
1060 | ||
dfeec247 | 1061 | fn visit_impl_item(&mut self, ii: &'v hir::ImplItem<'v>) { |
ba9703b0 | 1062 | if let hir::ImplItemKind::Fn(hir::FnSig { .. }, _) = ii.kind { |
6a06907d | 1063 | self.push_if_root(ii.def_id); |
7453a54e | 1064 | } |
7453a54e | 1065 | } |
fc512014 XL |
1066 | |
1067 | fn visit_foreign_item(&mut self, _foreign_item: &'v hir::ForeignItem<'v>) {} | |
7453a54e SL |
1068 | } |
1069 | ||
dc9dc135 | 1070 | impl RootCollector<'_, 'v> { |
f9f354fc | 1071 | fn is_root(&self, def_id: LocalDefId) -> bool { |
dfeec247 XL |
1072 | !item_requires_monomorphization(self.tcx, def_id) |
1073 | && match self.mode { | |
1074 | MonoItemCollectionMode::Eager => true, | |
1075 | MonoItemCollectionMode::Lazy => { | |
1076 | self.entry_fn.map(|(id, _)| id) == Some(def_id) | |
1077 | || self.tcx.is_reachable_non_generic(def_id) | |
1078 | || self | |
1079 | .tcx | |
1080 | .codegen_fn_attrs(def_id) | |
1081 | .flags | |
1082 | .contains(CodegenFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL) | |
1083 | } | |
abe05a73 | 1084 | } |
abe05a73 | 1085 | } |
ff7c6d11 | 1086 | |
60c5eb7d | 1087 | /// If `def_id` represents a root, pushes it onto the list of |
ff7c6d11 | 1088 | /// outputs. (Note that all roots must be monomorphic.) |
f9f354fc | 1089 | fn push_if_root(&mut self, def_id: LocalDefId) { |
ff7c6d11 XL |
1090 | if self.is_root(def_id) { |
1091 | debug!("RootCollector::push_if_root: found root def_id={:?}", def_id); | |
1092 | ||
f9f354fc | 1093 | let instance = Instance::mono(self.tcx, def_id.to_def_id()); |
3dfed10e | 1094 | self.output.push(create_fn_mono_item(self.tcx, instance, DUMMY_SP)); |
ff7c6d11 XL |
1095 | } |
1096 | } | |
1097 | ||
1098 | /// As a special case, when/if we encounter the | |
1099 | /// `main()` function, we also have to generate a | |
1100 | /// monomorphized copy of the start lang item based on | |
1101 | /// the return type of `main`. This is not needed when | |
1102 | /// the user writes their own `start` manually. | |
0531ce1d | 1103 | fn push_extra_entry_roots(&mut self) { |
9fa01778 XL |
1104 | let main_def_id = match self.entry_fn { |
1105 | Some((def_id, EntryFnType::Main)) => def_id, | |
1106 | _ => return, | |
0531ce1d XL |
1107 | }; |
1108 | ||
3dfed10e | 1109 | let start_def_id = match self.tcx.lang_items().require(LangItem::Start) { |
ff7c6d11 XL |
1110 | Ok(s) => s, |
1111 | Err(err) => self.tcx.sess.fatal(&err), | |
1112 | }; | |
0531ce1d | 1113 | let main_ret_ty = self.tcx.fn_sig(main_def_id).output(); |
ff7c6d11 XL |
1114 | |
1115 | // Given that `main()` has no arguments, | |
1116 | // then its return type cannot have | |
1117 | // late-bound regions, since late-bound | |
1118 | // regions must appear in the argument | |
1119 | // listing. | |
fc512014 | 1120 | let main_ret_ty = self.tcx.erase_regions(main_ret_ty.no_bound_vars().unwrap()); |
ff7c6d11 XL |
1121 | |
1122 | let start_instance = Instance::resolve( | |
1123 | self.tcx, | |
0531ce1d | 1124 | ty::ParamEnv::reveal_all(), |
ff7c6d11 | 1125 | start_def_id, |
dfeec247 XL |
1126 | self.tcx.intern_substs(&[main_ret_ty.into()]), |
1127 | ) | |
f9f354fc | 1128 | .unwrap() |
dfeec247 | 1129 | .unwrap(); |
ff7c6d11 | 1130 | |
3dfed10e | 1131 | self.output.push(create_fn_mono_item(self.tcx, start_instance, DUMMY_SP)); |
ff7c6d11 | 1132 | } |
abe05a73 XL |
1133 | } |
1134 | ||
f9f354fc | 1135 | fn item_requires_monomorphization(tcx: TyCtxt<'_>, def_id: LocalDefId) -> bool { |
3b2f2976 | 1136 | let generics = tcx.generics_of(def_id); |
94b46f34 | 1137 | generics.requires_monomorphization(tcx) |
3b2f2976 XL |
1138 | } |
1139 | ||
dc9dc135 XL |
1140 | fn create_mono_items_for_default_impls<'tcx>( |
1141 | tcx: TyCtxt<'tcx>, | |
dfeec247 | 1142 | item: &'tcx hir::Item<'tcx>, |
f035d41b | 1143 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, |
dc9dc135 | 1144 | ) { |
e74abb32 | 1145 | match item.kind { |
5869c6ff XL |
1146 | hir::ItemKind::Impl(ref impl_) => { |
1147 | for param in impl_.generics.params { | |
8faf50e0 XL |
1148 | match param.kind { |
1149 | hir::GenericParamKind::Lifetime { .. } => {} | |
dfeec247 XL |
1150 | hir::GenericParamKind::Type { .. } | hir::GenericParamKind::Const { .. } => { |
1151 | return; | |
9fa01778 | 1152 | } |
8faf50e0 | 1153 | } |
7453a54e SL |
1154 | } |
1155 | ||
dfeec247 XL |
1156 | debug!( |
1157 | "create_mono_items_for_default_impls(item={})", | |
6a06907d | 1158 | tcx.def_path_str(item.def_id.to_def_id()) |
dfeec247 | 1159 | ); |
7453a54e | 1160 | |
6a06907d | 1161 | if let Some(trait_ref) = tcx.impl_trait_ref(item.def_id) { |
416331ca | 1162 | let param_env = ty::ParamEnv::reveal_all(); |
dfeec247 | 1163 | let trait_ref = tcx.normalize_erasing_regions(param_env, trait_ref); |
476ff2be | 1164 | let overridden_methods: FxHashSet<_> = |
5869c6ff | 1165 | impl_.items.iter().map(|iiref| iiref.ident.normalize_to_macros_2_0()).collect(); |
9e0c209e | 1166 | for method in tcx.provided_trait_methods(trait_ref.def_id) { |
ba9703b0 | 1167 | if overridden_methods.contains(&method.ident.normalize_to_macros_2_0()) { |
7453a54e SL |
1168 | continue; |
1169 | } | |
1170 | ||
48663c56 | 1171 | if tcx.generics_of(method.def_id).own_requires_monomorphization() { |
7453a54e SL |
1172 | continue; |
1173 | } | |
1174 | ||
dfeec247 XL |
1175 | let substs = |
1176 | InternalSubsts::for_item(tcx, method.def_id, |param, _| match param.kind { | |
48663c56 | 1177 | GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(), |
dfeec247 | 1178 | GenericParamDefKind::Type { .. } | GenericParamDefKind::Const => { |
94b46f34 XL |
1179 | trait_ref.substs[param.index as usize] |
1180 | } | |
dfeec247 | 1181 | }); |
f9f354fc XL |
1182 | let instance = ty::Instance::resolve(tcx, param_env, method.def_id, substs) |
1183 | .unwrap() | |
1184 | .unwrap(); | |
cc61c64b | 1185 | |
3dfed10e XL |
1186 | let mono_item = create_fn_mono_item(tcx, instance, DUMMY_SP); |
1187 | if mono_item.node.is_instantiable(tcx) && should_codegen_locally(tcx, &instance) | |
dfeec247 | 1188 | { |
ff7c6d11 | 1189 | output.push(mono_item); |
7453a54e SL |
1190 | } |
1191 | } | |
1192 | } | |
1193 | } | |
dfeec247 | 1194 | _ => bug!(), |
7453a54e SL |
1195 | } |
1196 | } | |
1197 | ||
60c5eb7d | 1198 | /// Scans the miri alloc in order to find function calls, closures, and drop-glue. |
f035d41b XL |
1199 | fn collect_miri<'tcx>( |
1200 | tcx: TyCtxt<'tcx>, | |
1201 | alloc_id: AllocId, | |
1202 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, | |
1203 | ) { | |
f9f354fc XL |
1204 | match tcx.global_alloc(alloc_id) { |
1205 | GlobalAlloc::Static(def_id) => { | |
1206 | assert!(!tcx.is_thread_local_static(def_id)); | |
dc9dc135 | 1207 | let instance = Instance::mono(tcx, def_id); |
3dfed10e | 1208 | if should_codegen_locally(tcx, &instance) { |
dc9dc135 | 1209 | trace!("collecting static {:?}", def_id); |
f035d41b | 1210 | output.push(dummy_spanned(MonoItem::Static(def_id))); |
94b46f34 | 1211 | } |
0531ce1d | 1212 | } |
f9f354fc | 1213 | GlobalAlloc::Memory(alloc) => { |
94b46f34 | 1214 | trace!("collecting {:?} with {:#?}", alloc_id, alloc); |
e1599b0c | 1215 | for &((), inner) in alloc.relocations().values() { |
f9f354fc XL |
1216 | rustc_data_structures::stack::ensure_sufficient_stack(|| { |
1217 | collect_miri(tcx, inner, output); | |
1218 | }); | |
94b46f34 | 1219 | } |
dfeec247 | 1220 | } |
f9f354fc | 1221 | GlobalAlloc::Function(fn_instance) => { |
3dfed10e | 1222 | if should_codegen_locally(tcx, &fn_instance) { |
94b46f34 | 1223 | trace!("collecting {:?} with {:#?}", alloc_id, fn_instance); |
3dfed10e | 1224 | output.push(create_fn_mono_item(tcx, fn_instance, DUMMY_SP)); |
94b46f34 | 1225 | } |
0531ce1d | 1226 | } |
0531ce1d XL |
1227 | } |
1228 | } | |
1229 | ||
60c5eb7d | 1230 | /// Scans the MIR in order to find function calls, closures, and drop-glue. |
dc9dc135 XL |
1231 | fn collect_neighbours<'tcx>( |
1232 | tcx: TyCtxt<'tcx>, | |
1233 | instance: Instance<'tcx>, | |
f035d41b | 1234 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, |
dc9dc135 | 1235 | ) { |
e1599b0c | 1236 | debug!("collect_neighbours: {:?}", instance.def_id()); |
dc9dc135 | 1237 | let body = tcx.instance_mir(instance.def); |
5bcae85e | 1238 | |
ba9703b0 | 1239 | MirNeighborCollector { tcx, body: &body, output, instance }.visit_body(&body); |
7453a54e | 1240 | } |
476ff2be | 1241 | |
74b04a01 XL |
1242 | fn collect_const_value<'tcx>( |
1243 | tcx: TyCtxt<'tcx>, | |
1244 | value: ConstValue<'tcx>, | |
f035d41b | 1245 | output: &mut Vec<Spanned<MonoItem<'tcx>>>, |
74b04a01 XL |
1246 | ) { |
1247 | match value { | |
1248 | ConstValue::Scalar(Scalar::Ptr(ptr)) => collect_miri(tcx, ptr.alloc_id, output), | |
1249 | ConstValue::Slice { data: alloc, start: _, end: _ } | ConstValue::ByRef { alloc, .. } => { | |
1250 | for &((), id) in alloc.relocations().values() { | |
1251 | collect_miri(tcx, id, output); | |
1252 | } | |
1253 | } | |
1254 | _ => {} | |
1255 | } | |
1256 | } |