Module collector

Mono Item Collection

This module is responsible for discovering all items that will contribute to code generation of the crate. The important part here is that it not only needs to find syntax-level items (functions, structs, etc) but also all their monomorphized instantiations. Every non-generic, non-const function maps to one LLVM artifact. Every generic function can produce from zero to N artifacts, depending on the sets of type arguments it is instantiated with. This also applies to generic items from other crates: A generic definition in crate X might produce monomorphizations that are compiled into crate Y. We also have to collect these here.

The following kinds of “mono items” are handled here:

• Functions
• Methods
• Closures
• Statics
• Drop glue

The following things also result in LLVM artifacts, but are not collected here, since we instantiate them locally on demand when needed in a given codegen unit:

• Constants
• VTables
• Object Shims

The main entry point is collect_crate_mono_items, at the bottom of this file.

General Algorithm

Let’s define some terms first:

• A “mono item” is something that results in a function or global in the LLVM IR of a codegen unit. Mono items do not stand on their own, they can use other mono items. For example, if function foo() calls function bar() then the mono item for foo() uses the mono item for function bar(). In general, the definition for mono item A using a mono item B is that the LLVM artifact produced for A uses the LLVM artifact produced for B.

• Mono items and the uses between them form a directed graph, where the mono items are the nodes and uses form the edges. Let’s call this graph the “mono item graph”.

• The mono item graph for a program contains all mono items that are needed in order to produce the complete LLVM IR of the program.

The purpose of the algorithm implemented in this module is to build the mono item graph for the current crate. It runs in two phases:

1. Discover the roots of the graph by traversing the HIR of the crate.
2. Starting from the roots, find uses by inspecting the MIR representation of the item corresponding to a given node, until no more new nodes are found.

Discovering roots

