]>
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 | ||
11 | //! Translation Item Collection | |
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 | //! | |
25 | //! The following kinds of "translation items" are handled here: | |
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 | //! | |
46 | //! - A "translation item" is something that results in a function or global in | |
47 | //! the LLVM IR of a codegen unit. Translation items do not stand on their | |
48 | //! own, they can reference other translation items. For example, if function | |
49 | //! `foo()` calls function `bar()` then the translation item for `foo()` | |
50 | //! references the translation item for function `bar()`. In general, the | |
51 | //! definition for translation item A referencing a translation item B is that | |
52 | //! the LLVM artifact produced for A references the LLVM artifact produced | |
53 | //! for B. | |
54 | //! | |
55 | //! - Translation items and the references between them for a directed graph, | |
56 | //! where the translation items are the nodes and references form the edges. | |
57 | //! Let's call this graph the "translation item graph". | |
58 | //! | |
59 | //! - The translation item graph for a program contains all translation items | |
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 | |
63 | //! translation item graph for the current crate. It runs in two phases: | |
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 | //! | |
72 | //! The roots of the translation item graph correspond to the non-generic | |
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 | |
75 | //! create a translation item consisting of the items DefId and, since we only | |
76 | //! consider non-generic items, an empty type-substitution set. | |
77 | //! | |
78 | //! ### Finding neighbor nodes | |
79 | //! Given a translation item node, we can discover neighbors by inspecting its | |
80 | //! MIR. We walk the MIR and any time we hit upon something that signifies a | |
81 | //! reference to another translation item, we have found a neighbor. Since the | |
82 | //! translation item we are currently at is always monomorphic, we also know the | |
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 | |
88 | //! The most obvious form of one translation item referencing another is a | |
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 | |
91 | //! function translation items, and as we will see below, they are just a | |
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 | |
115 | //! `print_val::<i32>`. Nonetheless, in order to translate this program, we need | |
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 | |
118 | //! translation item. Calls are just a special case of that. | |
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 | |
127 | //! Drop glue translation items are introduced by MIR drop-statements. The | |
128 | //! generated translation item will again have drop-glue item neighbors if the | |
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 | |
152 | //! #[inline]. | |
153 | //! The collection algorithm handles this more or less transparently. If it is | |
154 | //! about to create a translation item for something with an external `DefId`, | |
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 | //! ------------------------------ | |
162 | //! Translation item collection can be performed in one of two modes: | |
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 | |
169 | //! where a stable set of translation items is more important than a minimal | |
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 | |
186 | //! Ideally, no translation item should be generated for const fns unless there | |
187 | //! is a call to them that cannot be evaluated at compile time. At the moment | |
188 | //! this is not implemented however: a translation item will be produced | |
189 | //! regardless of whether it is actually needed or not. | |
190 | ||
54a0048b SL |
191 | use rustc::hir; |
192 | use rustc::hir::intravisit as hir_visit; | |
7453a54e | 193 | |
54a0048b SL |
194 | use rustc::hir::map as hir_map; |
195 | use rustc::hir::def_id::DefId; | |
7453a54e | 196 | use rustc::middle::lang_items::{ExchangeFreeFnLangItem, ExchangeMallocFnLangItem}; |
54a0048b | 197 | use rustc::traits; |
9e0c209e | 198 | use rustc::ty::subst::{Substs, Subst}; |
a7813a04 | 199 | use rustc::ty::{self, TypeFoldable, TyCtxt}; |
54a0048b | 200 | use rustc::ty::adjustment::CustomCoerceUnsized; |
c30ab7b3 | 201 | use rustc::mir::{self, Location}; |
7453a54e SL |
202 | use rustc::mir::visit as mir_visit; |
203 | use rustc::mir::visit::Visitor as MirVisitor; | |
204 | ||
5bcae85e SL |
205 | use rustc_const_eval as const_eval; |
206 | ||
a7813a04 | 207 | use syntax::abi::Abi; |
3157f602 | 208 | use syntax_pos::DUMMY_SP; |
54a0048b | 209 | use base::custom_coerce_unsize_info; |
a7813a04 | 210 | use context::SharedCrateContext; |
9e0c209e | 211 | use common::{fulfill_obligation, type_is_sized}; |
a7813a04 | 212 | use glue::{self, DropGlueKind}; |
54a0048b | 213 | use monomorphize::{self, Instance}; |
7453a54e SL |
214 | use util::nodemap::{FnvHashSet, FnvHashMap, DefIdMap}; |
215 | ||
a7813a04 | 216 | use trans_item::{TransItem, type_to_string, def_id_to_string}; |
7453a54e SL |
217 | |
218 | #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] | |
219 | pub enum TransItemCollectionMode { | |
220 | Eager, | |
221 | Lazy | |
222 | } | |
223 | ||
a7813a04 XL |
224 | /// Maps every translation item to all translation items it references in its |
225 | /// body. | |
226 | pub struct InliningMap<'tcx> { | |
227 | // Maps a source translation item to a range of target translation items | |
228 | // that are potentially inlined by LLVM into the source. | |
229 | // The two numbers in the tuple are the start (inclusive) and | |
230 | // end index (exclusive) within the `targets` vecs. | |
231 | index: FnvHashMap<TransItem<'tcx>, (usize, usize)>, | |
232 | targets: Vec<TransItem<'tcx>>, | |
7453a54e SL |
233 | } |
234 | ||
a7813a04 XL |
235 | impl<'tcx> InliningMap<'tcx> { |
236 | ||
237 | fn new() -> InliningMap<'tcx> { | |
238 | InliningMap { | |
239 | index: FnvHashMap(), | |
240 | targets: Vec::new(), | |
241 | } | |
242 | } | |
243 | ||
244 | fn record_inlining_canditates<I>(&mut self, | |
245 | source: TransItem<'tcx>, | |
246 | targets: I) | |
247 | where I: Iterator<Item=TransItem<'tcx>> | |
248 | { | |
249 | assert!(!self.index.contains_key(&source)); | |
250 | ||
251 | let start_index = self.targets.len(); | |
252 | self.targets.extend(targets); | |
253 | let end_index = self.targets.len(); | |
254 | self.index.insert(source, (start_index, end_index)); | |
255 | } | |
256 | ||
257 | // Internally iterate over all items referenced by `source` which will be | |
258 | // made available for inlining. | |
259 | pub fn with_inlining_candidates<F>(&self, source: TransItem<'tcx>, mut f: F) | |
260 | where F: FnMut(TransItem<'tcx>) { | |
261 | if let Some(&(start_index, end_index)) = self.index.get(&source) | |
262 | { | |
263 | for candidate in &self.targets[start_index .. end_index] { | |
264 | f(*candidate) | |
7453a54e | 265 | } |
a7813a04 | 266 | } |
7453a54e SL |
267 | } |
268 | } | |
269 | ||
a7813a04 | 270 | pub fn collect_crate_translation_items<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e | 271 | mode: TransItemCollectionMode) |
a7813a04 XL |
272 | -> (FnvHashSet<TransItem<'tcx>>, |
273 | InliningMap<'tcx>) { | |
7453a54e SL |
274 | // We are not tracking dependencies of this pass as it has to be re-executed |
275 | // every time no matter what. | |
a7813a04 XL |
276 | scx.tcx().dep_graph.with_ignore(|| { |
277 | let roots = collect_roots(scx, mode); | |
7453a54e SL |
278 | |
279 | debug!("Building translation item graph, beginning at roots"); | |
280 | let mut visited = FnvHashSet(); | |
281 | let mut recursion_depths = DefIdMap(); | |
a7813a04 | 282 | let mut inlining_map = InliningMap::new(); |
7453a54e SL |
283 | |
284 | for root in roots { | |
a7813a04 XL |
285 | collect_items_rec(scx, |
286 | root, | |
287 | &mut visited, | |
288 | &mut recursion_depths, | |
289 | &mut inlining_map); | |
7453a54e SL |
290 | } |
291 | ||
a7813a04 | 292 | (visited, inlining_map) |
7453a54e SL |
293 | }) |
294 | } | |
295 | ||
296 | // Find all non-generic items by walking the HIR. These items serve as roots to | |
297 | // start monomorphizing from. | |
a7813a04 | 298 | fn collect_roots<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
299 | mode: TransItemCollectionMode) |
300 | -> Vec<TransItem<'tcx>> { | |
301 | debug!("Collecting roots"); | |
302 | let mut roots = Vec::new(); | |
303 | ||
304 | { | |
305 | let mut visitor = RootCollector { | |
a7813a04 | 306 | scx: scx, |
7453a54e SL |
307 | mode: mode, |
308 | output: &mut roots, | |
309 | enclosing_item: None, | |
7453a54e SL |
310 | }; |
311 | ||
a7813a04 | 312 | scx.tcx().map.krate().visit_all_items(&mut visitor); |
7453a54e SL |
313 | } |
314 | ||
315 | roots | |
316 | } | |
317 | ||
7453a54e | 318 | // Collect all monomorphized translation items reachable from `starting_point` |
a7813a04 | 319 | fn collect_items_rec<'a, 'tcx: 'a>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
320 | starting_point: TransItem<'tcx>, |
321 | visited: &mut FnvHashSet<TransItem<'tcx>>, | |
a7813a04 XL |
322 | recursion_depths: &mut DefIdMap<usize>, |
323 | inlining_map: &mut InliningMap<'tcx>) { | |
7453a54e SL |
324 | if !visited.insert(starting_point.clone()) { |
325 | // We've been here already, no need to search again. | |
326 | return; | |
327 | } | |
a7813a04 | 328 | debug!("BEGIN collect_items_rec({})", starting_point.to_string(scx.tcx())); |
7453a54e SL |
329 | |
330 | let mut neighbors = Vec::new(); | |
331 | let recursion_depth_reset; | |
332 | ||
333 | match starting_point { | |
334 | TransItem::DropGlue(t) => { | |
a7813a04 | 335 | find_drop_glue_neighbors(scx, t, &mut neighbors); |
7453a54e SL |
336 | recursion_depth_reset = None; |
337 | } | |
a7813a04 XL |
338 | TransItem::Static(node_id) => { |
339 | let def_id = scx.tcx().map.local_def_id(node_id); | |
340 | let ty = scx.tcx().lookup_item_type(def_id).ty; | |
341 | let ty = glue::get_drop_glue_type(scx.tcx(), ty); | |
342 | neighbors.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); | |
343 | ||
7453a54e | 344 | recursion_depth_reset = None; |
a7813a04 XL |
345 | |
346 | // Scan the MIR in order to find function calls, closures, and | |
347 | // drop-glue | |
c30ab7b3 | 348 | let mir = scx.tcx().item_mir(def_id); |
a7813a04 XL |
349 | |
350 | let empty_substs = scx.empty_substs_for_def_id(def_id); | |
5bcae85e | 351 | let visitor = MirNeighborCollector { |
a7813a04 XL |
352 | scx: scx, |
353 | mir: &mir, | |
354 | output: &mut neighbors, | |
355 | param_substs: empty_substs | |
356 | }; | |
357 | ||
5bcae85e | 358 | visit_mir_and_promoted(visitor, &mir); |
7453a54e | 359 | } |
54a0048b | 360 | TransItem::Fn(instance) => { |
7453a54e | 361 | // Keep track of the monomorphization recursion depth |
a7813a04 | 362 | recursion_depth_reset = Some(check_recursion_limit(scx.tcx(), |
54a0048b | 363 | instance, |
7453a54e SL |
364 | recursion_depths)); |
365 | ||
366 | // Scan the MIR in order to find function calls, closures, and | |
367 | // drop-glue | |
c30ab7b3 | 368 | let mir = scx.tcx().item_mir(instance.def); |
7453a54e | 369 | |
5bcae85e | 370 | let visitor = MirNeighborCollector { |
a7813a04 | 371 | scx: scx, |
54a0048b | 372 | mir: &mir, |
7453a54e | 373 | output: &mut neighbors, |
54a0048b | 374 | param_substs: instance.substs |
7453a54e SL |
375 | }; |
376 | ||
5bcae85e | 377 | visit_mir_and_promoted(visitor, &mir); |
7453a54e SL |
378 | } |
379 | } | |
380 | ||
a7813a04 XL |
381 | record_inlining_canditates(scx.tcx(), starting_point, &neighbors[..], inlining_map); |
382 | ||
7453a54e | 383 | for neighbour in neighbors { |
a7813a04 | 384 | collect_items_rec(scx, neighbour, visited, recursion_depths, inlining_map); |
7453a54e SL |
385 | } |
386 | ||
387 | if let Some((def_id, depth)) = recursion_depth_reset { | |
388 | recursion_depths.insert(def_id, depth); | |
389 | } | |
390 | ||
a7813a04 | 391 | debug!("END collect_items_rec({})", starting_point.to_string(scx.tcx())); |
7453a54e SL |
392 | } |
393 | ||
a7813a04 XL |
394 | fn record_inlining_canditates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
395 | caller: TransItem<'tcx>, | |
396 | callees: &[TransItem<'tcx>], | |
397 | inlining_map: &mut InliningMap<'tcx>) { | |
398 | let is_inlining_candidate = |trans_item: &TransItem<'tcx>| { | |
9e0c209e | 399 | trans_item.needs_local_copy(tcx) |
a7813a04 XL |
400 | }; |
401 | ||
402 | let inlining_candidates = callees.into_iter() | |
403 | .map(|x| *x) | |
404 | .filter(is_inlining_candidate); | |
405 | ||
406 | inlining_map.record_inlining_canditates(caller, inlining_candidates); | |
407 | } | |
408 | ||
409 | fn check_recursion_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
410 | instance: Instance<'tcx>, | |
411 | recursion_depths: &mut DefIdMap<usize>) | |
412 | -> (DefId, usize) { | |
54a0048b | 413 | let recursion_depth = recursion_depths.get(&instance.def) |
7453a54e SL |
414 | .map(|x| *x) |
415 | .unwrap_or(0); | |
416 | debug!(" => recursion depth={}", recursion_depth); | |
417 | ||
418 | // Code that needs to instantiate the same function recursively | |
419 | // more than the recursion limit is assumed to be causing an | |
420 | // infinite expansion. | |
a7813a04 | 421 | if recursion_depth > tcx.sess.recursion_limit.get() { |
54a0048b SL |
422 | let error = format!("reached the recursion limit while instantiating `{}`", |
423 | instance); | |
a7813a04 XL |
424 | if let Some(node_id) = tcx.map.as_local_node_id(instance.def) { |
425 | tcx.sess.span_fatal(tcx.map.span(node_id), &error); | |
7453a54e | 426 | } else { |
a7813a04 | 427 | tcx.sess.fatal(&error); |
7453a54e SL |
428 | } |
429 | } | |
430 | ||
54a0048b | 431 | recursion_depths.insert(instance.def, recursion_depth + 1); |
7453a54e | 432 | |
54a0048b | 433 | (instance.def, recursion_depth) |
7453a54e SL |
434 | } |
435 | ||
436 | struct MirNeighborCollector<'a, 'tcx: 'a> { | |
a7813a04 | 437 | scx: &'a SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
438 | mir: &'a mir::Mir<'tcx>, |
439 | output: &'a mut Vec<TransItem<'tcx>>, | |
440 | param_substs: &'tcx Substs<'tcx> | |
441 | } | |
442 | ||
443 | impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> { | |
444 | ||
9e0c209e | 445 | fn visit_rvalue(&mut self, rvalue: &mir::Rvalue<'tcx>, location: Location) { |
7453a54e SL |
446 | debug!("visiting rvalue {:?}", *rvalue); |
447 | ||
448 | match *rvalue { | |
449 | mir::Rvalue::Aggregate(mir::AggregateKind::Closure(def_id, | |
450 | ref substs), _) => { | |
c30ab7b3 | 451 | let mir = self.scx.tcx().item_mir(def_id); |
5bcae85e | 452 | |
9e0c209e | 453 | let concrete_substs = monomorphize::apply_param_substs(self.scx, |
5bcae85e SL |
454 | self.param_substs, |
455 | &substs.func_substs); | |
456 | let concrete_substs = self.scx.tcx().erase_regions(&concrete_substs); | |
457 | ||
458 | let visitor = MirNeighborCollector { | |
459 | scx: self.scx, | |
460 | mir: &mir, | |
461 | output: self.output, | |
462 | param_substs: concrete_substs | |
463 | }; | |
464 | ||
465 | visit_mir_and_promoted(visitor, &mir); | |
7453a54e SL |
466 | } |
467 | // When doing an cast from a regular pointer to a fat pointer, we | |
468 | // have to instantiate all methods of the trait being cast to, so we | |
469 | // can build the appropriate vtable. | |
470 | mir::Rvalue::Cast(mir::CastKind::Unsize, ref operand, target_ty) => { | |
9e0c209e | 471 | let target_ty = monomorphize::apply_param_substs(self.scx, |
7453a54e SL |
472 | self.param_substs, |
473 | &target_ty); | |
5bcae85e | 474 | let source_ty = operand.ty(self.mir, self.scx.tcx()); |
9e0c209e | 475 | let source_ty = monomorphize::apply_param_substs(self.scx, |
7453a54e SL |
476 | self.param_substs, |
477 | &source_ty); | |
a7813a04 | 478 | let (source_ty, target_ty) = find_vtable_types_for_unsizing(self.scx, |
7453a54e SL |
479 | source_ty, |
480 | target_ty); | |
481 | // This could also be a different Unsize instruction, like | |
482 | // from a fixed sized array to a slice. But we are only | |
483 | // interested in things that produce a vtable. | |
484 | if target_ty.is_trait() && !source_ty.is_trait() { | |
a7813a04 | 485 | create_trans_items_for_vtable_methods(self.scx, |
7453a54e SL |
486 | target_ty, |
487 | source_ty, | |
488 | self.output); | |
489 | } | |
490 | } | |
9e0c209e | 491 | mir::Rvalue::Box(..) => { |
7453a54e | 492 | let exchange_malloc_fn_def_id = |
a7813a04 | 493 | self.scx |
7453a54e SL |
494 | .tcx() |
495 | .lang_items | |
496 | .require(ExchangeMallocFnLangItem) | |
a7813a04 | 497 | .unwrap_or_else(|e| self.scx.sess().fatal(&e)); |
7453a54e | 498 | |
a7813a04 XL |
499 | assert!(can_have_local_instance(self.scx.tcx(), exchange_malloc_fn_def_id)); |
500 | let empty_substs = self.scx.empty_substs_for_def_id(exchange_malloc_fn_def_id); | |
7453a54e | 501 | let exchange_malloc_fn_trans_item = |
9e0c209e | 502 | create_fn_trans_item(self.scx, |
7453a54e | 503 | exchange_malloc_fn_def_id, |
a7813a04 | 504 | empty_substs, |
7453a54e SL |
505 | self.param_substs); |
506 | ||
507 | self.output.push(exchange_malloc_fn_trans_item); | |
508 | } | |
509 | _ => { /* not interesting */ } | |
510 | } | |
511 | ||
9e0c209e | 512 | self.super_rvalue(rvalue, location); |
7453a54e SL |
513 | } |
514 | ||
515 | fn visit_lvalue(&mut self, | |
516 | lvalue: &mir::Lvalue<'tcx>, | |
9e0c209e SL |
517 | context: mir_visit::LvalueContext<'tcx>, |
518 | location: Location) { | |
7453a54e SL |
519 | debug!("visiting lvalue {:?}", *lvalue); |
520 | ||
521 | if let mir_visit::LvalueContext::Drop = context { | |
5bcae85e SL |
522 | let ty = lvalue.ty(self.mir, self.scx.tcx()) |
523 | .to_ty(self.scx.tcx()); | |
7453a54e | 524 | |
9e0c209e | 525 | let ty = monomorphize::apply_param_substs(self.scx, |
7453a54e SL |
526 | self.param_substs, |
527 | &ty); | |
3157f602 | 528 | assert!(ty.is_normalized_for_trans()); |
a7813a04 XL |
529 | let ty = glue::get_drop_glue_type(self.scx.tcx(), ty); |
530 | self.output.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); | |
7453a54e SL |
531 | } |
532 | ||
9e0c209e | 533 | self.super_lvalue(lvalue, context, location); |
7453a54e SL |
534 | } |
535 | ||
9e0c209e | 536 | fn visit_operand(&mut self, operand: &mir::Operand<'tcx>, location: Location) { |
7453a54e SL |
537 | debug!("visiting operand {:?}", *operand); |
538 | ||
539 | let callee = match *operand { | |
5bcae85e SL |
540 | mir::Operand::Constant(ref constant) => { |
541 | if let ty::TyFnDef(def_id, substs, _) = constant.ty.sty { | |
542 | // This is something that can act as a callee, proceed | |
543 | Some((def_id, substs)) | |
544 | } else { | |
545 | // This is not a callee, but we still have to look for | |
546 | // references to `const` items | |
547 | if let mir::Literal::Item { def_id, substs } = constant.literal { | |
548 | let tcx = self.scx.tcx(); | |
9e0c209e | 549 | let substs = monomorphize::apply_param_substs(self.scx, |
5bcae85e SL |
550 | self.param_substs, |
551 | &substs); | |
552 | ||
553 | // If the constant referred to here is an associated | |
554 | // item of a trait, we need to resolve it to the actual | |
555 | // constant in the corresponding impl. Luckily | |
556 | // const_eval::lookup_const_by_id() does that for us. | |
557 | if let Some((expr, _)) = const_eval::lookup_const_by_id(tcx, | |
558 | def_id, | |
559 | Some(substs)) { | |
560 | // The hir::Expr we get here is the initializer of | |
561 | // the constant, what we really want is the item | |
562 | // DefId. | |
563 | let const_node_id = tcx.map.get_parent(expr.id); | |
564 | let def_id = if tcx.map.is_inlined_node_id(const_node_id) { | |
565 | tcx.sess.cstore.defid_for_inlined_node(const_node_id).unwrap() | |
566 | } else { | |
567 | tcx.map.local_def_id(const_node_id) | |
568 | }; | |
569 | ||
570 | collect_const_item_neighbours(self.scx, | |
571 | def_id, | |
572 | substs, | |
573 | self.output); | |
574 | } | |
575 | } | |
576 | ||
577 | None | |
578 | } | |
579 | } | |
7453a54e SL |
580 | _ => None |
581 | }; | |
582 | ||
583 | if let Some((callee_def_id, callee_substs)) = callee { | |
584 | debug!(" => operand is callable"); | |
585 | ||
586 | // `callee_def_id` might refer to a trait method instead of a | |
587 | // concrete implementation, so we have to find the actual | |
588 | // implementation. For example, the call might look like | |
589 | // | |
590 | // std::cmp::partial_cmp(0i32, 1i32) | |
591 | // | |
592 | // Calling do_static_dispatch() here will map the def_id of | |
593 | // `std::cmp::partial_cmp` to the def_id of `i32::partial_cmp<i32>` | |
a7813a04 | 594 | let dispatched = do_static_dispatch(self.scx, |
7453a54e SL |
595 | callee_def_id, |
596 | callee_substs, | |
597 | self.param_substs); | |
598 | ||
599 | if let Some((callee_def_id, callee_substs)) = dispatched { | |
600 | // if we have a concrete impl (which we might not have | |
601 | // in the case of something compiler generated like an | |
602 | // object shim or a closure that is handled differently), | |
603 | // we check if the callee is something that will actually | |
604 | // result in a translation item ... | |
a7813a04 | 605 | if can_result_in_trans_item(self.scx.tcx(), callee_def_id) { |
7453a54e | 606 | // ... and create one if it does. |
9e0c209e | 607 | let trans_item = create_fn_trans_item(self.scx, |
7453a54e SL |
608 | callee_def_id, |
609 | callee_substs, | |
610 | self.param_substs); | |
611 | self.output.push(trans_item); | |
612 | } | |
613 | } | |
614 | } | |
615 | ||
9e0c209e | 616 | self.super_operand(operand, location); |
7453a54e | 617 | |
a7813a04 | 618 | fn can_result_in_trans_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
7453a54e SL |
619 | def_id: DefId) |
620 | -> bool { | |
9e0c209e SL |
621 | match tcx.lookup_item_type(def_id).ty.sty { |
622 | ty::TyFnDef(def_id, _, f) => { | |
54a0048b | 623 | // Some constructors also have type TyFnDef but they are |
7453a54e | 624 | // always instantiated inline and don't result in |
54a0048b | 625 | // translation item. Same for FFI functions. |
9e0c209e SL |
626 | if let Some(hir_map::NodeForeignItem(_)) = tcx.map.get_if_local(def_id) { |
627 | return false; | |
628 | } | |
629 | ||
630 | if let Some(adt_def) = f.sig.output().skip_binder().ty_adt_def() { | |
631 | if adt_def.variants.iter().any(|v| def_id == v.did) { | |
632 | return false; | |
7453a54e SL |
633 | } |
634 | } | |
635 | } | |
9e0c209e SL |
636 | ty::TyClosure(..) => {} |
637 | _ => return false | |
7453a54e SL |
638 | } |
639 | ||
a7813a04 XL |
640 | can_have_local_instance(tcx, def_id) |
641 | } | |
642 | } | |
643 | ||
644 | // This takes care of the "drop_in_place" intrinsic for which we otherwise | |
645 | // we would not register drop-glues. | |
646 | fn visit_terminator_kind(&mut self, | |
647 | block: mir::BasicBlock, | |
9e0c209e SL |
648 | kind: &mir::TerminatorKind<'tcx>, |
649 | location: Location) { | |
a7813a04 XL |
650 | let tcx = self.scx.tcx(); |
651 | match *kind { | |
652 | mir::TerminatorKind::Call { | |
653 | func: mir::Operand::Constant(ref constant), | |
654 | ref args, | |
655 | .. | |
656 | } => { | |
657 | match constant.ty.sty { | |
658 | ty::TyFnDef(def_id, _, bare_fn_ty) | |
659 | if is_drop_in_place_intrinsic(tcx, def_id, bare_fn_ty) => { | |
5bcae85e | 660 | let operand_ty = args[0].ty(self.mir, tcx); |
a7813a04 | 661 | if let ty::TyRawPtr(mt) = operand_ty.sty { |
9e0c209e | 662 | let operand_ty = monomorphize::apply_param_substs(self.scx, |
a7813a04 XL |
663 | self.param_substs, |
664 | &mt.ty); | |
5bcae85e SL |
665 | let ty = glue::get_drop_glue_type(tcx, operand_ty); |
666 | self.output.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); | |
a7813a04 XL |
667 | } else { |
668 | bug!("Has the drop_in_place() intrinsic's signature changed?") | |
669 | } | |
670 | } | |
671 | _ => { /* Nothing to do. */ } | |
672 | } | |
673 | } | |
674 | _ => { /* Nothing to do. */ } | |
675 | } | |
676 | ||
9e0c209e | 677 | self.super_terminator_kind(block, kind, location); |
a7813a04 XL |
678 | |
679 | fn is_drop_in_place_intrinsic<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
680 | def_id: DefId, | |
681 | bare_fn_ty: &ty::BareFnTy<'tcx>) | |
682 | -> bool { | |
683 | (bare_fn_ty.abi == Abi::RustIntrinsic || | |
684 | bare_fn_ty.abi == Abi::PlatformIntrinsic) && | |
685 | tcx.item_name(def_id).as_str() == "drop_in_place" | |
7453a54e SL |
686 | } |
687 | } | |
688 | } | |
689 | ||
a7813a04 | 690 | fn can_have_local_instance<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
7453a54e SL |
691 | def_id: DefId) |
692 | -> bool { | |
693 | // Take a look if we have the definition available. If not, we | |
694 | // will not emit code for this item in the local crate, and thus | |
695 | // don't create a translation item for it. | |
a7813a04 | 696 | def_id.is_local() || tcx.sess.cstore.is_item_mir_available(def_id) |
7453a54e SL |
697 | } |
698 | ||
a7813a04 XL |
699 | fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
700 | dg: DropGlueKind<'tcx>, | |
701 | output: &mut Vec<TransItem<'tcx>>) { | |
702 | let ty = match dg { | |
703 | DropGlueKind::Ty(ty) => ty, | |
704 | DropGlueKind::TyContents(_) => { | |
705 | // We already collected the neighbors of this item via the | |
706 | // DropGlueKind::Ty variant. | |
707 | return | |
708 | } | |
709 | }; | |
710 | ||
711 | debug!("find_drop_glue_neighbors: {}", type_to_string(scx.tcx(), ty)); | |
7453a54e SL |
712 | |
713 | // Make sure the exchange_free_fn() lang-item gets translated if | |
714 | // there is a boxed value. | |
715 | if let ty::TyBox(_) = ty.sty { | |
a7813a04 | 716 | let exchange_free_fn_def_id = scx.tcx() |
7453a54e SL |
717 | .lang_items |
718 | .require(ExchangeFreeFnLangItem) | |
a7813a04 | 719 | .unwrap_or_else(|e| scx.sess().fatal(&e)); |
7453a54e | 720 | |
a7813a04 XL |
721 | assert!(can_have_local_instance(scx.tcx(), exchange_free_fn_def_id)); |
722 | let fn_substs = scx.empty_substs_for_def_id(exchange_free_fn_def_id); | |
7453a54e | 723 | let exchange_free_fn_trans_item = |
9e0c209e | 724 | create_fn_trans_item(scx, |
7453a54e | 725 | exchange_free_fn_def_id, |
a7813a04 | 726 | fn_substs, |
c30ab7b3 | 727 | scx.tcx().intern_substs(&[])); |
7453a54e SL |
728 | |
729 | output.push(exchange_free_fn_trans_item); | |
730 | } | |
731 | ||
732 | // If the type implements Drop, also add a translation item for the | |
733 | // monomorphized Drop::drop() implementation. | |
734 | let destructor_did = match ty.sty { | |
9e0c209e | 735 | ty::TyAdt(def, _) => def.destructor(), |
7453a54e SL |
736 | _ => None |
737 | }; | |
738 | ||
739 | if let Some(destructor_did) = destructor_did { | |
54a0048b | 740 | use rustc::ty::ToPolyTraitRef; |
7453a54e | 741 | |
a7813a04 | 742 | let drop_trait_def_id = scx.tcx() |
7453a54e SL |
743 | .lang_items |
744 | .drop_trait() | |
745 | .unwrap(); | |
746 | ||
c30ab7b3 | 747 | let self_type_substs = scx.tcx().mk_substs_trait(ty, &[]); |
7453a54e SL |
748 | |
749 | let trait_ref = ty::TraitRef { | |
750 | def_id: drop_trait_def_id, | |
751 | substs: self_type_substs, | |
752 | }.to_poly_trait_ref(); | |
753 | ||
a7813a04 | 754 | let substs = match fulfill_obligation(scx, DUMMY_SP, trait_ref) { |
7453a54e | 755 | traits::VtableImpl(data) => data.substs, |
54a0048b | 756 | _ => bug!() |
7453a54e SL |
757 | }; |
758 | ||
a7813a04 | 759 | if can_have_local_instance(scx.tcx(), destructor_did) { |
9e0c209e | 760 | let trans_item = create_fn_trans_item(scx, |
7453a54e | 761 | destructor_did, |
54a0048b | 762 | substs, |
c30ab7b3 | 763 | scx.tcx().intern_substs(&[])); |
7453a54e SL |
764 | output.push(trans_item); |
765 | } | |
a7813a04 XL |
766 | |
767 | // This type has a Drop implementation, we'll need the contents-only | |
768 | // version of the glue too. | |
769 | output.push(TransItem::DropGlue(DropGlueKind::TyContents(ty))); | |
7453a54e SL |
770 | } |
771 | ||
772 | // Finally add the types of nested values | |
773 | match ty.sty { | |
54a0048b SL |
774 | ty::TyBool | |
775 | ty::TyChar | | |
776 | ty::TyInt(_) | | |
777 | ty::TyUint(_) | | |
778 | ty::TyStr | | |
779 | ty::TyFloat(_) | | |
780 | ty::TyRawPtr(_) | | |
781 | ty::TyRef(..) | | |
782 | ty::TyFnDef(..) | | |
783 | ty::TyFnPtr(_) | | |
5bcae85e | 784 | ty::TyNever | |
54a0048b | 785 | ty::TyTrait(_) => { |
7453a54e SL |
786 | /* nothing to do */ |
787 | } | |
9e0c209e | 788 | ty::TyAdt(adt_def, substs) => { |
7453a54e | 789 | for field in adt_def.all_fields() { |
9e0c209e | 790 | let field_type = monomorphize::apply_param_substs(scx, |
7453a54e SL |
791 | substs, |
792 | &field.unsubst_ty()); | |
a7813a04 | 793 | let field_type = glue::get_drop_glue_type(scx.tcx(), field_type); |
7453a54e | 794 | |
a7813a04 XL |
795 | if glue::type_needs_drop(scx.tcx(), field_type) { |
796 | output.push(TransItem::DropGlue(DropGlueKind::Ty(field_type))); | |
7453a54e SL |
797 | } |
798 | } | |
799 | } | |
a7813a04 XL |
800 | ty::TyClosure(_, substs) => { |
801 | for upvar_ty in substs.upvar_tys { | |
802 | let upvar_ty = glue::get_drop_glue_type(scx.tcx(), upvar_ty); | |
803 | if glue::type_needs_drop(scx.tcx(), upvar_ty) { | |
804 | output.push(TransItem::DropGlue(DropGlueKind::Ty(upvar_ty))); | |
7453a54e SL |
805 | } |
806 | } | |
807 | } | |
808 | ty::TyBox(inner_type) | | |
a7813a04 | 809 | ty::TySlice(inner_type) | |
7453a54e | 810 | ty::TyArray(inner_type, _) => { |
a7813a04 XL |
811 | let inner_type = glue::get_drop_glue_type(scx.tcx(), inner_type); |
812 | if glue::type_needs_drop(scx.tcx(), inner_type) { | |
813 | output.push(TransItem::DropGlue(DropGlueKind::Ty(inner_type))); | |
7453a54e SL |
814 | } |
815 | } | |
a7813a04 | 816 | ty::TyTuple(args) => { |
7453a54e | 817 | for arg in args { |
a7813a04 XL |
818 | let arg = glue::get_drop_glue_type(scx.tcx(), arg); |
819 | if glue::type_needs_drop(scx.tcx(), arg) { | |
820 | output.push(TransItem::DropGlue(DropGlueKind::Ty(arg))); | |
7453a54e SL |
821 | } |
822 | } | |
823 | } | |
824 | ty::TyProjection(_) | | |
825 | ty::TyParam(_) | | |
826 | ty::TyInfer(_) | | |
5bcae85e | 827 | ty::TyAnon(..) | |
7453a54e | 828 | ty::TyError => { |
54a0048b | 829 | bug!("encountered unexpected type"); |
7453a54e SL |
830 | } |
831 | } | |
a7813a04 XL |
832 | |
833 | ||
7453a54e SL |
834 | } |
835 | ||
a7813a04 | 836 | fn do_static_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
837 | fn_def_id: DefId, |
838 | fn_substs: &'tcx Substs<'tcx>, | |
839 | param_substs: &'tcx Substs<'tcx>) | |
840 | -> Option<(DefId, &'tcx Substs<'tcx>)> { | |
841 | debug!("do_static_dispatch(fn_def_id={}, fn_substs={:?}, param_substs={:?})", | |
a7813a04 | 842 | def_id_to_string(scx.tcx(), fn_def_id), |
7453a54e SL |
843 | fn_substs, |
844 | param_substs); | |
845 | ||
9e0c209e | 846 | if let Some(trait_def_id) = scx.tcx().trait_of_item(fn_def_id) { |
a7813a04 | 847 | match scx.tcx().impl_or_trait_item(fn_def_id) { |
7453a54e | 848 | ty::MethodTraitItem(ref method) => { |
9e0c209e SL |
849 | debug!(" => trait method, attempting to find impl"); |
850 | do_static_trait_method_dispatch(scx, | |
851 | method, | |
852 | trait_def_id, | |
853 | fn_substs, | |
854 | param_substs) | |
7453a54e | 855 | } |
54a0048b | 856 | _ => bug!() |
7453a54e SL |
857 | } |
858 | } else { | |
859 | debug!(" => regular function"); | |
860 | // The function is not part of an impl or trait, no dispatching | |
861 | // to be done | |
862 | Some((fn_def_id, fn_substs)) | |
863 | } | |
864 | } | |
865 | ||
866 | // Given a trait-method and substitution information, find out the actual | |
867 | // implementation of the trait method. | |
a7813a04 | 868 | fn do_static_trait_method_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
869 | trait_method: &ty::Method, |
870 | trait_id: DefId, | |
871 | callee_substs: &'tcx Substs<'tcx>, | |
872 | param_substs: &'tcx Substs<'tcx>) | |
873 | -> Option<(DefId, &'tcx Substs<'tcx>)> { | |
a7813a04 | 874 | let tcx = scx.tcx(); |
7453a54e SL |
875 | debug!("do_static_trait_method_dispatch(trait_method={}, \ |
876 | trait_id={}, \ | |
877 | callee_substs={:?}, \ | |
878 | param_substs={:?}", | |
a7813a04 XL |
879 | def_id_to_string(scx.tcx(), trait_method.def_id), |
880 | def_id_to_string(scx.tcx(), trait_id), | |
7453a54e SL |
881 | callee_substs, |
882 | param_substs); | |
883 | ||
9e0c209e | 884 | let rcvr_substs = monomorphize::apply_param_substs(scx, |
7453a54e | 885 | param_substs, |
a7813a04 | 886 | &callee_substs); |
9e0c209e SL |
887 | let trait_ref = ty::TraitRef::from_method(tcx, trait_id, rcvr_substs); |
888 | let vtbl = fulfill_obligation(scx, DUMMY_SP, ty::Binder(trait_ref)); | |
7453a54e SL |
889 | |
890 | // Now that we know which impl is being used, we can dispatch to | |
891 | // the actual function: | |
892 | match vtbl { | |
9e0c209e SL |
893 | traits::VtableImpl(impl_data) => { |
894 | Some(traits::find_method(tcx, trait_method.name, rcvr_substs, &impl_data)) | |
7453a54e SL |
895 | } |
896 | // If we have a closure or a function pointer, we will also encounter | |
897 | // the concrete closure/function somewhere else (during closure or fn | |
898 | // pointer construction). That's where we track those things. | |
899 | traits::VtableClosure(..) | | |
900 | traits::VtableFnPointer(..) | | |
901 | traits::VtableObject(..) => { | |
902 | None | |
903 | } | |
904 | _ => { | |
54a0048b | 905 | bug!("static call to invalid vtable: {:?}", vtbl) |
7453a54e SL |
906 | } |
907 | } | |
908 | } | |
909 | ||
910 | /// For given pair of source and target type that occur in an unsizing coercion, | |
911 | /// this function finds the pair of types that determines the vtable linking | |
912 | /// them. | |
913 | /// | |
914 | /// For example, the source type might be `&SomeStruct` and the target type\ | |
915 | /// might be `&SomeTrait` in a cast like: | |
916 | /// | |
917 | /// let src: &SomeStruct = ...; | |
918 | /// let target = src as &SomeTrait; | |
919 | /// | |
920 | /// Then the output of this function would be (SomeStruct, SomeTrait) since for | |
921 | /// constructing the `target` fat-pointer we need the vtable for that pair. | |
922 | /// | |
923 | /// Things can get more complicated though because there's also the case where | |
924 | /// the unsized type occurs as a field: | |
925 | /// | |
926 | /// ```rust | |
927 | /// struct ComplexStruct<T: ?Sized> { | |
928 | /// a: u32, | |
929 | /// b: f64, | |
930 | /// c: T | |
931 | /// } | |
932 | /// ``` | |
933 | /// | |
934 | /// In this case, if `T` is sized, `&ComplexStruct<T>` is a thin pointer. If `T` | |
935 | /// is unsized, `&SomeStruct` is a fat pointer, and the vtable it points to is | |
936 | /// for the pair of `T` (which is a trait) and the concrete type that `T` was | |
937 | /// originally coerced from: | |
938 | /// | |
939 | /// let src: &ComplexStruct<SomeStruct> = ...; | |
940 | /// let target = src as &ComplexStruct<SomeTrait>; | |
941 | /// | |
942 | /// Again, we want this `find_vtable_types_for_unsizing()` to provide the pair | |
943 | /// `(SomeStruct, SomeTrait)`. | |
944 | /// | |
945 | /// Finally, there is also the case of custom unsizing coercions, e.g. for | |
946 | /// smart pointers such as `Rc` and `Arc`. | |
a7813a04 | 947 | fn find_vtable_types_for_unsizing<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
948 | source_ty: ty::Ty<'tcx>, |
949 | target_ty: ty::Ty<'tcx>) | |
950 | -> (ty::Ty<'tcx>, ty::Ty<'tcx>) { | |
951 | match (&source_ty.sty, &target_ty.sty) { | |
952 | (&ty::TyBox(a), &ty::TyBox(b)) | | |
953 | (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), | |
954 | &ty::TyRef(_, ty::TypeAndMut { ty: b, .. })) | | |
955 | (&ty::TyRef(_, ty::TypeAndMut { ty: a, .. }), | |
956 | &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) | | |
957 | (&ty::TyRawPtr(ty::TypeAndMut { ty: a, .. }), | |
958 | &ty::TyRawPtr(ty::TypeAndMut { ty: b, .. })) => { | |
959 | let (inner_source, inner_target) = (a, b); | |
960 | ||
a7813a04 | 961 | if !type_is_sized(scx.tcx(), inner_source) { |
7453a54e SL |
962 | (inner_source, inner_target) |
963 | } else { | |
a7813a04 | 964 | scx.tcx().struct_lockstep_tails(inner_source, inner_target) |
7453a54e SL |
965 | } |
966 | } | |
967 | ||
9e0c209e SL |
968 | (&ty::TyAdt(source_adt_def, source_substs), |
969 | &ty::TyAdt(target_adt_def, target_substs)) => { | |
7453a54e SL |
970 | assert_eq!(source_adt_def, target_adt_def); |
971 | ||
a7813a04 | 972 | let kind = custom_coerce_unsize_info(scx, source_ty, target_ty); |
7453a54e SL |
973 | |
974 | let coerce_index = match kind { | |
975 | CustomCoerceUnsized::Struct(i) => i | |
976 | }; | |
977 | ||
978 | let source_fields = &source_adt_def.struct_variant().fields; | |
979 | let target_fields = &target_adt_def.struct_variant().fields; | |
980 | ||
981 | assert!(coerce_index < source_fields.len() && | |
982 | source_fields.len() == target_fields.len()); | |
983 | ||
a7813a04 XL |
984 | find_vtable_types_for_unsizing(scx, |
985 | source_fields[coerce_index].ty(scx.tcx(), | |
7453a54e | 986 | source_substs), |
a7813a04 | 987 | target_fields[coerce_index].ty(scx.tcx(), |
7453a54e SL |
988 | target_substs)) |
989 | } | |
54a0048b SL |
990 | _ => bug!("find_vtable_types_for_unsizing: invalid coercion {:?} -> {:?}", |
991 | source_ty, | |
992 | target_ty) | |
7453a54e SL |
993 | } |
994 | } | |
995 | ||
9e0c209e | 996 | fn create_fn_trans_item<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e | 997 | def_id: DefId, |
a7813a04 XL |
998 | fn_substs: &'tcx Substs<'tcx>, |
999 | param_substs: &'tcx Substs<'tcx>) | |
1000 | -> TransItem<'tcx> { | |
9e0c209e SL |
1001 | let tcx = scx.tcx(); |
1002 | ||
7453a54e | 1003 | debug!("create_fn_trans_item(def_id={}, fn_substs={:?}, param_substs={:?})", |
a7813a04 | 1004 | def_id_to_string(tcx, def_id), |
7453a54e SL |
1005 | fn_substs, |
1006 | param_substs); | |
1007 | ||
1008 | // We only get here, if fn_def_id either designates a local item or | |
1009 | // an inlineable external item. Non-inlineable external items are | |
1010 | // ignored because we don't want to generate any code for them. | |
9e0c209e | 1011 | let concrete_substs = monomorphize::apply_param_substs(scx, |
7453a54e | 1012 | param_substs, |
a7813a04 | 1013 | &fn_substs); |
1bb2cb6e SL |
1014 | assert!(concrete_substs.is_normalized_for_trans(), |
1015 | "concrete_substs not normalized for trans: {:?}", | |
1016 | concrete_substs); | |
3157f602 | 1017 | TransItem::Fn(Instance::new(def_id, concrete_substs)) |
7453a54e SL |
1018 | } |
1019 | ||
1020 | /// Creates a `TransItem` for each method that is referenced by the vtable for | |
1021 | /// the given trait/impl pair. | |
a7813a04 | 1022 | fn create_trans_items_for_vtable_methods<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
1023 | trait_ty: ty::Ty<'tcx>, |
1024 | impl_ty: ty::Ty<'tcx>, | |
1025 | output: &mut Vec<TransItem<'tcx>>) { | |
1026 | assert!(!trait_ty.needs_subst() && !impl_ty.needs_subst()); | |
1027 | ||
1028 | if let ty::TyTrait(ref trait_ty) = trait_ty.sty { | |
9e0c209e | 1029 | let poly_trait_ref = trait_ty.principal.with_self_ty(scx.tcx(), impl_ty); |
c30ab7b3 | 1030 | let param_substs = scx.tcx().intern_substs(&[]); |
7453a54e SL |
1031 | |
1032 | // Walk all methods of the trait, including those of its supertraits | |
9e0c209e SL |
1033 | let methods = traits::get_vtable_methods(scx.tcx(), poly_trait_ref); |
1034 | let methods = methods.filter_map(|method| method) | |
1035 | .filter_map(|(def_id, substs)| do_static_dispatch(scx, def_id, substs, param_substs)) | |
1036 | .filter(|&(def_id, _)| can_have_local_instance(scx.tcx(), def_id)) | |
1037 | .map(|(def_id, substs)| create_fn_trans_item(scx, def_id, substs, param_substs)); | |
1038 | output.extend(methods); | |
1039 | ||
1040 | // Also add the destructor | |
1041 | let dg_type = glue::get_drop_glue_type(scx.tcx(), impl_ty); | |
1042 | output.push(TransItem::DropGlue(DropGlueKind::Ty(dg_type))); | |
7453a54e SL |
1043 | } |
1044 | } | |
1045 | ||
1046 | //=----------------------------------------------------------------------------- | |
1047 | // Root Collection | |
1048 | //=----------------------------------------------------------------------------- | |
1049 | ||
1050 | struct RootCollector<'b, 'a: 'b, 'tcx: 'a + 'b> { | |
a7813a04 | 1051 | scx: &'b SharedCrateContext<'a, 'tcx>, |
7453a54e SL |
1052 | mode: TransItemCollectionMode, |
1053 | output: &'b mut Vec<TransItem<'tcx>>, | |
1054 | enclosing_item: Option<&'tcx hir::Item>, | |
7453a54e SL |
1055 | } |
1056 | ||
1057 | impl<'b, 'a, 'v> hir_visit::Visitor<'v> for RootCollector<'b, 'a, 'v> { | |
1058 | fn visit_item(&mut self, item: &'v hir::Item) { | |
1059 | let old_enclosing_item = self.enclosing_item; | |
1060 | self.enclosing_item = Some(item); | |
1061 | ||
1062 | match item.node { | |
1063 | hir::ItemExternCrate(..) | | |
1064 | hir::ItemUse(..) | | |
1065 | hir::ItemForeignMod(..) | | |
1066 | hir::ItemTy(..) | | |
1067 | hir::ItemDefaultImpl(..) | | |
1068 | hir::ItemTrait(..) | | |
7453a54e SL |
1069 | hir::ItemMod(..) => { |
1070 | // Nothing to do, just keep recursing... | |
1071 | } | |
1072 | ||
1073 | hir::ItemImpl(..) => { | |
1074 | if self.mode == TransItemCollectionMode::Eager { | |
9e0c209e | 1075 | create_trans_items_for_default_impls(self.scx, |
7453a54e | 1076 | item, |
7453a54e SL |
1077 | self.output); |
1078 | } | |
1079 | } | |
1080 | ||
9e0c209e SL |
1081 | hir::ItemEnum(_, ref generics) | |
1082 | hir::ItemStruct(_, ref generics) | | |
1083 | hir::ItemUnion(_, ref generics) => { | |
7453a54e | 1084 | if !generics.is_parameterized() { |
c30ab7b3 | 1085 | let ty = self.scx.tcx().tables().node_types[&item.id]; |
7453a54e SL |
1086 | |
1087 | if self.mode == TransItemCollectionMode::Eager { | |
1088 | debug!("RootCollector: ADT drop-glue for {}", | |
a7813a04 XL |
1089 | def_id_to_string(self.scx.tcx(), |
1090 | self.scx.tcx().map.local_def_id(item.id))); | |
7453a54e | 1091 | |
a7813a04 XL |
1092 | let ty = glue::get_drop_glue_type(self.scx.tcx(), ty); |
1093 | self.output.push(TransItem::DropGlue(DropGlueKind::Ty(ty))); | |
7453a54e SL |
1094 | } |
1095 | } | |
1096 | } | |
1097 | hir::ItemStatic(..) => { | |
1098 | debug!("RootCollector: ItemStatic({})", | |
a7813a04 XL |
1099 | def_id_to_string(self.scx.tcx(), |
1100 | self.scx.tcx().map.local_def_id(item.id))); | |
7453a54e SL |
1101 | self.output.push(TransItem::Static(item.id)); |
1102 | } | |
5bcae85e SL |
1103 | hir::ItemConst(..) => { |
1104 | // const items only generate translation items if they are | |
1105 | // actually used somewhere. Just declaring them is insufficient. | |
1106 | } | |
9e0c209e | 1107 | hir::ItemFn(.., ref generics, _) => { |
5bcae85e | 1108 | if !generics.is_type_parameterized() { |
a7813a04 | 1109 | let def_id = self.scx.tcx().map.local_def_id(item.id); |
7453a54e SL |
1110 | |
1111 | debug!("RootCollector: ItemFn({})", | |
a7813a04 | 1112 | def_id_to_string(self.scx.tcx(), def_id)); |
7453a54e | 1113 | |
a7813a04 | 1114 | let instance = Instance::mono(self.scx, def_id); |
54a0048b | 1115 | self.output.push(TransItem::Fn(instance)); |
7453a54e SL |
1116 | } |
1117 | } | |
1118 | } | |
1119 | ||
1120 | hir_visit::walk_item(self, item); | |
1121 | self.enclosing_item = old_enclosing_item; | |
1122 | } | |
1123 | ||
1124 | fn visit_impl_item(&mut self, ii: &'v hir::ImplItem) { | |
1125 | match ii.node { | |
1126 | hir::ImplItemKind::Method(hir::MethodSig { | |
1127 | ref generics, | |
7453a54e | 1128 | .. |
5bcae85e | 1129 | }, _) => { |
a7813a04 | 1130 | let hir_map = &self.scx.tcx().map; |
7453a54e SL |
1131 | let parent_node_id = hir_map.get_parent_node(ii.id); |
1132 | let is_impl_generic = match hir_map.expect_item(parent_node_id) { | |
1133 | &hir::Item { | |
9e0c209e | 1134 | node: hir::ItemImpl(_, _, ref generics, ..), |
7453a54e SL |
1135 | .. |
1136 | } => { | |
1137 | generics.is_type_parameterized() | |
1138 | } | |
1139 | _ => { | |
54a0048b | 1140 | bug!() |
7453a54e SL |
1141 | } |
1142 | }; | |
1143 | ||
1144 | if !generics.is_type_parameterized() && !is_impl_generic { | |
a7813a04 | 1145 | let def_id = self.scx.tcx().map.local_def_id(ii.id); |
7453a54e SL |
1146 | |
1147 | debug!("RootCollector: MethodImplItem({})", | |
a7813a04 | 1148 | def_id_to_string(self.scx.tcx(), def_id)); |
7453a54e | 1149 | |
a7813a04 | 1150 | let instance = Instance::mono(self.scx, def_id); |
54a0048b | 1151 | self.output.push(TransItem::Fn(instance)); |
7453a54e SL |
1152 | } |
1153 | } | |
1154 | _ => { /* Nothing to do here */ } | |
1155 | } | |
1156 | ||
1157 | hir_visit::walk_impl_item(self, ii) | |
1158 | } | |
1159 | } | |
1160 | ||
9e0c209e | 1161 | fn create_trans_items_for_default_impls<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, |
7453a54e | 1162 | item: &'tcx hir::Item, |
7453a54e | 1163 | output: &mut Vec<TransItem<'tcx>>) { |
9e0c209e | 1164 | let tcx = scx.tcx(); |
7453a54e SL |
1165 | match item.node { |
1166 | hir::ItemImpl(_, | |
1167 | _, | |
1168 | ref generics, | |
9e0c209e | 1169 | .., |
7453a54e SL |
1170 | ref items) => { |
1171 | if generics.is_type_parameterized() { | |
1172 | return | |
1173 | } | |
1174 | ||
7453a54e SL |
1175 | let impl_def_id = tcx.map.local_def_id(item.id); |
1176 | ||
1177 | debug!("create_trans_items_for_default_impls(item={})", | |
a7813a04 | 1178 | def_id_to_string(tcx, impl_def_id)); |
7453a54e SL |
1179 | |
1180 | if let Some(trait_ref) = tcx.impl_trait_ref(impl_def_id) { | |
a7813a04 | 1181 | let callee_substs = tcx.erase_regions(&trait_ref.substs); |
7453a54e SL |
1182 | let overridden_methods: FnvHashSet<_> = items.iter() |
1183 | .map(|item| item.name) | |
1184 | .collect(); | |
9e0c209e SL |
1185 | for method in tcx.provided_trait_methods(trait_ref.def_id) { |
1186 | if overridden_methods.contains(&method.name) { | |
7453a54e SL |
1187 | continue; |
1188 | } | |
1189 | ||
9e0c209e | 1190 | if !method.generics.types.is_empty() { |
7453a54e SL |
1191 | continue; |
1192 | } | |
1193 | ||
1194 | // The substitutions we have are on the impl, so we grab | |
1195 | // the method type from the impl to substitute into. | |
9e0c209e SL |
1196 | let impl_substs = Substs::for_item(tcx, impl_def_id, |
1197 | |_, _| tcx.mk_region(ty::ReErased), | |
1198 | |_, _| tcx.types.err); | |
1199 | let impl_data = traits::VtableImplData { | |
1200 | impl_def_id: impl_def_id, | |
1201 | substs: impl_substs, | |
1202 | nested: vec![] | |
1203 | }; | |
1204 | let (def_id, substs) = traits::find_method(tcx, | |
1205 | method.name, | |
1206 | callee_substs, | |
1207 | &impl_data); | |
1208 | ||
1209 | let predicates = tcx.lookup_predicates(def_id).predicates | |
1210 | .subst(tcx, substs); | |
1211 | if !traits::normalize_and_test_predicates(tcx, predicates) { | |
7453a54e SL |
1212 | continue; |
1213 | } | |
1214 | ||
9e0c209e SL |
1215 | if can_have_local_instance(tcx, method.def_id) { |
1216 | let item = create_fn_trans_item(scx, | |
1217 | method.def_id, | |
7453a54e | 1218 | callee_substs, |
9e0c209e | 1219 | tcx.erase_regions(&substs)); |
7453a54e SL |
1220 | output.push(item); |
1221 | } | |
1222 | } | |
1223 | } | |
1224 | } | |
1225 | _ => { | |
54a0048b | 1226 | bug!() |
7453a54e SL |
1227 | } |
1228 | } | |
1229 | } | |
1230 | ||
5bcae85e SL |
1231 | // There are no translation items for constants themselves but their |
1232 | // initializers might still contain something that produces translation items, | |
1233 | // such as cast that introduce a new vtable. | |
1234 | fn collect_const_item_neighbours<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>, | |
1235 | def_id: DefId, | |
1236 | substs: &'tcx Substs<'tcx>, | |
1237 | output: &mut Vec<TransItem<'tcx>>) | |
1238 | { | |
1239 | // Scan the MIR in order to find function calls, closures, and | |
1240 | // drop-glue | |
c30ab7b3 | 1241 | let mir = scx.tcx().item_mir(def_id); |
5bcae85e SL |
1242 | |
1243 | let visitor = MirNeighborCollector { | |
1244 | scx: scx, | |
1245 | mir: &mir, | |
1246 | output: output, | |
1247 | param_substs: substs | |
1248 | }; | |
7453a54e | 1249 | |
5bcae85e | 1250 | visit_mir_and_promoted(visitor, &mir); |
7453a54e SL |
1251 | } |
1252 | ||
5bcae85e SL |
1253 | fn visit_mir_and_promoted<'tcx, V: MirVisitor<'tcx>>(mut visitor: V, mir: &mir::Mir<'tcx>) { |
1254 | visitor.visit_mir(&mir); | |
1255 | for promoted in &mir.promoted { | |
1256 | visitor.visit_mir(promoted); | |
7453a54e SL |
1257 | } |
1258 | } |