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