]>
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 | //! | |
181 | //! ### Initializers of Constants and Statics | |
182 | //! Since no MIR is constructed yet for initializer expressions of constants and | |
183 | //! statics we cannot inspect these properly. | |
184 | //! | |
185 | //! ### Const Fns | |
ff7c6d11 | 186 | //! Ideally, no mono item should be generated for const fns unless there |
7453a54e | 187 | //! is a call to them that cannot be evaluated at compile time. At the moment |
ff7c6d11 | 188 | //! this is not implemented however: a mono item will be produced |
7453a54e SL |
189 | //! regardless of whether it is actually needed or not. |
190 | ||
0531ce1d | 191 | use rustc::hir::{self, TransFnAttrFlags}; |
476ff2be | 192 | use rustc::hir::itemlikevisit::ItemLikeVisitor; |
7453a54e | 193 | |
54a0048b SL |
194 | use rustc::hir::map as hir_map; |
195 | use rustc::hir::def_id::DefId; | |
ea8adc8c | 196 | use rustc::middle::const_val::ConstVal; |
0531ce1d | 197 | use rustc::mir::interpret::{Value, PrimVal, AllocId, Pointer}; |
ff7c6d11 | 198 | use rustc::middle::lang_items::{ExchangeMallocFnLangItem, StartFnLangItem}; |
ff7c6d11 | 199 | use rustc::ty::subst::{Substs, Kind}; |
ea8adc8c | 200 | use rustc::ty::{self, TypeFoldable, Ty, TyCtxt}; |
54a0048b | 201 | use rustc::ty::adjustment::CustomCoerceUnsized; |
ff7c6d11 | 202 | use rustc::session::config; |
0531ce1d | 203 | use rustc::mir::{self, Location, Promoted}; |
7453a54e | 204 | use rustc::mir::visit::Visitor as MirVisitor; |
ff7c6d11 | 205 | use rustc::mir::mono::MonoItem; |
0531ce1d | 206 | use rustc::mir::interpret::GlobalId; |
7453a54e | 207 | |
54a0048b | 208 | use monomorphize::{self, Instance}; |
7cac9316 | 209 | use rustc::util::nodemap::{FxHashSet, FxHashMap, DefIdMap}; |
7453a54e | 210 | |
ff7c6d11 | 211 | use monomorphize::item::{MonoItemExt, DefPathBasedNames, InstantiationMode}; |
32a655c1 | 212 | |
3b2f2976 | 213 | use rustc_data_structures::bitvec::BitVector; |
3b2f2976 | 214 | |
7453a54e | 215 | #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] |
ff7c6d11 | 216 | pub enum MonoItemCollectionMode { |
7453a54e SL |
217 | Eager, |
218 | Lazy | |
219 | } | |
220 | ||
ff7c6d11 | 221 | /// Maps every mono item to all mono items it references in its |
a7813a04 XL |
222 | /// body. |
223 | pub struct InliningMap<'tcx> { | |
ff7c6d11 | 224 | // Maps a source mono item to the range of mono items |
3b2f2976 | 225 | // accessed by it. |
a7813a04 XL |
226 | // The two numbers in the tuple are the start (inclusive) and |
227 | // end index (exclusive) within the `targets` vecs. | |
ff7c6d11 XL |
228 | index: FxHashMap<MonoItem<'tcx>, (usize, usize)>, |
229 | targets: Vec<MonoItem<'tcx>>, | |
3b2f2976 | 230 | |
ff7c6d11 XL |
231 | // Contains one bit per mono item in the `targets` field. That bit |
232 | // is true if that mono item needs to be inlined into every CGU. | |
3b2f2976 | 233 | inlines: BitVector, |
7453a54e SL |
234 | } |
235 | ||
a7813a04 XL |
236 | impl<'tcx> InliningMap<'tcx> { |
237 | ||
238 | fn new() -> InliningMap<'tcx> { | |
239 | InliningMap { | |
476ff2be | 240 | index: FxHashMap(), |
a7813a04 | 241 | targets: Vec::new(), |
3b2f2976 | 242 | inlines: BitVector::new(1024), |
a7813a04 XL |
243 | } |
244 | } | |
245 | ||
3b2f2976 | 246 | fn record_accesses<I>(&mut self, |
ff7c6d11 | 247 | source: MonoItem<'tcx>, |
3b2f2976 | 248 | new_targets: I) |
ff7c6d11 | 249 | where I: Iterator<Item=(MonoItem<'tcx>, bool)> + ExactSizeIterator |
a7813a04 XL |
250 | { |
251 | assert!(!self.index.contains_key(&source)); | |
252 | ||
253 | let start_index = self.targets.len(); | |
3b2f2976 XL |
254 | let new_items_count = new_targets.len(); |
255 | let new_items_count_total = new_items_count + self.targets.len(); | |
256 | ||
257 | self.targets.reserve(new_items_count); | |
258 | self.inlines.grow(new_items_count_total); | |
259 | ||
260 | for (i, (target, inline)) in new_targets.enumerate() { | |
261 | self.targets.push(target); | |
262 | if inline { | |
263 | self.inlines.insert(i + start_index); | |
264 | } | |
265 | } | |
266 | ||
a7813a04 XL |
267 | let end_index = self.targets.len(); |
268 | self.index.insert(source, (start_index, end_index)); | |
269 | } | |
270 | ||
271 | // Internally iterate over all items referenced by `source` which will be | |
272 | // made available for inlining. | |
ff7c6d11 XL |
273 | pub fn with_inlining_candidates<F>(&self, source: MonoItem<'tcx>, mut f: F) |
274 | where F: FnMut(MonoItem<'tcx>) | |
3b2f2976 XL |
275 | { |
276 | if let Some(&(start_index, end_index)) = self.index.get(&source) { | |
277 | for (i, candidate) in self.targets[start_index .. end_index] | |
278 | .iter() | |
279 | .enumerate() { | |
280 | if self.inlines.contains(start_index + i) { | |
281 | f(*candidate); | |
282 | } | |
7453a54e | 283 | } |
a7813a04 | 284 | } |
7453a54e | 285 | } |
3b2f2976 XL |
286 | |
287 | // Internally iterate over all items and the things each accesses. | |
288 | pub fn iter_accesses<F>(&self, mut f: F) | |
ff7c6d11 | 289 | where F: FnMut(MonoItem<'tcx>, &[MonoItem<'tcx>]) |
3b2f2976 XL |
290 | { |
291 | for (&accessor, &(start_index, end_index)) in &self.index { | |
292 | f(accessor, &self.targets[start_index .. end_index]) | |
293 | } | |
294 | } | |
7453a54e SL |
295 | } |
296 | ||
ff7c6d11 XL |
297 | pub fn collect_crate_mono_items<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
298 | mode: MonoItemCollectionMode) | |
299 | -> (FxHashSet<MonoItem<'tcx>>, | |
a7813a04 | 300 | InliningMap<'tcx>) { |
ea8adc8c XL |
301 | let roots = collect_roots(tcx, mode); |
302 | ||
ff7c6d11 | 303 | debug!("Building mono item graph, beginning at roots"); |
ea8adc8c XL |
304 | let mut visited = FxHashSet(); |
305 | let mut recursion_depths = DefIdMap(); | |
306 | let mut inlining_map = InliningMap::new(); | |
307 | ||
308 | for root in roots { | |
309 | collect_items_rec(tcx, | |
310 | root, | |
311 | &mut visited, | |
312 | &mut recursion_depths, | |
313 | &mut inlining_map); | |
314 | } | |
7453a54e | 315 | |
ea8adc8c | 316 | (visited, inlining_map) |
7453a54e SL |
317 | } |
318 | ||
319 | // Find all non-generic items by walking the HIR. These items serve as roots to | |
320 | // start monomorphizing from. | |
ea8adc8c | 321 | fn collect_roots<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
ff7c6d11 XL |
322 | mode: MonoItemCollectionMode) |
323 | -> Vec<MonoItem<'tcx>> { | |
7453a54e SL |
324 | debug!("Collecting roots"); |
325 | let mut roots = Vec::new(); | |
326 | ||
327 | { | |
83c7162d | 328 | let entry_fn = tcx.sess.entry_fn.borrow().map(|(node_id, _, _)| { |
abe05a73 XL |
329 | tcx.hir.local_def_id(node_id) |
330 | }); | |
331 | ||
ff7c6d11 XL |
332 | debug!("collect_roots: entry_fn = {:?}", entry_fn); |
333 | ||
7453a54e | 334 | let mut visitor = RootCollector { |
ea8adc8c | 335 | tcx, |
3b2f2976 | 336 | mode, |
abe05a73 | 337 | entry_fn, |
7453a54e | 338 | output: &mut roots, |
7453a54e SL |
339 | }; |
340 | ||
ea8adc8c | 341 | tcx.hir.krate().visit_all_item_likes(&mut visitor); |
0531ce1d XL |
342 | |
343 | visitor.push_extra_entry_roots(); | |
7453a54e SL |
344 | } |
345 | ||
041b39d2 XL |
346 | // We can only translate items that are instantiable - items all of |
347 | // whose predicates hold. Luckily, items that aren't instantiable | |
348 | // can't actually be used, so we can just skip translating them. | |
ea8adc8c | 349 | roots.retain(|root| root.is_instantiable(tcx)); |
041b39d2 | 350 | |
7453a54e SL |
351 | roots |
352 | } | |
353 | ||
ff7c6d11 | 354 | // Collect all monomorphized items reachable from `starting_point` |
ea8adc8c | 355 | fn collect_items_rec<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
ff7c6d11 XL |
356 | starting_point: MonoItem<'tcx>, |
357 | visited: &mut FxHashSet<MonoItem<'tcx>>, | |
a7813a04 XL |
358 | recursion_depths: &mut DefIdMap<usize>, |
359 | inlining_map: &mut InliningMap<'tcx>) { | |
7453a54e SL |
360 | if !visited.insert(starting_point.clone()) { |
361 | // We've been here already, no need to search again. | |
362 | return; | |
363 | } | |
ea8adc8c | 364 | debug!("BEGIN collect_items_rec({})", starting_point.to_string(tcx)); |
7453a54e SL |
365 | |
366 | let mut neighbors = Vec::new(); | |
367 | let recursion_depth_reset; | |
368 | ||
369 | match starting_point { | |
0531ce1d | 370 | MonoItem::Static(def_id) => { |
ea8adc8c | 371 | let instance = Instance::mono(tcx, def_id); |
32a655c1 SL |
372 | |
373 | // Sanity check whether this ended up being collected accidentally | |
ff7c6d11 | 374 | debug_assert!(should_monomorphize_locally(tcx, &instance)); |
32a655c1 | 375 | |
ff7c6d11 | 376 | let ty = instance.ty(tcx); |
ea8adc8c | 377 | visit_drop_use(tcx, ty, true, &mut neighbors); |
a7813a04 | 378 | |
7453a54e | 379 | recursion_depth_reset = None; |
a7813a04 | 380 | |
0531ce1d XL |
381 | let cid = GlobalId { |
382 | instance, | |
383 | promoted: None, | |
384 | }; | |
385 | let param_env = ty::ParamEnv::reveal_all(); | |
386 | ||
387 | match tcx.const_eval(param_env.and(cid)) { | |
388 | Ok(val) => collect_const(tcx, val, instance.substs, &mut neighbors), | |
389 | Err(err) => { | |
390 | let span = tcx.def_span(def_id); | |
391 | err.report(tcx, span, "static"); | |
392 | } | |
393 | } | |
7453a54e | 394 | } |
ff7c6d11 | 395 | MonoItem::Fn(instance) => { |
32a655c1 | 396 | // Sanity check whether this ended up being collected accidentally |
ff7c6d11 | 397 | debug_assert!(should_monomorphize_locally(tcx, &instance)); |
32a655c1 | 398 | |
7453a54e | 399 | // Keep track of the monomorphization recursion depth |
ea8adc8c | 400 | recursion_depth_reset = Some(check_recursion_limit(tcx, |
54a0048b | 401 | instance, |
7453a54e | 402 | recursion_depths)); |
ea8adc8c | 403 | check_type_length_limit(tcx, instance); |
7453a54e | 404 | |
0531ce1d | 405 | collect_neighbours(tcx, instance, &mut neighbors); |
7453a54e | 406 | } |
ff7c6d11 | 407 | MonoItem::GlobalAsm(..) => { |
cc61c64b XL |
408 | recursion_depth_reset = None; |
409 | } | |
7453a54e SL |
410 | } |
411 | ||
ea8adc8c | 412 | record_accesses(tcx, starting_point, &neighbors[..], inlining_map); |
a7813a04 | 413 | |
7453a54e | 414 | for neighbour in neighbors { |
ea8adc8c | 415 | collect_items_rec(tcx, neighbour, visited, recursion_depths, inlining_map); |
7453a54e SL |
416 | } |
417 | ||
418 | if let Some((def_id, depth)) = recursion_depth_reset { | |
419 | recursion_depths.insert(def_id, depth); | |
420 | } | |
421 | ||
ea8adc8c | 422 | debug!("END collect_items_rec({})", starting_point.to_string(tcx)); |
7453a54e SL |
423 | } |
424 | ||
3b2f2976 | 425 | fn record_accesses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
ff7c6d11 XL |
426 | caller: MonoItem<'tcx>, |
427 | callees: &[MonoItem<'tcx>], | |
ea8adc8c | 428 | inlining_map: &mut InliningMap<'tcx>) { |
ff7c6d11 XL |
429 | let is_inlining_candidate = |mono_item: &MonoItem<'tcx>| { |
430 | mono_item.instantiation_mode(tcx) == InstantiationMode::LocalCopy | |
a7813a04 XL |
431 | }; |
432 | ||
3b2f2976 | 433 | let accesses = callees.into_iter() |
ff7c6d11 XL |
434 | .map(|mono_item| { |
435 | (*mono_item, is_inlining_candidate(mono_item)) | |
3b2f2976 | 436 | }); |
a7813a04 | 437 | |
3b2f2976 | 438 | inlining_map.record_accesses(caller, accesses); |
a7813a04 XL |
439 | } |
440 | ||
441 | fn check_recursion_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
442 | instance: Instance<'tcx>, | |
443 | recursion_depths: &mut DefIdMap<usize>) | |
444 | -> (DefId, usize) { | |
cc61c64b XL |
445 | let def_id = instance.def_id(); |
446 | let recursion_depth = recursion_depths.get(&def_id).cloned().unwrap_or(0); | |
7453a54e SL |
447 | debug!(" => recursion depth={}", recursion_depth); |
448 | ||
ea8adc8c | 449 | let recursion_depth = if Some(def_id) == tcx.lang_items().drop_in_place_fn() { |
cc61c64b XL |
450 | // HACK: drop_in_place creates tight monomorphization loops. Give |
451 | // it more margin. | |
452 | recursion_depth / 4 | |
453 | } else { | |
454 | recursion_depth | |
455 | }; | |
456 | ||
7453a54e SL |
457 | // Code that needs to instantiate the same function recursively |
458 | // more than the recursion limit is assumed to be causing an | |
459 | // infinite expansion. | |
83c7162d | 460 | if recursion_depth > *tcx.sess.recursion_limit.get() { |
54a0048b SL |
461 | let error = format!("reached the recursion limit while instantiating `{}`", |
462 | instance); | |
cc61c64b | 463 | if let Some(node_id) = tcx.hir.as_local_node_id(def_id) { |
32a655c1 | 464 | tcx.sess.span_fatal(tcx.hir.span(node_id), &error); |
7453a54e | 465 | } else { |
a7813a04 | 466 | tcx.sess.fatal(&error); |
7453a54e SL |
467 | } |
468 | } | |
469 | ||
cc61c64b | 470 | recursion_depths.insert(def_id, recursion_depth + 1); |
7453a54e | 471 | |
cc61c64b | 472 | (def_id, recursion_depth) |
7453a54e SL |
473 | } |
474 | ||
476ff2be SL |
475 | fn check_type_length_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
476 | instance: Instance<'tcx>) | |
477 | { | |
478 | let type_length = instance.substs.types().flat_map(|ty| ty.walk()).count(); | |
479 | debug!(" => type length={}", type_length); | |
480 | ||
481 | // Rust code can easily create exponentially-long types using only a | |
482 | // polynomial recursion depth. Even with the default recursion | |
483 | // depth, you can easily get cases that take >2^60 steps to run, | |
484 | // which means that rustc basically hangs. | |
485 | // | |
486 | // Bail out in these cases to avoid that bad user experience. | |
83c7162d | 487 | let type_length_limit = *tcx.sess.type_length_limit.get(); |
476ff2be SL |
488 | if type_length > type_length_limit { |
489 | // The instance name is already known to be too long for rustc. Use | |
490 | // `{:.64}` to avoid blasting the user's terminal with thousands of | |
491 | // lines of type-name. | |
492 | let instance_name = instance.to_string(); | |
493 | let msg = format!("reached the type-length limit while instantiating `{:.64}...`", | |
494 | instance_name); | |
cc61c64b | 495 | let mut diag = if let Some(node_id) = tcx.hir.as_local_node_id(instance.def_id()) { |
32a655c1 | 496 | tcx.sess.struct_span_fatal(tcx.hir.span(node_id), &msg) |
476ff2be SL |
497 | } else { |
498 | tcx.sess.struct_fatal(&msg) | |
499 | }; | |
500 | ||
501 | diag.note(&format!( | |
502 | "consider adding a `#![type_length_limit=\"{}\"]` attribute to your crate", | |
503 | type_length_limit*2)); | |
504 | diag.emit(); | |
505 | tcx.sess.abort_if_errors(); | |
506 | } | |
507 | } | |
508 | ||
7453a54e | 509 | struct MirNeighborCollector<'a, 'tcx: 'a> { |
ea8adc8c | 510 | tcx: TyCtxt<'a, 'tcx, 'tcx>, |
7453a54e | 511 | mir: &'a mir::Mir<'tcx>, |
ff7c6d11 | 512 | output: &'a mut Vec<MonoItem<'tcx>>, |
3b2f2976 | 513 | param_substs: &'tcx Substs<'tcx>, |
7453a54e SL |
514 | } |
515 | ||
516 | impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> { | |
517 | ||
9e0c209e | 518 | fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) { |
7453a54e SL |
519 | debug!("visiting rvalue {:?}", *rvalue); |
520 | ||
521 | match *rvalue { | |
7453a54e SL |
522 | // When doing an cast from a regular pointer to a fat pointer, we |
523 | // have to instantiate all methods of the trait being cast to, so we | |
524 | // can build the appropriate vtable. | |
525 | mir::Rvalue::Cast(mir::CastKind::Unsize, ref operand, target_ty) => { | |
0531ce1d XL |
526 | let target_ty = self.tcx.subst_and_normalize_erasing_regions( |
527 | self.param_substs, | |
528 | ty::ParamEnv::reveal_all(), | |
529 | &target_ty, | |
530 | ); | |
ea8adc8c | 531 | let source_ty = operand.ty(self.mir, self.tcx); |
0531ce1d XL |
532 | let source_ty = self.tcx.subst_and_normalize_erasing_regions( |
533 | self.param_substs, | |
534 | ty::ParamEnv::reveal_all(), | |
535 | &source_ty, | |
536 | ); | |
ea8adc8c | 537 | let (source_ty, target_ty) = find_vtable_types_for_unsizing(self.tcx, |
7453a54e SL |
538 | source_ty, |
539 | target_ty); | |
540 | // This could also be a different Unsize instruction, like | |
541 | // from a fixed sized array to a slice. But we are only | |
542 | // interested in things that produce a vtable. | |
543 | if target_ty.is_trait() && !source_ty.is_trait() { | |
ff7c6d11 XL |
544 | create_mono_items_for_vtable_methods(self.tcx, |
545 | target_ty, | |
546 | source_ty, | |
547 | self.output); | |
7453a54e SL |
548 | } |
549 | } | |
cc61c64b | 550 | mir::Rvalue::Cast(mir::CastKind::ReifyFnPointer, ref operand, _) => { |
ea8adc8c | 551 | let fn_ty = operand.ty(self.mir, self.tcx); |
0531ce1d XL |
552 | let fn_ty = self.tcx.subst_and_normalize_erasing_regions( |
553 | self.param_substs, | |
554 | ty::ParamEnv::reveal_all(), | |
555 | &fn_ty, | |
556 | ); | |
ea8adc8c | 557 | visit_fn_use(self.tcx, fn_ty, false, &mut self.output); |
cc61c64b | 558 | } |
8bb4bdeb | 559 | mir::Rvalue::Cast(mir::CastKind::ClosureFnPointer, ref operand, _) => { |
ea8adc8c | 560 | let source_ty = operand.ty(self.mir, self.tcx); |
0531ce1d XL |
561 | let source_ty = self.tcx.subst_and_normalize_erasing_regions( |
562 | self.param_substs, | |
563 | ty::ParamEnv::reveal_all(), | |
564 | &source_ty, | |
565 | ); | |
8bb4bdeb XL |
566 | match source_ty.sty { |
567 | ty::TyClosure(def_id, substs) => { | |
cc61c64b | 568 | let instance = monomorphize::resolve_closure( |
ea8adc8c | 569 | self.tcx, def_id, substs, ty::ClosureKind::FnOnce); |
83c7162d XL |
570 | if should_monomorphize_locally(self.tcx, &instance) { |
571 | self.output.push(create_fn_mono_item(instance)); | |
572 | } | |
8bb4bdeb XL |
573 | } |
574 | _ => bug!(), | |
575 | } | |
576 | } | |
7cac9316 | 577 | mir::Rvalue::NullaryOp(mir::NullOp::Box, _) => { |
ea8adc8c | 578 | let tcx = self.tcx; |
cc61c64b | 579 | let exchange_malloc_fn_def_id = tcx |
ea8adc8c | 580 | .lang_items() |
cc61c64b | 581 | .require(ExchangeMallocFnLangItem) |
ea8adc8c | 582 | .unwrap_or_else(|e| tcx.sess.fatal(&e)); |
cc61c64b | 583 | let instance = Instance::mono(tcx, exchange_malloc_fn_def_id); |
ff7c6d11 XL |
584 | if should_monomorphize_locally(tcx, &instance) { |
585 | self.output.push(create_fn_mono_item(instance)); | |
32a655c1 | 586 | } |
7453a54e SL |
587 | } |
588 | _ => { /* not interesting */ } | |
589 | } | |
590 | ||
9e0c209e | 591 | self.super_rvalue(rvalue, location); |
7453a54e SL |
592 | } |
593 | ||
ea8adc8c XL |
594 | fn visit_const(&mut self, constant: &&'tcx ty::Const<'tcx>, location: Location) { |
595 | debug!("visiting const {:?} @ {:?}", *constant, location); | |
596 | ||
0531ce1d | 597 | collect_const(self.tcx, constant, self.param_substs, self.output); |
7453a54e | 598 | |
ea8adc8c | 599 | self.super_const(constant); |
a7813a04 XL |
600 | } |
601 | ||
a7813a04 XL |
602 | fn visit_terminator_kind(&mut self, |
603 | block: mir::BasicBlock, | |
9e0c209e SL |
604 | kind: &mir::TerminatorKind<'tcx>, |
605 | location: Location) { | |
7cac9316 XL |
606 | debug!("visiting terminator {:?} @ {:?}", kind, location); |
607 | ||
ea8adc8c | 608 | let tcx = self.tcx; |
a7813a04 | 609 | match *kind { |
cc61c64b XL |
610 | mir::TerminatorKind::Call { ref func, .. } => { |
611 | let callee_ty = func.ty(self.mir, tcx); | |
0531ce1d XL |
612 | let callee_ty = tcx.subst_and_normalize_erasing_regions( |
613 | self.param_substs, | |
614 | ty::ParamEnv::reveal_all(), | |
615 | &callee_ty, | |
616 | ); | |
617 | visit_fn_use(self.tcx, callee_ty, true, &mut self.output); | |
a7813a04 | 618 | } |
cc61c64b XL |
619 | mir::TerminatorKind::Drop { ref location, .. } | |
620 | mir::TerminatorKind::DropAndReplace { ref location, .. } => { | |
ea8adc8c XL |
621 | let ty = location.ty(self.mir, self.tcx) |
622 | .to_ty(self.tcx); | |
0531ce1d XL |
623 | let ty = tcx.subst_and_normalize_erasing_regions( |
624 | self.param_substs, | |
625 | ty::ParamEnv::reveal_all(), | |
626 | &ty, | |
627 | ); | |
ea8adc8c | 628 | visit_drop_use(self.tcx, ty, true, self.output); |
cc61c64b XL |
629 | } |
630 | mir::TerminatorKind::Goto { .. } | | |
631 | mir::TerminatorKind::SwitchInt { .. } | | |
632 | mir::TerminatorKind::Resume | | |
ff7c6d11 | 633 | mir::TerminatorKind::Abort | |
cc61c64b XL |
634 | mir::TerminatorKind::Return | |
635 | mir::TerminatorKind::Unreachable | | |
636 | mir::TerminatorKind::Assert { .. } => {} | |
ea8adc8c | 637 | mir::TerminatorKind::GeneratorDrop | |
abe05a73 | 638 | mir::TerminatorKind::Yield { .. } | |
2c00a5a8 XL |
639 | mir::TerminatorKind::FalseEdges { .. } | |
640 | mir::TerminatorKind::FalseUnwind { .. } => bug!(), | |
a7813a04 XL |
641 | } |
642 | ||
9e0c209e | 643 | self.super_terminator_kind(block, kind, location); |
7453a54e | 644 | } |
3b2f2976 XL |
645 | |
646 | fn visit_static(&mut self, | |
647 | static_: &mir::Static<'tcx>, | |
ff7c6d11 | 648 | context: mir::visit::PlaceContext<'tcx>, |
3b2f2976 XL |
649 | location: Location) { |
650 | debug!("visiting static {:?} @ {:?}", static_.def_id, location); | |
651 | ||
ea8adc8c | 652 | let tcx = self.tcx; |
3b2f2976 | 653 | let instance = Instance::mono(tcx, static_.def_id); |
ff7c6d11 | 654 | if should_monomorphize_locally(tcx, &instance) { |
0531ce1d | 655 | self.output.push(MonoItem::Static(static_.def_id)); |
3b2f2976 XL |
656 | } |
657 | ||
658 | self.super_static(static_, context, location); | |
659 | } | |
7453a54e SL |
660 | } |
661 | ||
ea8adc8c XL |
662 | fn visit_drop_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
663 | ty: Ty<'tcx>, | |
cc61c64b | 664 | is_direct_call: bool, |
ff7c6d11 | 665 | output: &mut Vec<MonoItem<'tcx>>) |
cc61c64b | 666 | { |
ea8adc8c XL |
667 | let instance = monomorphize::resolve_drop_in_place(tcx, ty); |
668 | visit_instance_use(tcx, instance, is_direct_call, output); | |
7453a54e SL |
669 | } |
670 | ||
ea8adc8c XL |
671 | fn visit_fn_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
672 | ty: Ty<'tcx>, | |
cc61c64b | 673 | is_direct_call: bool, |
ff7c6d11 | 674 | output: &mut Vec<MonoItem<'tcx>>) |
cc61c64b | 675 | { |
041b39d2 | 676 | if let ty::TyFnDef(def_id, substs) = ty.sty { |
ea8adc8c | 677 | let instance = ty::Instance::resolve(tcx, |
0531ce1d | 678 | ty::ParamEnv::reveal_all(), |
ea8adc8c XL |
679 | def_id, |
680 | substs).unwrap(); | |
681 | visit_instance_use(tcx, instance, is_direct_call, output); | |
7453a54e | 682 | } |
cc61c64b | 683 | } |
7453a54e | 684 | |
ea8adc8c | 685 | fn visit_instance_use<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
cc61c64b XL |
686 | instance: ty::Instance<'tcx>, |
687 | is_direct_call: bool, | |
ff7c6d11 | 688 | output: &mut Vec<MonoItem<'tcx>>) |
cc61c64b XL |
689 | { |
690 | debug!("visit_item_use({:?}, is_direct_call={:?})", instance, is_direct_call); | |
ff7c6d11 | 691 | if !should_monomorphize_locally(tcx, &instance) { |
cc61c64b | 692 | return |
7453a54e SL |
693 | } |
694 | ||
cc61c64b XL |
695 | match instance.def { |
696 | ty::InstanceDef::Intrinsic(def_id) => { | |
697 | if !is_direct_call { | |
698 | bug!("intrinsic {:?} being reified", def_id); | |
32a655c1 SL |
699 | } |
700 | } | |
cc61c64b XL |
701 | ty::InstanceDef::Virtual(..) | |
702 | ty::InstanceDef::DropGlue(_, None) => { | |
703 | // don't need to emit shim if we are calling directly. | |
704 | if !is_direct_call { | |
ff7c6d11 | 705 | output.push(create_fn_mono_item(instance)); |
7453a54e SL |
706 | } |
707 | } | |
7cac9316 | 708 | ty::InstanceDef::DropGlue(_, Some(_)) => { |
ff7c6d11 | 709 | output.push(create_fn_mono_item(instance)); |
7453a54e | 710 | } |
cc61c64b XL |
711 | ty::InstanceDef::ClosureOnceShim { .. } | |
712 | ty::InstanceDef::Item(..) | | |
3b2f2976 XL |
713 | ty::InstanceDef::FnPtrShim(..) | |
714 | ty::InstanceDef::CloneShim(..) => { | |
ff7c6d11 | 715 | output.push(create_fn_mono_item(instance)); |
32a655c1 | 716 | } |
7453a54e SL |
717 | } |
718 | } | |
719 | ||
cc61c64b XL |
720 | // Returns true if we should translate an instance in the local crate. |
721 | // Returns false if we can just link to the upstream crate and therefore don't | |
ff7c6d11 XL |
722 | // need a mono item. |
723 | fn should_monomorphize_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, instance: &Instance<'tcx>) | |
724 | -> bool { | |
cc61c64b XL |
725 | let def_id = match instance.def { |
726 | ty::InstanceDef::Item(def_id) => def_id, | |
727 | ty::InstanceDef::ClosureOnceShim { .. } | | |
728 | ty::InstanceDef::Virtual(..) | | |
729 | ty::InstanceDef::FnPtrShim(..) | | |
730 | ty::InstanceDef::DropGlue(..) | | |
3b2f2976 XL |
731 | ty::InstanceDef::Intrinsic(_) | |
732 | ty::InstanceDef::CloneShim(..) => return true | |
cc61c64b | 733 | }; |
83c7162d XL |
734 | |
735 | return match tcx.hir.get_if_local(def_id) { | |
cc61c64b XL |
736 | Some(hir_map::NodeForeignItem(..)) => { |
737 | false // foreign items are linked against, not translated. | |
738 | } | |
739 | Some(_) => true, | |
740 | None => { | |
0531ce1d | 741 | if tcx.is_reachable_non_generic(def_id) || |
83c7162d XL |
742 | tcx.is_foreign_item(def_id) || |
743 | is_available_upstream_generic(tcx, def_id, instance.substs) | |
cc61c64b XL |
744 | { |
745 | // We can link to the item in question, no instance needed | |
746 | // in this crate | |
747 | false | |
32a655c1 | 748 | } else { |
7cac9316 | 749 | if !tcx.is_mir_available(def_id) { |
ff7c6d11 | 750 | bug!("Cannot create local mono-item for {:?}", def_id) |
cc61c64b XL |
751 | } |
752 | true | |
32a655c1 SL |
753 | } |
754 | } | |
83c7162d XL |
755 | }; |
756 | ||
757 | fn is_available_upstream_generic<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
758 | def_id: DefId, | |
759 | substs: &'tcx Substs<'tcx>) | |
760 | -> bool { | |
761 | debug_assert!(!def_id.is_local()); | |
762 | ||
763 | // If we are not in share generics mode, we don't link to upstream | |
764 | // monomorphizations but always instantiate our own internal versions | |
765 | // instead. | |
766 | if !tcx.share_generics() { | |
767 | return false | |
768 | } | |
769 | ||
770 | // If this instance has no type parameters, it cannot be a shared | |
771 | // monomorphization. Non-generic instances are already handled above | |
772 | // by `is_reachable_non_generic()` | |
773 | if substs.types().next().is_none() { | |
774 | return false | |
775 | } | |
776 | ||
777 | // Take a look at the available monomorphizations listed in the metadata | |
778 | // of upstream crates. | |
779 | tcx.upstream_monomorphizations_for(def_id) | |
780 | .map(|set| set.contains_key(substs)) | |
781 | .unwrap_or(false) | |
7453a54e SL |
782 | } |
783 | } | |
784 | ||
785 | /// For given pair of source and target type that occur in an unsizing coercion, | |
786 | /// this function finds the pair of types that determines the vtable linking | |
787 | /// them. | |
788 | /// | |
789 | /// For example, the source type might be `&SomeStruct` and the target type\ | |
790 | /// might be `&SomeTrait` in a cast like: | |
791 | /// | |
792 | /// let src: &SomeStruct = ...; | |
793 | /// let target = src as &SomeTrait; | |
794 | /// | |
795 | /// Then the output of this function would be (SomeStruct, SomeTrait) since for | |
796 | /// constructing the `target` fat-pointer we need the vtable for that pair. | |
797 | /// | |
798 | /// Things can get more complicated though because there's also the case where | |
799 | /// the unsized type occurs as a field: | |
800 | /// | |
801 | /// ```rust | |
802 | /// struct ComplexStruct<T: ?Sized> { | |
803 | /// a: u32, | |
804 | /// b: f64, | |
805 | /// c: T | |
806 | /// } | |
807 | /// ``` | |
808 | /// | |
809 | /// In this case, if `T` is sized, `&ComplexStruct<T>` is a thin pointer. If `T` | |
810 | /// is unsized, `&SomeStruct` is a fat pointer, and the vtable it points to is | |
811 | /// for the pair of `T` (which is a trait) and the concrete type that `T` was | |
812 | /// originally coerced from: | |
813 | /// | |
814 | /// let src: &ComplexStruct<SomeStruct> = ...; | |
815 | /// let target = src as &ComplexStruct<SomeTrait>; | |
816 | /// | |
817 | /// Again, we want this `find_vtable_types_for_unsizing()` to provide the pair | |
818 | /// `(SomeStruct, SomeTrait)`. | |
819 | /// | |
820 | /// Finally, there is also the case of custom unsizing coercions, e.g. for | |
821 | /// smart pointers such as `Rc` and `Arc`. | |
ea8adc8c XL |
822 | fn find_vtable_types_for_unsizing<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
823 | source_ty: Ty<'tcx>, | |
824 | target_ty: Ty<'tcx>) | |
825 | -> (Ty<'tcx>, Ty<'tcx>) { | |
826 | let ptr_vtable = |inner_source: Ty<'tcx>, inner_target: Ty<'tcx>| { | |
ff7c6d11 XL |
827 | let type_has_metadata = |ty: Ty<'tcx>| -> bool { |
828 | use syntax_pos::DUMMY_SP; | |
0531ce1d | 829 | if ty.is_sized(tcx.at(DUMMY_SP), ty::ParamEnv::reveal_all()) { |
ff7c6d11 XL |
830 | return false; |
831 | } | |
832 | let tail = tcx.struct_tail(ty); | |
833 | match tail.sty { | |
834 | ty::TyForeign(..) => false, | |
835 | ty::TyStr | ty::TySlice(..) | ty::TyDynamic(..) => true, | |
836 | _ => bug!("unexpected unsized tail: {:?}", tail.sty), | |
837 | } | |
838 | }; | |
839 | if type_has_metadata(inner_source) { | |
32a655c1 SL |
840 | (inner_source, inner_target) |
841 | } else { | |
ea8adc8c | 842 | tcx.struct_lockstep_tails(inner_source, inner_target) |
32a655c1 SL |
843 | } |
844 | }; | |
ff7c6d11 | 845 | |
7453a54e | 846 | match (&source_ty.sty, &target_ty.sty) { |
7453a54e SL |
847 | (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), |
848 | &ty::TyRef(_, ty::TypeAndMut { ty: b, .. })) | | |
849 | (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), | |
850 | &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) | | |
851 | (&ty::TyRawPtr(ty::TypeAndMut { ty: a, .. }), | |
852 | &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) => { | |
32a655c1 SL |
853 | ptr_vtable(a, b) |
854 | } | |
855 | (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) if def_a.is_box() && def_b.is_box() => { | |
856 | ptr_vtable(source_ty.boxed_ty(), target_ty.boxed_ty()) | |
7453a54e SL |
857 | } |
858 | ||
9e0c209e SL |
859 | (&ty::TyAdt(source_adt_def, source_substs), |
860 | &ty::TyAdt(target_adt_def, target_substs)) => { | |
7453a54e SL |
861 | assert_eq!(source_adt_def, target_adt_def); |
862 | ||
cc61c64b | 863 | let kind = |
ea8adc8c | 864 | monomorphize::custom_coerce_unsize_info(tcx, source_ty, target_ty); |
7453a54e SL |
865 | |
866 | let coerce_index = match kind { | |
867 | CustomCoerceUnsized::Struct(i) => i | |
868 | }; | |
869 | ||
2c00a5a8 XL |
870 | let source_fields = &source_adt_def.non_enum_variant().fields; |
871 | let target_fields = &target_adt_def.non_enum_variant().fields; | |
7453a54e SL |
872 | |
873 | assert!(coerce_index < source_fields.len() && | |
874 | source_fields.len() == target_fields.len()); | |
875 | ||
ea8adc8c XL |
876 | find_vtable_types_for_unsizing(tcx, |
877 | source_fields[coerce_index].ty(tcx, | |
7453a54e | 878 | source_substs), |
ea8adc8c | 879 | target_fields[coerce_index].ty(tcx, |
7453a54e SL |
880 | target_substs)) |
881 | } | |
54a0048b SL |
882 | _ => bug!("find_vtable_types_for_unsizing: invalid coercion {:?} -> {:?}", |
883 | source_ty, | |
884 | target_ty) | |
7453a54e SL |
885 | } |
886 | } | |
887 | ||
ff7c6d11 XL |
888 | fn create_fn_mono_item<'a, 'tcx>(instance: Instance<'tcx>) -> MonoItem<'tcx> { |
889 | debug!("create_fn_mono_item(instance={})", instance); | |
890 | MonoItem::Fn(instance) | |
7453a54e SL |
891 | } |
892 | ||
ff7c6d11 | 893 | /// Creates a `MonoItem` for each method that is referenced by the vtable for |
7453a54e | 894 | /// the given trait/impl pair. |
ff7c6d11 XL |
895 | fn create_mono_items_for_vtable_methods<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
896 | trait_ty: Ty<'tcx>, | |
897 | impl_ty: Ty<'tcx>, | |
898 | output: &mut Vec<MonoItem<'tcx>>) { | |
8bb4bdeb XL |
899 | assert!(!trait_ty.needs_subst() && !trait_ty.has_escaping_regions() && |
900 | !impl_ty.needs_subst() && !impl_ty.has_escaping_regions()); | |
7453a54e | 901 | |
476ff2be SL |
902 | if let ty::TyDynamic(ref trait_ty, ..) = trait_ty.sty { |
903 | if let Some(principal) = trait_ty.principal() { | |
ea8adc8c | 904 | let poly_trait_ref = principal.with_self_ty(tcx, impl_ty); |
8bb4bdeb XL |
905 | assert!(!poly_trait_ref.has_escaping_regions()); |
906 | ||
476ff2be | 907 | // Walk all methods of the trait, including those of its supertraits |
abe05a73 XL |
908 | let methods = tcx.vtable_methods(poly_trait_ref); |
909 | let methods = methods.iter().cloned().filter_map(|method| method) | |
ea8adc8c XL |
910 | .map(|(def_id, substs)| ty::Instance::resolve( |
911 | tcx, | |
0531ce1d | 912 | ty::ParamEnv::reveal_all(), |
ea8adc8c XL |
913 | def_id, |
914 | substs).unwrap()) | |
ff7c6d11 XL |
915 | .filter(|&instance| should_monomorphize_locally(tcx, &instance)) |
916 | .map(|instance| create_fn_mono_item(instance)); | |
476ff2be SL |
917 | output.extend(methods); |
918 | } | |
9e0c209e | 919 | // Also add the destructor |
ea8adc8c | 920 | visit_drop_use(tcx, impl_ty, false, output); |
7453a54e SL |
921 | } |
922 | } | |
923 | ||
924 | //=----------------------------------------------------------------------------- | |
925 | // Root Collection | |
926 | //=----------------------------------------------------------------------------- | |
927 | ||
928 | struct RootCollector<'b, 'a: 'b, 'tcx: 'a + 'b> { | |
ea8adc8c | 929 | tcx: TyCtxt<'a, 'tcx, 'tcx>, |
ff7c6d11 XL |
930 | mode: MonoItemCollectionMode, |
931 | output: &'b mut Vec<MonoItem<'tcx>>, | |
abe05a73 | 932 | entry_fn: Option<DefId>, |
7453a54e SL |
933 | } |
934 | ||
476ff2be | 935 | impl<'b, 'a, 'v> ItemLikeVisitor<'v> for RootCollector<'b, 'a, 'v> { |
7453a54e | 936 | fn visit_item(&mut self, item: &'v hir::Item) { |
7453a54e SL |
937 | match item.node { |
938 | hir::ItemExternCrate(..) | | |
939 | hir::ItemUse(..) | | |
940 | hir::ItemForeignMod(..) | | |
941 | hir::ItemTy(..) | | |
7453a54e | 942 | hir::ItemTrait(..) | |
ff7c6d11 | 943 | hir::ItemTraitAlias(..) | |
7453a54e SL |
944 | hir::ItemMod(..) => { |
945 | // Nothing to do, just keep recursing... | |
946 | } | |
947 | ||
948 | hir::ItemImpl(..) => { | |
ff7c6d11 XL |
949 | if self.mode == MonoItemCollectionMode::Eager { |
950 | create_mono_items_for_default_impls(self.tcx, | |
951 | item, | |
952 | self.output); | |
7453a54e SL |
953 | } |
954 | } | |
955 | ||
9e0c209e SL |
956 | hir::ItemEnum(_, ref generics) | |
957 | hir::ItemStruct(_, ref generics) | | |
958 | hir::ItemUnion(_, ref generics) => { | |
ff7c6d11 XL |
959 | if generics.params.is_empty() { |
960 | if self.mode == MonoItemCollectionMode::Eager { | |
ea8adc8c | 961 | let def_id = self.tcx.hir.local_def_id(item.id); |
7453a54e | 962 | debug!("RootCollector: ADT drop-glue for {}", |
ea8adc8c | 963 | def_id_to_string(self.tcx, def_id)); |
7453a54e | 964 | |
ff7c6d11 | 965 | let ty = Instance::new(def_id, Substs::empty()).ty(self.tcx); |
ea8adc8c | 966 | visit_drop_use(self.tcx, ty, true, self.output); |
7453a54e SL |
967 | } |
968 | } | |
969 | } | |
cc61c64b XL |
970 | hir::ItemGlobalAsm(..) => { |
971 | debug!("RootCollector: ItemGlobalAsm({})", | |
ea8adc8c XL |
972 | def_id_to_string(self.tcx, |
973 | self.tcx.hir.local_def_id(item.id))); | |
ff7c6d11 | 974 | self.output.push(MonoItem::GlobalAsm(item.id)); |
cc61c64b | 975 | } |
7453a54e | 976 | hir::ItemStatic(..) => { |
0531ce1d | 977 | let def_id = self.tcx.hir.local_def_id(item.id); |
7453a54e | 978 | debug!("RootCollector: ItemStatic({})", |
0531ce1d XL |
979 | def_id_to_string(self.tcx, def_id)); |
980 | self.output.push(MonoItem::Static(def_id)); | |
7453a54e | 981 | } |
5bcae85e | 982 | hir::ItemConst(..) => { |
ff7c6d11 | 983 | // const items only generate mono items if they are |
5bcae85e SL |
984 | // actually used somewhere. Just declaring them is insufficient. |
985 | } | |
3b2f2976 | 986 | hir::ItemFn(..) => { |
ff7c6d11 XL |
987 | let def_id = self.tcx.hir.local_def_id(item.id); |
988 | self.push_if_root(def_id); | |
7453a54e SL |
989 | } |
990 | } | |
7453a54e SL |
991 | } |
992 | ||
32a655c1 SL |
993 | fn visit_trait_item(&mut self, _: &'v hir::TraitItem) { |
994 | // Even if there's a default body with no explicit generics, | |
995 | // it's still generic over some `Self: Trait`, so not a root. | |
996 | } | |
997 | ||
7453a54e SL |
998 | fn visit_impl_item(&mut self, ii: &'v hir::ImplItem) { |
999 | match ii.node { | |
3b2f2976 | 1000 | hir::ImplItemKind::Method(hir::MethodSig { .. }, _) => { |
ff7c6d11 XL |
1001 | let def_id = self.tcx.hir.local_def_id(ii.id); |
1002 | self.push_if_root(def_id); | |
7453a54e SL |
1003 | } |
1004 | _ => { /* Nothing to do here */ } | |
1005 | } | |
7453a54e SL |
1006 | } |
1007 | } | |
1008 | ||
abe05a73 XL |
1009 | impl<'b, 'a, 'v> RootCollector<'b, 'a, 'v> { |
1010 | fn is_root(&self, def_id: DefId) -> bool { | |
1011 | !item_has_type_parameters(self.tcx, def_id) && match self.mode { | |
ff7c6d11 | 1012 | MonoItemCollectionMode::Eager => { |
abe05a73 XL |
1013 | true |
1014 | } | |
ff7c6d11 | 1015 | MonoItemCollectionMode::Lazy => { |
abe05a73 | 1016 | self.entry_fn == Some(def_id) || |
0531ce1d XL |
1017 | self.tcx.is_reachable_non_generic(def_id) || |
1018 | self.tcx.trans_fn_attrs(def_id).flags.contains( | |
1019 | TransFnAttrFlags::RUSTC_STD_INTERNAL_SYMBOL) | |
abe05a73 XL |
1020 | } |
1021 | } | |
1022 | } | |
ff7c6d11 XL |
1023 | |
1024 | /// If `def_id` represents a root, then push it onto the list of | |
1025 | /// outputs. (Note that all roots must be monomorphic.) | |
1026 | fn push_if_root(&mut self, def_id: DefId) { | |
1027 | if self.is_root(def_id) { | |
1028 | debug!("RootCollector::push_if_root: found root def_id={:?}", def_id); | |
1029 | ||
1030 | let instance = Instance::mono(self.tcx, def_id); | |
1031 | self.output.push(create_fn_mono_item(instance)); | |
ff7c6d11 XL |
1032 | } |
1033 | } | |
1034 | ||
1035 | /// As a special case, when/if we encounter the | |
1036 | /// `main()` function, we also have to generate a | |
1037 | /// monomorphized copy of the start lang item based on | |
1038 | /// the return type of `main`. This is not needed when | |
1039 | /// the user writes their own `start` manually. | |
0531ce1d | 1040 | fn push_extra_entry_roots(&mut self) { |
83c7162d | 1041 | if self.tcx.sess.entry_fn.get().map(|e| e.2) != Some(config::EntryMain) { |
0531ce1d | 1042 | return |
ff7c6d11 XL |
1043 | } |
1044 | ||
0531ce1d XL |
1045 | let main_def_id = if let Some(def_id) = self.entry_fn { |
1046 | def_id | |
1047 | } else { | |
1048 | return | |
1049 | }; | |
1050 | ||
ff7c6d11 XL |
1051 | let start_def_id = match self.tcx.lang_items().require(StartFnLangItem) { |
1052 | Ok(s) => s, | |
1053 | Err(err) => self.tcx.sess.fatal(&err), | |
1054 | }; | |
0531ce1d | 1055 | let main_ret_ty = self.tcx.fn_sig(main_def_id).output(); |
ff7c6d11 XL |
1056 | |
1057 | // Given that `main()` has no arguments, | |
1058 | // then its return type cannot have | |
1059 | // late-bound regions, since late-bound | |
1060 | // regions must appear in the argument | |
1061 | // listing. | |
0531ce1d XL |
1062 | let main_ret_ty = self.tcx.erase_regions( |
1063 | &main_ret_ty.no_late_bound_regions().unwrap(), | |
1064 | ); | |
ff7c6d11 XL |
1065 | |
1066 | let start_instance = Instance::resolve( | |
1067 | self.tcx, | |
0531ce1d | 1068 | ty::ParamEnv::reveal_all(), |
ff7c6d11 | 1069 | start_def_id, |
0531ce1d | 1070 | self.tcx.intern_substs(&[Kind::from(main_ret_ty)]) |
ff7c6d11 XL |
1071 | ).unwrap(); |
1072 | ||
1073 | self.output.push(create_fn_mono_item(start_instance)); | |
1074 | } | |
abe05a73 XL |
1075 | } |
1076 | ||
3b2f2976 XL |
1077 | fn item_has_type_parameters<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> bool { |
1078 | let generics = tcx.generics_of(def_id); | |
1079 | generics.parent_types as usize + generics.types.len() > 0 | |
1080 | } | |
1081 | ||
ff7c6d11 XL |
1082 | fn create_mono_items_for_default_impls<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
1083 | item: &'tcx hir::Item, | |
1084 | output: &mut Vec<MonoItem<'tcx>>) { | |
7453a54e SL |
1085 | match item.node { |
1086 | hir::ItemImpl(_, | |
7cac9316 | 1087 | _, |
7453a54e SL |
1088 | _, |
1089 | ref generics, | |
9e0c209e | 1090 | .., |
476ff2be | 1091 | ref impl_item_refs) => { |
7453a54e SL |
1092 | if generics.is_type_parameterized() { |
1093 | return | |
1094 | } | |
1095 | ||
32a655c1 | 1096 | let impl_def_id = tcx.hir.local_def_id(item.id); |
7453a54e | 1097 | |
ff7c6d11 | 1098 | debug!("create_mono_items_for_default_impls(item={})", |
a7813a04 | 1099 | def_id_to_string(tcx, impl_def_id)); |
7453a54e SL |
1100 | |
1101 | if let Some(trait_ref) = tcx.impl_trait_ref(impl_def_id) { | |
476ff2be SL |
1102 | let overridden_methods: FxHashSet<_> = |
1103 | impl_item_refs.iter() | |
1104 | .map(|iiref| iiref.name) | |
1105 | .collect(); | |
9e0c209e SL |
1106 | for method in tcx.provided_trait_methods(trait_ref.def_id) { |
1107 | if overridden_methods.contains(&method.name) { | |
7453a54e SL |
1108 | continue; |
1109 | } | |
1110 | ||
7cac9316 | 1111 | if !tcx.generics_of(method.def_id).types.is_empty() { |
7453a54e SL |
1112 | continue; |
1113 | } | |
1114 | ||
0531ce1d XL |
1115 | let substs = Substs::for_item(tcx, |
1116 | method.def_id, | |
1117 | |_, _| tcx.types.re_erased, | |
1118 | |def, _| trait_ref.substs.type_for_def(def)); | |
1119 | ||
ea8adc8c | 1120 | let instance = ty::Instance::resolve(tcx, |
0531ce1d | 1121 | ty::ParamEnv::reveal_all(), |
ea8adc8c | 1122 | method.def_id, |
0531ce1d | 1123 | substs).unwrap(); |
cc61c64b | 1124 | |
ff7c6d11 XL |
1125 | let mono_item = create_fn_mono_item(instance); |
1126 | if mono_item.is_instantiable(tcx) | |
1127 | && should_monomorphize_locally(tcx, &instance) { | |
1128 | output.push(mono_item); | |
7453a54e SL |
1129 | } |
1130 | } | |
1131 | } | |
1132 | } | |
1133 | _ => { | |
54a0048b | 1134 | bug!() |
7453a54e SL |
1135 | } |
1136 | } | |
1137 | } | |
1138 | ||
0531ce1d XL |
1139 | /// Scan the miri alloc in order to find function calls, closures, and drop-glue |
1140 | fn collect_miri<'a, 'tcx>( | |
1141 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1142 | alloc_id: AllocId, | |
1143 | output: &mut Vec<MonoItem<'tcx>>, | |
1144 | ) { | |
1145 | if let Some(did) = tcx.interpret_interner.get_static(alloc_id) { | |
1146 | let instance = Instance::mono(tcx, did); | |
1147 | if should_monomorphize_locally(tcx, &instance) { | |
1148 | trace!("collecting static {:?}", did); | |
1149 | output.push(MonoItem::Static(did)); | |
1150 | } | |
1151 | } else if let Some(alloc) = tcx.interpret_interner.get_alloc(alloc_id) { | |
1152 | trace!("collecting {:?} with {:#?}", alloc_id, alloc); | |
1153 | for &inner in alloc.relocations.values() { | |
1154 | collect_miri(tcx, inner, output); | |
1155 | } | |
1156 | } else if let Some(fn_instance) = tcx.interpret_interner.get_fn(alloc_id) { | |
1157 | if should_monomorphize_locally(tcx, &fn_instance) { | |
1158 | trace!("collecting {:?} with {:#?}", alloc_id, fn_instance); | |
1159 | output.push(create_fn_mono_item(fn_instance)); | |
1160 | } | |
1161 | } else { | |
1162 | bug!("alloc id without corresponding allocation: {}", alloc_id); | |
1163 | } | |
1164 | } | |
1165 | ||
32a655c1 | 1166 | /// Scan the MIR in order to find function calls, closures, and drop-glue |
ea8adc8c | 1167 | fn collect_neighbours<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
32a655c1 | 1168 | instance: Instance<'tcx>, |
ff7c6d11 | 1169 | output: &mut Vec<MonoItem<'tcx>>) |
5bcae85e | 1170 | { |
ea8adc8c | 1171 | let mir = tcx.instance_mir(instance.def); |
5bcae85e | 1172 | |
0531ce1d | 1173 | MirNeighborCollector { |
ea8adc8c | 1174 | tcx, |
5bcae85e | 1175 | mir: &mir, |
3b2f2976 XL |
1176 | output, |
1177 | param_substs: instance.substs, | |
0531ce1d XL |
1178 | }.visit_mir(&mir); |
1179 | let param_env = ty::ParamEnv::reveal_all(); | |
1180 | for i in 0..mir.promoted.len() { | |
1181 | use rustc_data_structures::indexed_vec::Idx; | |
1182 | let cid = GlobalId { | |
1183 | instance, | |
1184 | promoted: Some(Promoted::new(i)), | |
1185 | }; | |
1186 | match tcx.const_eval(param_env.and(cid)) { | |
1187 | Ok(val) => collect_const(tcx, val, instance.substs, output), | |
1188 | Err(_) => {}, | |
1189 | } | |
7453a54e SL |
1190 | } |
1191 | } | |
476ff2be SL |
1192 | |
1193 | fn def_id_to_string<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1194 | def_id: DefId) | |
1195 | -> String { | |
1196 | let mut output = String::new(); | |
1197 | let printer = DefPathBasedNames::new(tcx, false, false); | |
1198 | printer.push_def_path(def_id, &mut output); | |
1199 | output | |
1200 | } | |
0531ce1d XL |
1201 | |
1202 | fn collect_const<'a, 'tcx>( | |
1203 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
1204 | constant: &ty::Const<'tcx>, | |
1205 | param_substs: &'tcx Substs<'tcx>, | |
1206 | output: &mut Vec<MonoItem<'tcx>>, | |
1207 | ) { | |
1208 | debug!("visiting const {:?}", *constant); | |
1209 | ||
1210 | let val = match constant.val { | |
1211 | ConstVal::Unevaluated(def_id, substs) => { | |
1212 | let param_env = ty::ParamEnv::reveal_all(); | |
1213 | let substs = tcx.subst_and_normalize_erasing_regions( | |
1214 | param_substs, | |
1215 | param_env, | |
1216 | &substs, | |
1217 | ); | |
1218 | let instance = ty::Instance::resolve(tcx, | |
1219 | param_env, | |
1220 | def_id, | |
1221 | substs).unwrap(); | |
1222 | ||
1223 | let cid = GlobalId { | |
1224 | instance, | |
1225 | promoted: None, | |
1226 | }; | |
1227 | match tcx.const_eval(param_env.and(cid)) { | |
1228 | Ok(val) => val.val, | |
1229 | Err(err) => { | |
1230 | let span = tcx.def_span(def_id); | |
1231 | err.report(tcx, span, "constant"); | |
1232 | return; | |
1233 | } | |
1234 | } | |
1235 | }, | |
1236 | _ => constant.val, | |
1237 | }; | |
1238 | match val { | |
1239 | ConstVal::Unevaluated(..) => bug!("const eval yielded unevaluated const"), | |
1240 | ConstVal::Value(Value::ByValPair(PrimVal::Ptr(a), PrimVal::Ptr(b))) => { | |
1241 | collect_miri(tcx, a.alloc_id, output); | |
1242 | collect_miri(tcx, b.alloc_id, output); | |
1243 | } | |
1244 | ConstVal::Value(Value::ByValPair(_, PrimVal::Ptr(ptr))) | | |
1245 | ConstVal::Value(Value::ByValPair(PrimVal::Ptr(ptr), _)) | | |
1246 | ConstVal::Value(Value::ByVal(PrimVal::Ptr(ptr))) => | |
1247 | collect_miri(tcx, ptr.alloc_id, output), | |
1248 | ConstVal::Value(Value::ByRef(Pointer { primval: PrimVal::Ptr(ptr) }, _)) => { | |
1249 | // by ref should only collect the inner allocation, not the value itself | |
1250 | let alloc = tcx | |
1251 | .interpret_interner | |
1252 | .get_alloc(ptr.alloc_id) | |
1253 | .expect("ByRef to extern static is not allowed"); | |
1254 | for &inner in alloc.relocations.values() { | |
1255 | collect_miri(tcx, inner, output); | |
1256 | } | |
1257 | } | |
1258 | _ => {}, | |
1259 | } | |
1260 | } |