Skip to main content

wasmtime/
compile.rs

1//! Wasm compilation orchestration.
2//!
3//! It works roughly like this:
4//!
5//! * We walk over the Wasm module/component and make a list of all the things
6//!   we need to compile. This is a `CompileInputs`.
7//!
8//! * The `CompileInputs::compile` method compiles each of these in parallel,
9//!   producing a `UnlinkedCompileOutputs`. This is an unlinked set of compiled
10//!   functions, bucketed by type of function.
11//!
12//! * The `UnlinkedCompileOutputs::pre_link` method re-arranges the compiled
13//!   functions into a flat list. This is the order we will place them within
14//!   the ELF file, so we must also keep track of all the functions' indices
15//!   within this list, because we will need them for resolving
16//!   relocations. These indices are kept track of in the resulting
17//!   `FunctionIndices`.
18//!
19//! * The `FunctionIndices::link_and_append_code` method appends the functions
20//!   to the given ELF file and resolves relocations. It produces an `Artifacts`
21//!   which contains the data needed at runtime to find and call Wasm
22//!   functions. It is up to the caller to serialize the relevant parts of the
23//!   `Artifacts` into the ELF file.
24
25use crate::Engine;
26use crate::hash_map::HashMap;
27use crate::hash_set::HashSet;
28use crate::prelude::*;
29use std::{any::Any, borrow::Cow, mem, ops::Range};
30use wasmtime_environ::{
31    Abi, CallSite, CompiledFunctionBody, CompiledFunctionsTable, CompiledFunctionsTableBuilder,
32    CompiledModuleInfo, Compiler, DefinedFuncIndex, FilePos, FinishedObject, FuncKey,
33    FunctionBodyData, Inlining, InliningCompiler, ModuleEnvironment, ModuleTranslation,
34    ModuleTypes, ModuleTypesBuilder, ObjectKind, PrimaryMap, StaticModuleIndex, Tunables,
35    graphs::{EntityGraph, Graph as _},
36};
37#[cfg(feature = "component-model")]
38use wasmtime_environ::{WasmChecksum, component::Translator};
39
40mod stratify;
41
42mod code_builder;
43pub use self::code_builder::{CodeBuilder, CodeHint, HashedEngineCompileEnv};
44
45#[cfg(feature = "runtime")]
46mod runtime;
47
48/// Converts an input binary-encoded WebAssembly module to compilation
49/// artifacts and type information.
50///
51/// This is where compilation actually happens of WebAssembly modules and
52/// translation/parsing/validation of the binary input occurs. The binary
53/// artifact represented in the `MmapVec` returned here is an in-memory ELF
54/// file in an owned area of virtual linear memory where permissions (such
55/// as the executable bit) can be applied.
56///
57/// Additionally compilation returns an `Option` here which is always
58/// `Some`, notably compiled metadata about the module in addition to the
59/// type information found within.
60pub(crate) fn build_module_artifacts<T: FinishedObject>(
61    engine: &Engine,
62    wasm: &[u8],
63    dwarf_package: Option<&[u8]>,
64    obj_state: &T::State,
65) -> Result<(
66    T,
67    Option<(CompiledModuleInfo, CompiledFunctionsTable, ModuleTypes)>,
68)> {
69    let compiler = engine.try_compiler()?;
70    let tunables = engine.tunables();
71
72    // First a `ModuleEnvironment` is created which records type information
73    // about the wasm module. This is where the WebAssembly is parsed and
74    // validated. Afterwards `types` will have all the type information for
75    // this module.
76    let mut parser = wasmparser::Parser::new(0);
77    let mut validator = wasmparser::Validator::new_with_features(engine.features());
78    parser.set_features(*validator.features());
79    let mut types = ModuleTypesBuilder::new(&validator);
80    let mut translation = ModuleEnvironment::new(
81        tunables,
82        &mut validator,
83        &mut types,
84        StaticModuleIndex::from_u32(0),
85    )
86    .translate(parser, wasm)
87    .context("failed to parse WebAssembly module")?;
88    prepare_translation(engine, compiler, &mut translation, &mut types);
89    let functions = mem::take(&mut translation.function_body_inputs);
90
91    let compile_inputs = CompileInputs::for_module(&types, &translation, functions);
92    let unlinked_compile_outputs = compile_inputs.compile(engine, &types)?;
93    let PreLinkOutput {
94        needs_gc_heap,
95        compiled_funcs,
96        indices,
97    } = unlinked_compile_outputs.pre_link();
98    translation.module.needs_gc_heap |= needs_gc_heap;
99
100    // Emplace all compiled functions into the object file with any other
101    // sections associated with code as well.
102    let mut object = compiler.object(ObjectKind::Module)?;
103    // Insert `Engine` and type-level information into the compiled
104    // artifact so if this module is deserialized later it contains all
105    // information necessary.
106    //
107    // Note that `append_compiler_info` and `append_types` here in theory
108    // can both be skipped if this module will never get serialized.
109    // They're only used during deserialization and not during runtime for
110    // the module itself. Currently there's no need for that, however, so
111    // it's left as an exercise for later.
112    engine.append_compiler_info(&mut object)?;
113    engine.append_bti(&mut object);
114
115    let (mut object, compilation_artifacts) = indices.link_and_append_code(
116        object,
117        engine,
118        compiled_funcs,
119        std::iter::once(translation).collect(),
120        dwarf_package,
121    )?;
122
123    if tunables.debug_guest {
124        object.append_wasm_bytecode(std::iter::once(wasm));
125    }
126
127    let (info, index) = compilation_artifacts.unwrap_as_module_info();
128    let types = types.finish();
129    object.serialize_info(&(&info, &index, &types));
130    let result = T::finish_object(object, obj_state)?;
131
132    compiler.release_caches();
133
134    Ok((result, Some((info, index, types))))
135}
136
137/// Performs the compilation phase for a component, translating and
138/// validating the provided wasm binary to machine code.
139///
140/// This method will compile all nested core wasm binaries in addition to
141/// any necessary extra functions required for operation with components.
142/// The output artifact here is the serialized object file contained within
143/// an owned mmap along with metadata about the compilation itself.
144#[cfg(feature = "component-model")]
145pub(crate) fn build_component_artifacts<T: FinishedObject>(
146    engine: &Engine,
147    binary: &[u8],
148    _dwarf_package: Option<&[u8]>,
149    unsafe_intrinsics_import: Option<&str>,
150    obj_state: &T::State,
151) -> Result<(T, Option<wasmtime_environ::component::ComponentArtifacts>)> {
152    use wasmtime_environ::ScopeVec;
153    use wasmtime_environ::component::{
154        CompiledComponentInfo, ComponentArtifacts, ComponentTypesBuilder,
155    };
156
157    let compiler = engine.try_compiler()?;
158    let tunables = engine.tunables();
159
160    let scope = ScopeVec::new();
161    let mut validator = wasmparser::Validator::new_with_features(engine.features());
162    let mut types = ComponentTypesBuilder::new(&validator);
163    let mut translator = Translator::new(tunables, &mut validator, &mut types, &scope);
164    if let Some(name) = unsafe_intrinsics_import {
165        translator.expose_unsafe_intrinsics(name);
166    }
167    let (component, mut module_translations) = translator
168        .translate(binary)
169        .context("failed to parse WebAssembly module")?;
170
171    for (_, translation) in module_translations.iter_mut() {
172        prepare_translation(
173            engine,
174            compiler,
175            translation,
176            types.module_types_builder_mut(),
177        );
178    }
179
180    let compile_inputs = CompileInputs::for_component(
181        engine,
182        &types,
183        &component,
184        module_translations.iter_mut().map(|(i, translation)| {
185            let functions = mem::take(&mut translation.function_body_inputs);
186            (i, &*translation, functions)
187        }),
188    );
189    let unlinked_compile_outputs = compile_inputs.compile(&engine, types.module_types_builder())?;
190
191    let PreLinkOutput {
192        needs_gc_heap,
193        compiled_funcs,
194        indices,
195    } = unlinked_compile_outputs.pre_link();
196    for (_, t) in &mut module_translations {
197        t.module.needs_gc_heap |= needs_gc_heap
198    }
199
200    // Collect bytecode slices here before moving `module_translations` below.
201    let module_wasms = if tunables.debug_guest {
202        module_translations
203            .values()
204            .map(|t| t.wasm)
205            .collect::<Vec<_>>()
206    } else {
207        vec![]
208    };
209
210    let mut object = compiler.object(ObjectKind::Component)?;
211    engine.append_compiler_info(&mut object)?;
212    engine.append_bti(&mut object);
213
214    let (mut object, compilation_artifacts) = indices.link_and_append_code(
215        object,
216        engine,
217        compiled_funcs,
218        module_translations,
219        None, // TODO: Support dwarf packages for components.
220    )?;
221
222    if tunables.debug_guest {
223        object.append_wasm_bytecode(module_wasms);
224    }
225
226    let (types, ty) = types.finish(&component.component);
227
228    let info = CompiledComponentInfo {
229        component: component.component,
230    };
231    let artifacts = ComponentArtifacts {
232        info,
233        table: compilation_artifacts.table,
234        ty,
235        types,
236        static_modules: compilation_artifacts.modules.into(),
237        checksum: WasmChecksum::from_binary(binary, tunables.recording),
238    };
239    object.serialize_info(&artifacts);
240
241    compiler.release_caches();
242
243    let result = T::finish_object(object, obj_state)?;
244    Ok((result, Some(artifacts)))
245}
246
247fn prepare_translation(
248    engine: &Engine,
249    compiler: &dyn Compiler,
250    translation: &mut ModuleTranslation<'_>,
251    types: &mut ModuleTypesBuilder,
252) {
253    // If configured attempt to use static memory initialization
254    // which can either at runtime be implemented as a single memcpy
255    // to initialize memory or otherwise enabling
256    // virtual-memory-tricks such as mmap'ing from a file to get
257    // copy-on-write.
258    let align = compiler.page_size_align();
259    let max_always_allowed = engine.config().memory_guaranteed_dense_image_size;
260    translation.finalize_memory_init(engine.tunables(), align, max_always_allowed, types);
261
262    // Attempt to convert table initializer segments to FuncTable
263    // representation where possible, to enable table lazy init.
264    translation.finalize_table_init(engine.tunables(), types);
265}
266
267type CompileInput<'a> = Box<dyn FnOnce(&dyn Compiler) -> Result<CompileOutput<'a>> + Send + 'a>;
268
269struct CompileOutput<'a> {
270    key: FuncKey,
271    symbol: String,
272    function: CompiledFunctionBody,
273    start_srcloc: FilePos,
274
275    // Only present when `self.key` is a `FuncKey::DefinedWasmFunction(..)`.
276    translation: Option<&'a ModuleTranslation<'a>>,
277
278    // Only present when `self.key` is a `FuncKey::DefinedWasmFunction(..)`.
279    func_body: Option<wasmparser::FunctionBody<'a>>,
280}
281
282/// Inputs to our inlining heuristics.
283struct InlineHeuristicParams<'a> {
284    tunables: &'a Tunables,
285    caller_size: u32,
286    caller_key: FuncKey,
287    caller_needs_gc_heap: bool,
288    callee_size: u32,
289    callee_key: FuncKey,
290    callee_needs_gc_heap: bool,
291    call_site_is_cold: bool,
292}
293
294/// The collection of things we need to compile for a Wasm module or component.
295#[derive(Default)]
296struct CompileInputs<'a> {
297    inputs: Vec<CompileInput<'a>>,
298}
299
300impl<'a> CompileInputs<'a> {
301    fn push_input(
302        &mut self,
303        f: impl FnOnce(&dyn Compiler) -> Result<CompileOutput<'a>> + Send + 'a,
304    ) {
305        self.inputs.push(Box::new(f));
306    }
307
308    /// Create the `CompileInputs` for a core Wasm module.
309    fn for_module(
310        types: &'a ModuleTypesBuilder,
311        translation: &'a ModuleTranslation<'a>,
312        functions: PrimaryMap<DefinedFuncIndex, FunctionBodyData<'a>>,
313    ) -> Self {
314        let mut ret = CompileInputs { inputs: vec![] };
315
316        let module_index = StaticModuleIndex::from_u32(0);
317        ret.collect_inputs_in_translations(types, None, [(module_index, translation, functions)]);
318
319        ret
320    }
321
322    /// Create a `CompileInputs` for a component.
323    #[cfg(feature = "component-model")]
324    fn for_component(
325        engine: &'a Engine,
326        types: &'a wasmtime_environ::component::ComponentTypesBuilder,
327        component: &'a wasmtime_environ::component::ComponentTranslation,
328        module_translations: impl IntoIterator<
329            Item = (
330                StaticModuleIndex,
331                &'a ModuleTranslation<'a>,
332                PrimaryMap<DefinedFuncIndex, FunctionBodyData<'a>>,
333            ),
334        >,
335    ) -> Self {
336        use wasmtime_environ::Abi;
337        use wasmtime_environ::component::UnsafeIntrinsic;
338
339        let mut ret = CompileInputs { inputs: vec![] };
340
341        ret.collect_inputs_in_translations(
342            types.module_types_builder(),
343            Some(wasmtime_environ::EnclosingComponent(&component.component)),
344            module_translations,
345        );
346        let tunables = engine.tunables();
347
348        for i in component
349            .component
350            .unsafe_intrinsics
351            .iter()
352            .enumerate()
353            .filter_map(|(i, ty)| if ty.is_some() { Some(i) } else { None })
354        {
355            let i = u32::try_from(i).unwrap();
356            let intrinsic = UnsafeIntrinsic::from_u32(i);
357            for abi in [Abi::Wasm, Abi::Array] {
358                ret.push_input(move |compiler| {
359                    let symbol = format!(
360                        "unsafe-intrinsics-{}-{}",
361                        match abi {
362                            Abi::Wasm => "wasm-call",
363                            Abi::Array => "array-call",
364                            Abi::Patchable => "patchable-call",
365                        },
366                        intrinsic.name(),
367                    );
368                    Ok(CompileOutput {
369                        key: FuncKey::UnsafeIntrinsic(abi, intrinsic),
370                        function: compiler
371                            .component_compiler()
372                            .compile_intrinsic(tunables, component, types, intrinsic, abi, &symbol)
373                            .with_context(|| format!("failed to compile `{symbol}`"))?,
374                        symbol,
375                        start_srcloc: FilePos::default(),
376                        translation: None,
377                        func_body: None,
378                    })
379                });
380            }
381        }
382
383        for (idx, trampoline) in component.trampolines.iter() {
384            for abi in [Abi::Wasm, Abi::Array] {
385                ret.push_input(move |compiler| {
386                    let key = FuncKey::ComponentTrampoline(abi, idx);
387                    let symbol = format!(
388                        "component-trampolines[{}]-{}-{}",
389                        idx.as_u32(),
390                        match abi {
391                            Abi::Wasm => "wasm-call",
392                            Abi::Array => "array-call",
393                            Abi::Patchable => "patchable-call",
394                        },
395                        trampoline.symbol_name(),
396                    );
397                    let function = compiler
398                        .component_compiler()
399                        .compile_component_trampoline(component, types, key, abi, tunables, &symbol)
400                        .with_context(|| format!("failed to compile {symbol}"))?;
401                    Ok(CompileOutput {
402                        key,
403                        function,
404                        symbol,
405                        start_srcloc: FilePos::default(),
406                        translation: None,
407                        func_body: None,
408                    })
409                });
410            }
411        }
412
413        // If there are any resources defined within this component, the
414        // signature for `resource.drop` is mentioned somewhere, and the
415        // wasm-to-native trampoline for `resource.drop` hasn't been created yet
416        // then insert that here. This is possibly required by destruction of
417        // resources from the embedder and otherwise won't be explicitly
418        // requested through initializers above or such.
419        if component.component.num_resources > 0 {
420            if types
421                .module_types_builder()
422                .find_resource_drop_signature()
423                .is_some()
424            {
425                ret.push_input(move |compiler| {
426                    let key = FuncKey::ResourceDropTrampoline;
427                    let symbol = "resource_drop_trampoline".to_string();
428                    let function = compiler
429                        .compile_trampoline(None, key, types.module_types_builder(), &symbol)
430                        .with_context(|| format!("failed to compile `{symbol}`"))?;
431                    Ok(CompileOutput {
432                        key,
433                        function,
434                        symbol,
435                        start_srcloc: FilePos::default(),
436                        translation: None,
437                        func_body: None,
438                    })
439                });
440            }
441        }
442
443        ret
444    }
445
446    fn clean_symbol(name: &str) -> Cow<'_, str> {
447        /// Maximum length of symbols generated in objects.
448        const MAX_SYMBOL_LEN: usize = 96;
449
450        // Just to be on the safe side, filter out characters that could
451        // pose issues to tools such as "perf" or "objdump".  To avoid
452        // having to update a list of allowed characters for each different
453        // language that compiles to Wasm, allows only graphic ASCII
454        // characters; replace runs of everything else with a "?".
455        let bad_char = |c: char| !c.is_ascii_graphic();
456        if name.chars().any(bad_char) {
457            let mut last_char_seen = '\u{0000}';
458            Cow::Owned(
459                name.chars()
460                    .map(|c| if bad_char(c) { '?' } else { c })
461                    .filter(|c| {
462                        let skip = last_char_seen == '?' && *c == '?';
463                        last_char_seen = *c;
464                        !skip
465                    })
466                    .take(MAX_SYMBOL_LEN)
467                    .collect::<String>(),
468            )
469        } else if name.len() <= MAX_SYMBOL_LEN {
470            Cow::Borrowed(&name[..])
471        } else {
472            Cow::Borrowed(&name[..MAX_SYMBOL_LEN])
473        }
474    }
475
476    fn collect_inputs_in_translations(
477        &mut self,
478        types: &'a ModuleTypesBuilder,
479        component: Option<wasmtime_environ::EnclosingComponent<'a>>,
480        translations: impl IntoIterator<
481            Item = (
482                StaticModuleIndex,
483                &'a ModuleTranslation<'a>,
484                PrimaryMap<DefinedFuncIndex, FunctionBodyData<'a>>,
485            ),
486        >,
487    ) {
488        for (module, translation, functions) in translations {
489            for (def_func_index, func_body_data) in functions {
490                self.push_input(move |compiler| {
491                    let key = FuncKey::DefinedWasmFunction(module, def_func_index);
492                    let func_index = translation.module.func_index(def_func_index);
493                    let symbol = match translation
494                        .debuginfo
495                        .name_section
496                        .func_names
497                        .get(&func_index)
498                    {
499                        Some(name) => format!(
500                            "wasm[{}]::function[{}]::{}",
501                            module.as_u32(),
502                            func_index.as_u32(),
503                            Self::clean_symbol(&name)
504                        ),
505                        None => format!(
506                            "wasm[{}]::function[{}]",
507                            module.as_u32(),
508                            func_index.as_u32()
509                        ),
510                    };
511                    let func_body = func_body_data.body.clone();
512                    let data = func_body.get_binary_reader();
513                    let offset = data.original_position();
514                    let start_srcloc = FilePos::new(u32::try_from(offset).unwrap());
515                    let function = compiler
516                        .compile_function(
517                            translation,
518                            key,
519                            func_body_data,
520                            types,
521                            component,
522                            &symbol,
523                        )
524                        .with_context(|| format!("failed to compile: {symbol}"))?;
525
526                    Ok(CompileOutput {
527                        key,
528                        symbol,
529                        function,
530                        start_srcloc,
531                        translation: Some(translation),
532                        func_body: Some(func_body),
533                    })
534                });
535
536                let func_index = translation.module.func_index(def_func_index);
537                if translation.module.functions[func_index].is_escaping() {
538                    self.push_input(move |compiler| {
539                        let key = FuncKey::ArrayToWasmTrampoline(module, def_func_index);
540                        let func_index = translation.module.func_index(def_func_index);
541                        let symbol = format!(
542                            "wasm[{}]::array_to_wasm_trampoline[{}]",
543                            module.as_u32(),
544                            func_index.as_u32()
545                        );
546                        let function = compiler
547                            .compile_trampoline(Some(translation), key, types, &symbol)
548                            .with_context(|| format!("failed to compile: {symbol}"))?;
549                        Ok(CompileOutput {
550                            key,
551                            symbol,
552                            function,
553                            start_srcloc: FilePos::default(),
554                            translation: None,
555                            func_body: None,
556                        })
557                    });
558                }
559            }
560
561            if !translation.module.startup.is_none() {
562                for abi in [Abi::Wasm, Abi::Array] {
563                    self.push_input(move |compiler| {
564                        let key = FuncKey::ModuleStartup(abi, module);
565                        let symbol = format!("module_start[{}]::{abi:?}", module.as_u32());
566                        let function = compiler
567                            .compile_trampoline(Some(translation), key, types, &symbol)
568                            .with_context(|| format!("failed to compile: {symbol}"))?;
569                        Ok(CompileOutput {
570                            key,
571                            function,
572                            symbol,
573                            start_srcloc: FilePos::default(),
574                            translation: None,
575                            func_body: None,
576                        })
577                    });
578                }
579            }
580        }
581
582        let mut trampoline_types_seen = HashSet::new();
583        for (_func_type_index, trampoline_type_index) in types.trampoline_types() {
584            let is_new = trampoline_types_seen.insert(trampoline_type_index);
585            if !is_new {
586                continue;
587            }
588            self.push_input(move |compiler| {
589                let key = FuncKey::WasmToArrayTrampoline(trampoline_type_index);
590                let symbol = format!(
591                    "signatures[{}]::wasm_to_array_trampoline",
592                    trampoline_type_index.as_u32()
593                );
594                let function = compiler
595                    .compile_trampoline(None, key, types, &symbol)
596                    .with_context(|| format!("failed to compile: {symbol}"))?;
597                Ok(CompileOutput {
598                    key,
599                    function,
600                    symbol,
601                    start_srcloc: FilePos::default(),
602                    translation: None,
603                    func_body: None,
604                })
605            });
606        }
607    }
608
609    /// Compile these `CompileInput`s (maybe in parallel) and return the
610    /// resulting `UnlinkedCompileOutput`s.
611    fn compile(
612        self,
613        engine: &Engine,
614        types: &'a ModuleTypesBuilder,
615    ) -> Result<UnlinkedCompileOutputs<'a>> {
616        let compiler = engine.try_compiler()?;
617
618        if self.inputs.len() > 0 && cfg!(miri) {
619            bail!(
620                "\
621You are attempting to compile a WebAssembly module or component that contains
622functions in Miri. Running Cranelift through Miri is known to take quite a long
623time and isn't what we want in CI at least. If this is a mistake then you should
624ignore this test in Miri with:
625
626    #[cfg_attr(miri, ignore)]
627
628If this is not a mistake then try to edit the `pulley_provenance_test` test
629which runs Cranelift outside of Miri. If you still feel this is a mistake then
630please open an issue or a topic on Zulip to talk about how best to accommodate
631the use case.
632"
633            );
634        }
635
636        let mut raw_outputs = if let Some(inlining_compiler) = compiler.inlining_compiler() {
637            if engine.tunables().inlining != Inlining::No {
638                self.compile_with_inlining(engine, compiler, inlining_compiler)?
639            } else {
640                // Inlining compiler but inlining is disabled: compile each
641                // input and immediately finish its output in parallel, skipping
642                // call graph computation and all that.
643                engine.run_maybe_parallel::<_, _, Error, _>(self.inputs, |f| {
644                    let mut compiled = f(compiler)?;
645                    inlining_compiler.finish_compiling(
646                        &mut compiled.function,
647                        compiled.func_body.take(),
648                        &compiled.symbol,
649                    )?;
650                    Ok(compiled)
651                })?
652            }
653        } else {
654            // No inlining: just compile each individual input in parallel.
655            engine.run_maybe_parallel(self.inputs, |f| f(compiler))?
656        };
657
658        if cfg!(debug_assertions) {
659            let mut symbols: Vec<_> = raw_outputs.iter().map(|i| &i.symbol).collect();
660            symbols.sort();
661            for [a, b] in symbols.array_windows() {
662                assert_ne!(
663                    a, b,
664                    "should never have duplicate symbols, but found two functions with the symbol `{a}`",
665                );
666            }
667        }
668
669        // Now that all functions have been compiled see if any
670        // wasmtime-builtin functions are necessary. If so those need to be
671        // collected and then those trampolines additionally need to be
672        // compiled.
673        compile_required_builtins(engine, types, &mut raw_outputs)?;
674
675        // Sort the outputs by their `FuncKey` which enables deterministically
676        // linking this output by function kind.
677        let mut outputs = raw_outputs;
678        outputs.sort_unstable_by_key(|output| output.key);
679
680        Ok(UnlinkedCompileOutputs { outputs })
681    }
682
683    fn compile_with_inlining(
684        self,
685        engine: &Engine,
686        compiler: &dyn Compiler,
687        inlining_compiler: &dyn InliningCompiler,
688    ) -> Result<Vec<CompileOutput<'a>>, Error> {
689        // Our list of unlinked outputs.
690        let mut outputs = PrimaryMap::<OutputIndex, Option<CompileOutput<'_>>>::from(
691            engine.run_maybe_parallel(self.inputs, |f| f(compiler).map(Some))?,
692        );
693
694        // A map from a `FuncKey` to its index in our unlinked outputs.
695        //
696        // We will generally just be working with `OutputIndex`es, but
697        // occasionally we must translate from keys back to our index space, for
698        // example when we know that one module's function import is always
699        // satisfied with a particular `FuncKey::DefinedWasmFunction`. This map
700        // enables that translation.
701        let key_to_output: HashMap<FuncKey, OutputIndex> = inlining_functions(&outputs)
702            .map(|output_index| {
703                let output = outputs[output_index].as_ref().unwrap();
704                (output.key, output_index)
705            })
706            .collect();
707
708        // Construct the call graph for inlining.
709        //
710        // We only inline Wasm functions, not trampolines, because we rely on
711        // trampolines being in their own stack frame when we save the entry and
712        // exit SP, FP, and PC for backtraces in trampolines.
713        let call_graph = EntityGraph::<OutputIndex>::new(inlining_functions(&outputs), {
714            let mut func_keys = IndexSet::default();
715            let outputs = &outputs;
716            let key_to_output = &key_to_output;
717            move |output_index, calls| {
718                let output = outputs[output_index].as_ref().unwrap();
719                debug_assert!(is_inlining_function(output.key));
720
721                // Get this function's call graph edges as `FuncKey`s.
722                func_keys.clear();
723                inlining_compiler.calls(&output.function, &mut func_keys)?;
724
725                // Translate each of those to keys to output indices, which is
726                // what we actually need.
727                debug_assert!(calls.is_empty());
728                calls.extend(
729                    func_keys
730                        .iter()
731                        .copied()
732                        .filter_map(|key| key_to_output.get(&key).copied()),
733                );
734
735                log::trace!(
736                    "call graph edges for {output_index:?} = {:?}: {calls:?}",
737                    output.key
738                );
739
740                crate::error::Ok(())
741            }
742        })?;
743
744        // Stratify the call graph into a sequence of layers. We process each
745        // layer in order, but process functions within a layer in parallel
746        // (because they either do not call each other or are part of a
747        // mutual-recursion cycle; either way we won't inline members of the
748        // same layer into each other).
749        let strata = stratify::Strata::<OutputIndex>::new(&call_graph.filter_nodes(|f| {
750            let key = outputs[*f].as_ref().unwrap().key;
751            is_inlining_function(key)
752        }));
753        let mut layer_outputs = vec![];
754        for layer in strata.layers() {
755            // Temporarily take this layer's outputs out of our unlinked outputs
756            // list so that we can mutate these outputs (by inlining callee
757            // functions into them) while also accessing shared borrows of the
758            // unlinked outputs list (finding the callee functions we will
759            // inline).
760            debug_assert!(layer_outputs.is_empty());
761            layer_outputs.extend(layer.iter().map(|f| outputs[*f].take().unwrap()));
762
763            // Process this layer's members in parallel.
764            engine.run_maybe_parallel_mut(
765                &mut layer_outputs,
766                |output: &mut CompileOutput<'_>| {
767                    log::trace!("processing inlining for {:?}", output.key);
768                    debug_assert!(is_inlining_function(output.key));
769
770                    let caller_key = output.key;
771                    let caller_needs_gc_heap =
772                        output.translation.is_some_and(|t| t.module.needs_gc_heap);
773                    let caller = &mut output.function;
774
775                    let mut caller_size = inlining_compiler.size(caller);
776
777                    inlining_compiler.inline(
778                        caller,
779                        &mut |callee_key: FuncKey, call_site: CallSite| {
780                            log::trace!("  --> considering call to {callee_key:?}");
781                            let callee_output_index: OutputIndex = key_to_output[&callee_key];
782
783                            // NB: If the callee is not inside `outputs`, then it is
784                            // in the same `Strata` layer as the caller (and
785                            // therefore is in the same strongly-connected component
786                            // as the caller, and they mutually recursive). In this
787                            // case, we do not do any inlining; communicate this
788                            // command via `?`-propagation.
789                            let callee_output = outputs[callee_output_index].as_ref()?;
790
791                            debug_assert_eq!(callee_output.key, callee_key);
792
793                            let callee = &callee_output.function;
794                            let callee_size = inlining_compiler.size(callee);
795
796                            let callee_needs_gc_heap = callee_output
797                                .translation
798                                .is_some_and(|t| t.module.needs_gc_heap);
799
800                            if Self::should_inline(InlineHeuristicParams {
801                                tunables: engine.tunables(),
802                                caller_size,
803                                caller_key,
804                                caller_needs_gc_heap,
805                                callee_size,
806                                callee_key,
807                                callee_needs_gc_heap,
808                                call_site_is_cold: call_site.is_cold,
809                            }) {
810                                caller_size = caller_size.saturating_add(callee_size);
811                                Some(callee)
812                            } else {
813                                None
814                            }
815                        },
816                    )
817                },
818            )?;
819
820            for (f, func) in layer.iter().zip(layer_outputs.drain(..)) {
821                debug_assert!(outputs[*f].is_none());
822                outputs[*f] = Some(func);
823            }
824        }
825
826        // Fan out in parallel again and finish compiling each function.
827        engine.run_maybe_parallel(outputs.into(), |output| {
828            let mut output = output.unwrap();
829            inlining_compiler.finish_compiling(
830                &mut output.function,
831                output.func_body.take(),
832                &output.symbol,
833            )?;
834            Ok(output)
835        })
836    }
837
838    /// Implementation of our inlining heuristics.
839    ///
840    /// TODO: We should improve our heuristics:
841    ///
842    /// * One potentially promising hint that we don't currently make use of is
843    ///   how many times a function appears as the callee in call sites. For
844    ///   example, a function that appears in only a single call site, and does
845    ///   not otherwise escape, is often beneficial to inline regardless of its
846    ///   size (assuming we can then GC away the non-inlined version of the
847    ///   function, which we do not currently attempt to do).
848    ///
849    /// * Another potentially promising hint would be whether any of the call
850    ///   site's actual arguments are constants.
851    ///
852    /// * A general improvement would be removing the decision-tree style of
853    ///   control flow below and replacing it with (1) a pure estimated-benefit
854    ///   formula and (2) a benefit threshold. Whenever the estimated benefit
855    ///   reaches the threshold, we would inline the call. Both the formula and
856    ///   the threshold would be parameterized by tunables. This would
857    ///   effectively allow reprioritizing the relative importance of different
858    ///   hint sources, rather than being stuck with the sequence hard-coded in
859    ///   the decision tree below.
860    fn should_inline(
861        InlineHeuristicParams {
862            tunables,
863            caller_size,
864            caller_key,
865            caller_needs_gc_heap,
866            callee_size,
867            callee_key,
868            callee_needs_gc_heap,
869            call_site_is_cold,
870        }: InlineHeuristicParams,
871    ) -> bool {
872        log::trace!(
873            "considering inlining:\n\
874             \tcaller = {caller_key:?}\n\
875             \t\tsize = {caller_size}\n\
876             \t\tneeds_gc_heap = {caller_needs_gc_heap}\n\
877             \tcallee = {callee_key:?}\n\
878             \t\tsize = {callee_size}\n\
879             \t\tneeds_gc_heap = {callee_needs_gc_heap}\n\
880             \tcall_site_is_cold = {call_site_is_cold}"
881        );
882
883        debug_assert!(
884            tunables.inlining != Inlining::No,
885            "shouldn't even call this method if we aren't configured for inlining"
886        );
887        debug_assert_ne!(caller_key, callee_key, "we never inline recursion");
888
889        // Don't inline into cold call sites: doing so bloats code that is
890        // rarely executed and provides little benefit.
891        if call_site_is_cold {
892            log::trace!("  --> not inlining: call site is cold");
893            return false;
894        }
895
896        // Put a limit on how large we can make a function via inlining to cap
897        // code bloat.
898        let sum_size = caller_size.saturating_add(callee_size);
899        if sum_size > tunables.inlining_sum_size_threshold {
900            log::trace!(
901                "  --> not inlining: the sum of the caller's and callee's sizes is greater than \
902                 the inlining-sum-size threshold: {callee_size} + {caller_size} > {}",
903                tunables.inlining_sum_size_threshold
904            );
905            return false;
906        }
907
908        // Skip inlining into array-abi functions which are entry
909        // trampolines into wasm. ABI-wise it's required that these have a
910        // single `try_call` into the module and it doesn't work if multiple
911        // get inlined or if the `try_call` goes away. Prevent all inlining
912        // to guarantee the structure of entry trampolines.
913        if caller_key.abi() == Abi::Array {
914            log::trace!("  --> not inlining: not inlining into array-abi caller");
915            return false;
916        }
917
918        // Consider whether this is an intra-module call.
919        //
920        // Inlining within a single core module has most often already been done
921        // by the toolchain that produced the module, e.g. LLVM, and any extant
922        // function calls to small callees were presumably annotated with the
923        // equivalent of `#[inline(never)]` or `#[cold]` but we don't have that
924        // information anymore.
925        match (caller_key, callee_key) {
926            (
927                FuncKey::DefinedWasmFunction(caller_module, _),
928                FuncKey::DefinedWasmFunction(callee_module, _),
929            ) => match tunables.inlining {
930                Inlining::Yes => {}
931
932                Inlining::InterModuleAndIntraGc => {
933                    if caller_module == callee_module && !caller_needs_gc_heap {
934                        log::trace!("  --> not inlining: intra-module call where GC is not used");
935                        return false;
936                    }
937                }
938
939                Inlining::InterModule => {
940                    if caller_module == callee_module {
941                        log::trace!("  --> not inlining: only inter-module calls inlined");
942                        return false;
943                    }
944                }
945
946                Inlining::Intrinsics => {
947                    log::trace!("  --> not inlining: only inlining intrinsics");
948                    return false;
949                }
950
951                Inlining::No => unreachable!(),
952            },
953            _ => {}
954        }
955
956        // Small callees are often worth inlining regardless of the size of the
957        // caller.
958        if callee_size <= tunables.inlining_small_callee_size {
959            log::trace!(
960                "  --> inlining: callee's size is less than the small-callee size: \
961                 {callee_size} <= {}",
962                tunables.inlining_small_callee_size
963            );
964            return true;
965        }
966
967        log::trace!("  --> inlining: did not find a reason we should not");
968        true
969    }
970}
971
972/// The index of a function (of any kind: Wasm function, trampoline, or
973/// etc...) in our list of unlinked outputs.
974#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
975struct OutputIndex(u32);
976wasmtime_environ::entity_impl!(OutputIndex);
977
978/// Whether a function (as described by the given `FuncKey`) can
979/// participate in inlining or not (either as a candidate for being
980/// inlined into a caller or having a callee inlined into a callsite
981/// within itself).
982fn is_inlining_function(key: FuncKey) -> bool {
983    match key {
984        // Wasm functions can both be inlined into other functions and
985        // have other functions inlined into them.
986        FuncKey::DefinedWasmFunction(..) => true,
987
988        // Intrinsics can be inlined into other functions.
989        FuncKey::UnsafeIntrinsic(..) => true,
990
991        // Trampolines cannot participate in inlining since our
992        // unwinding and exceptions infrastructure relies on them being
993        // in their own call frames.
994        FuncKey::ArrayToWasmTrampoline(..)
995        | FuncKey::WasmToArrayTrampoline(..)
996        | FuncKey::WasmToBuiltinTrampoline(..)
997        | FuncKey::PatchableToBuiltinTrampoline(..)
998        | FuncKey::ModuleStartup(..) => false,
999        FuncKey::ComponentTrampoline(..) | FuncKey::ResourceDropTrampoline => false,
1000
1001        FuncKey::PulleyHostCall(_) => {
1002            unreachable!("we don't compile artifacts for Pulley host calls")
1003        }
1004    }
1005}
1006
1007/// Get just the output indices of the functions that can participate in
1008/// inlining from our unlinked outputs.
1009fn inlining_functions<'a>(
1010    outputs: &'a PrimaryMap<OutputIndex, Option<CompileOutput<'_>>>,
1011) -> impl Iterator<Item = OutputIndex> + 'a {
1012    outputs.iter().filter_map(|(index, output)| {
1013        if is_inlining_function(output.as_ref().unwrap().key) {
1014            Some(index)
1015        } else {
1016            None
1017        }
1018    })
1019}
1020
1021fn compile_required_builtins<'a>(
1022    engine: &Engine,
1023    types: &'a ModuleTypesBuilder,
1024    raw_outputs: &mut Vec<CompileOutput<'a>>,
1025) -> Result<()> {
1026    let compiler = engine.try_compiler()?;
1027    let mut builtins = HashSet::new();
1028    let mut new_inputs: Vec<CompileInput<'_>> = Vec::new();
1029
1030    let compile_builtin = |key: FuncKey| {
1031        Box::new(move |compiler: &dyn Compiler| {
1032            let symbol = match key {
1033                FuncKey::WasmToBuiltinTrampoline(builtin) => {
1034                    format!("wasmtime_builtin_{}", builtin.name())
1035                }
1036                FuncKey::PatchableToBuiltinTrampoline(builtin) => {
1037                    format!("wasmtime_patchable_builtin_{}", builtin.name())
1038                }
1039                _ => unreachable!(),
1040            };
1041            let mut function = compiler
1042                .compile_trampoline(None, key, types, &symbol)
1043                .with_context(|| format!("failed to compile `{symbol}`"))?;
1044            if let Some(compiler) = compiler.inlining_compiler() {
1045                compiler.finish_compiling(&mut function, None, &symbol)?;
1046            }
1047            Ok(CompileOutput {
1048                key,
1049                function,
1050                symbol,
1051                start_srcloc: FilePos::default(),
1052                translation: None,
1053                func_body: None,
1054            })
1055        })
1056    };
1057
1058    for output in raw_outputs.iter() {
1059        for reloc in compiler.compiled_function_relocation_targets(&*output.function.code) {
1060            match reloc {
1061                FuncKey::WasmToBuiltinTrampoline(builtin)
1062                | FuncKey::PatchableToBuiltinTrampoline(builtin) => {
1063                    if builtins.insert(builtin) {
1064                        new_inputs.push(compile_builtin(reloc));
1065                    }
1066                }
1067                _ => {}
1068            }
1069        }
1070    }
1071    raw_outputs.extend(engine.run_maybe_parallel(new_inputs, |c| c(compiler))?);
1072    Ok(())
1073}
1074
1075#[derive(Default)]
1076struct UnlinkedCompileOutputs<'a> {
1077    // The compile outputs, sorted by `FuncKey`.
1078    outputs: Vec<CompileOutput<'a>>,
1079}
1080
1081impl UnlinkedCompileOutputs<'_> {
1082    /// Flatten all our functions into a single list and remember each of their
1083    /// indices within it.
1084    fn pre_link(self) -> PreLinkOutput {
1085        // We must ensure that `compiled_funcs` contains the function bodies
1086        // sorted by their `FuncKey`, as `CompiledFunctionsTable` relies on that
1087        // property.
1088        //
1089        // Furthermore, note that, because the order functions end up in
1090        // `compiled_funcs` is the order they will ultimately be laid out inside
1091        // the object file, we will group all trampolines together, all defined
1092        // Wasm functions from the same module together, and etc... This is a
1093        // nice property, because it means that (a) cold functions, like builtin
1094        // trampolines, are not interspersed between hot Wasm functions, and (b)
1095        // Wasm functions that are likely to call each other (i.e. are in the
1096        // same module together) are grouped together.
1097        let num_funcs = self.outputs.len();
1098        let mut compiled_funcs = Vec::with_capacity(num_funcs);
1099
1100        let mut indices = FunctionIndices {
1101            start_srclocs: HashMap::with_capacity(num_funcs),
1102            indices: HashMap::with_capacity(num_funcs),
1103        };
1104        let mut needs_gc_heap = false;
1105
1106        for output in self.outputs {
1107            needs_gc_heap |= output.function.needs_gc_heap;
1108
1109            let index = compiled_funcs.len();
1110            compiled_funcs.push((output.symbol, output.key, output.function.code));
1111
1112            if output.start_srcloc != FilePos::none() {
1113                indices
1114                    .start_srclocs
1115                    .insert(output.key, output.start_srcloc);
1116            }
1117
1118            indices.indices.insert(output.key, index);
1119        }
1120
1121        PreLinkOutput {
1122            needs_gc_heap,
1123            compiled_funcs,
1124            indices,
1125        }
1126    }
1127}
1128
1129/// Our pre-link functions that have been flattened into a single list.
1130struct PreLinkOutput {
1131    /// Whether or not any of these functions require a GC heap
1132    needs_gc_heap: bool,
1133    /// The flattened list of (symbol name, FuncKey, compiled
1134    /// function) triples, as they will be laid out in the object
1135    /// file.
1136    compiled_funcs: Vec<(String, FuncKey, Box<dyn Any + Send + Sync>)>,
1137    /// The `FunctionIndices` mapping our function keys to indices in that flat
1138    /// list.
1139    indices: FunctionIndices,
1140}
1141
1142#[derive(Default)]
1143struct FunctionIndices {
1144    // A map of wasm functions and where they're located in the original file.
1145    start_srclocs: HashMap<FuncKey, FilePos>,
1146
1147    // The index of each compiled function in `compiled_funcs`.
1148    indices: HashMap<FuncKey, usize>,
1149}
1150
1151impl FunctionIndices {
1152    /// Link the compiled functions together, resolving relocations, and append
1153    /// them to the given ELF file.
1154    fn link_and_append_code<'a>(
1155        self,
1156        mut obj: object::write::Object<'static>,
1157        engine: &'a Engine,
1158        compiled_funcs: Vec<(String, FuncKey, Box<dyn Any + Send + Sync>)>,
1159        translations: PrimaryMap<StaticModuleIndex, ModuleTranslation<'_>>,
1160        dwarf_package_bytes: Option<&[u8]>,
1161    ) -> Result<(wasmtime_environ::ObjectBuilder<'a>, Artifacts)> {
1162        // Append all the functions to the ELF file.
1163        //
1164        // The result is a vector parallel to `compiled_funcs` where
1165        // `symbol_ids_and_locs[i]` is the symbol ID and function location of
1166        // `compiled_funcs[i]`.
1167        let compiler = engine.try_compiler()?;
1168        let tunables = engine.tunables();
1169        let symbol_ids_and_locs = compiler.append_code(
1170            &mut obj,
1171            &compiled_funcs,
1172            &|_caller_index: usize, callee: FuncKey| {
1173                self.indices.get(&callee).copied().unwrap_or_else(|| {
1174                    panic!("cannot resolve relocation! no index for callee {callee:?}")
1175                })
1176            },
1177        )?;
1178
1179        // If requested, generate and add DWARF information.
1180        if tunables.debug_native {
1181            compiler.append_dwarf(
1182                &mut obj,
1183                &translations,
1184                &|module, func| {
1185                    let i = self.indices[&FuncKey::DefinedWasmFunction(module, func)];
1186                    let (symbol, _) = symbol_ids_and_locs[i];
1187                    let (_, _, compiled_func) = &compiled_funcs[i];
1188                    (symbol, &**compiled_func)
1189                },
1190                dwarf_package_bytes,
1191                tunables,
1192            )?;
1193        }
1194
1195        let mut table_builder = CompiledFunctionsTableBuilder::new();
1196        for ((_, key, _), (_, func_loc)) in compiled_funcs.iter().zip(&symbol_ids_and_locs) {
1197            let src_loc = self
1198                .start_srclocs
1199                .get(key)
1200                .copied()
1201                .unwrap_or_else(FilePos::none);
1202            table_builder.push_func(*key, *func_loc, src_loc);
1203        }
1204
1205        let mut obj = wasmtime_environ::ObjectBuilder::new(obj, tunables);
1206        let modules = translations
1207            .into_iter()
1208            .map(|(_, translation)| obj.append(translation))
1209            .collect::<Result<PrimaryMap<_, _>>>()?;
1210
1211        let artifacts = Artifacts {
1212            modules,
1213            table: table_builder.finish(),
1214        };
1215
1216        Ok((obj, artifacts))
1217    }
1218}
1219
1220/// The artifacts necessary for finding and calling Wasm functions at runtime,
1221/// to be serialized into an ELF file.
1222struct Artifacts {
1223    modules: PrimaryMap<StaticModuleIndex, CompiledModuleInfo>,
1224    table: CompiledFunctionsTable,
1225}
1226
1227impl Artifacts {
1228    /// Assuming this compilation was for a single core Wasm module, get the
1229    /// resulting `CompiledModuleInfo`.
1230    fn unwrap_as_module_info(self) -> (CompiledModuleInfo, CompiledFunctionsTable) {
1231        assert_eq!(self.modules.len(), 1);
1232        let info = self.modules.into_iter().next().unwrap().1;
1233        let table = self.table;
1234        (info, table)
1235    }
1236}
1237
1238/// Extend `dest` with `items` and return the range of indices in `dest` where
1239/// they ended up.
1240fn extend_with_range<T>(dest: &mut Vec<T>, items: impl IntoIterator<Item = T>) -> Range<u32> {
1241    let start = dest.len();
1242    let start = u32::try_from(start).unwrap();
1243
1244    dest.extend(items);
1245
1246    let end = dest.len();
1247    let end = u32::try_from(end).unwrap();
1248
1249    start..end
1250}