The roots of the mono item graph correspond to the public non-generic syntactic items in the source code. We find them by walking the HIR of the crate, and whenever we hit upon a public function, method, or static item, we create a mono item consisting of the items DefId and, since we only consider non-generic items, an empty type-parameters set. (In eager collection mode, during incremental compilation, all non-generic functions are considered as roots, as well as when the -Clink-dead-code option is specified. Functions marked #[no_mangle] and functions called by inlinable functions also always act as roots.)

Finding uses

Given a mono item node, we can discover uses by inspecting its MIR. We walk the MIR to find other mono items used by each mono item. Since the mono item we are currently at is always monomorphic, we also know the concrete type arguments of its used mono items. The specific forms a use can take in MIR are quite diverse. Here is an overview:

Calling Functions/Methods

The most obvious way for one mono item to use another is a function or method call (represented by a CALL terminator in MIR). But calls are not the only thing that might introduce a use between two function mono items, and as we will see below, they are just a specialization of the form described next, and consequently will not get any special treatment in the algorithm.

Taking a reference to a function or method

A function does not need to actually be called in order to be used by another function. It suffices to just take a reference in order to introduce an edge. Consider the following example:

fn print_val<T: Display>(x: T) {
    println!("{}", x);
}

fn call_fn(f: &dyn Fn(i32), x: i32) {
    f(x);
}

fn main() {
    let print_i32 = print_val::<i32>;
    call_fn(&print_i32, 0);
}

The MIR of none of these functions will contain an explicit call to print_val::<i32>. Nonetheless, in order to mono this program, we need an instance of this function. Thus, whenever we encounter a function or method in operand position, we treat it as a use of the current mono item. Calls are just a special case of that.

Drop glue

Drop glue mono items are introduced by MIR drop-statements. The generated mono item will have additional drop-glue item uses if the type to be dropped contains nested values that also need to be dropped. It might also have a function item use for the explicit Drop::drop implementation of its type.

Unsizing Casts

A subtle way of introducing use edges is by casting to a trait object. Since the resulting wide-pointer contains a reference to a vtable, we need to instantiate all dyn-compatible methods of the trait, as we need to store pointers to these functions even if they never get called anywhere. This can be seen as a special case of taking a function reference.

Interaction with Cross-Crate Inlining

The binary of a crate will not only contain machine code for the items defined in the source code of that crate. It will also contain monomorphic instantiations of any extern generic functions and of functions marked with #[inline]. The collection algorithm handles this more or less mono. If it is about to create a mono item for something with an external DefId, it will take a look if the MIR for that item is available, and if so just proceed normally. If the MIR is not available, it assumes that the item is just linked to and no node is created; which is exactly what we want, since no machine code should be generated in the current crate for such an item.

Eager and Lazy Collection Strategy

Mono item collection can be performed with one of two strategies:

• Lazy strategy means that items will only be instantiated when actually used. The goal is to produce the least amount of machine code possible.

• Eager strategy is meant to be used in conjunction with incremental compilation where a stable set of mono items is more important than a minimal one. Thus, eager strategy will instantiate drop-glue for every drop-able type in the crate, even if no drop call for that type exists (yet). It will also instantiate default implementations of trait methods, something that otherwise is only done on demand.

Collection-time const evaluation and “mentioned” items

One important role of collection is to evaluate all constants that are used by all the items which are being collected. Codegen can then rely on only encountering constants that evaluate successfully, and if a constant fails to evaluate, the collector has much better context to be able to show where this constant comes up.

However, the exact set of “used” items (collected as described above), and therefore the exact set of used constants, can depend on optimizations. Optimizing away dead code may optimize away a function call that uses a failing constant, so an unoptimized build may fail where an optimized build succeeds. This is undesirable.

To avoid this, the collector has the concept of “mentioned” items. Some time during the MIR pipeline, before any optimization-level-dependent optimizations, we compute a list of all items that syntactically appear in the code. These are considered “mentioned”, and even if they are in dead code and get optimized away (which makes them no longer “used”), they are still “mentioned”. For every used item, the collector ensures that all mentioned items, recursively, do not use a failing constant. This is reflected via the CollectionMode, which determines whether we are visiting a used item or merely a mentioned item.

The collector and “mentioned items” gathering (which lives in rustc_mir_transform::mentioned_items) need to stay in sync in the following sense:

• For every item that the collector gather that could eventually lead to build failure (most likely due to containing a constant that fails to evaluate), a corresponding mentioned item must be added. This should use the exact same strategy as the ecollector to make sure they are in sync. However, while the collector works on monomorphized types, mentioned items are collected on generic MIR – so any time the collector checks for a particular type (such as ty::FnDef), we have to just onconditionally add this as a mentioned item.
• In visit_mentioned_item, we then do with that mentioned item exactly what the collector would have done during regular MIR visiting. Basically you can think of the collector having two stages, a pre-monomorphization stage and a post-monomorphization stage (usually quite literally separated by a call to self.monomorphize); the pre-monomorphizationn stage is duplicated in mentioned items gathering and the post-monomorphization stage is duplicated in visit_mentioned_item.
• Finally, as a performance optimization, the collector should fill used_mentioned_item during its MIR traversal with exactly what mentioned item gathering would have added in the same situation. This detects mentioned items that have not been optimized away and hence don’t need a dedicated traversal.

Open Issues

Some things are not yet fully implemented in the current version of this module.

Const Fns

Ideally, no mono item should be generated for const fns unless there is a call to them that cannot be evaluated at compile time. At the moment this is not implemented however: a mono item will be produced regardless of whether it is actually needed or not.

Structs

• MirUsedCollector 🔒
• RootCollector 🔒
• SharedState 🔒
  The state that is shared across the concurrent threads that are doing collection.
• UsageMap 🔒

Enums

• CollectionMode 🔒
  See module-level docs on some contect for “mentioned” items.
• MonoItemCollectionStrategy 🔒

Functions

• check_recursion_limit 🔒
• collect_alloc 🔒
  Scans the CTFE alloc in order to find function pointers and statics that must be monomorphized.
• collect_const_value 🔒
• collect_crate_mono_items 🔒
• collect_items_of_instance 🔒
  Scans the MIR in order to find function calls, closures, and drop-glue.
• collect_items_rec 🔒
  Collect all monomorphized items reachable from starting_point, and emit a note diagnostic if a post-monomorphization error is encountered during a collection step.
• collect_roots 🔒
• create_fn_mono_item 🔒
• create_mono_items_for_default_impls 🔒
• create_mono_items_for_vtable_methods 🔒
  Creates a MonoItem for each method that is referenced by the vtable for the given trait/impl pair.
• find_vtable_types_for_unsizing 🔒
  For a given pair of source and target type that occur in an unsizing coercion, this function finds the pair of types that determines the vtable linking them.
• provide 🔒
• should_codegen_locally 🔒
  Returns true if we should codegen an instance in the local crate, or returns false if we can just link to the upstream crate and therefore don’t need a mono item.
• visit_drop_use 🔒
• visit_fn_use 🔒
  For every call of this function in the visitor, make sure there is a matching call in the mentioned_items pass!
• visit_instance_use 🔒
• visit_mentioned_item 🔒
  item must be already monomorphized.

Type Aliases

• MonoItems 🔒