cranelift_codegen/ir/
function.rs

1//! Intermediate representation of a function.
2//!
3//! The `Function` struct defined in this module owns all of its basic blocks and
4//! instructions.
5
6use crate::HashMap;
7use crate::entity::{PrimaryMap, SecondaryMap};
8use crate::ir::DebugTags;
9use crate::ir::{
10    self, Block, DataFlowGraph, DynamicStackSlot, DynamicStackSlotData, DynamicStackSlots,
11    DynamicType, ExtFuncData, FuncRef, GlobalValue, GlobalValueData, Inst, JumpTable,
12    JumpTableData, Layout, MemoryType, MemoryTypeData, SigRef, Signature, SourceLocs, StackSlot,
13    StackSlotData, StackSlots, Type, pcc::Fact,
14};
15use crate::isa::CallConv;
16use crate::write::{write_function, write_function_spec};
17#[cfg(feature = "enable-serde")]
18use alloc::string::String;
19use core::fmt;
20
21#[cfg(feature = "enable-serde")]
22use serde::de::{Deserializer, Error};
23#[cfg(feature = "enable-serde")]
24use serde::ser::Serializer;
25#[cfg(feature = "enable-serde")]
26use serde::{Deserialize, Serialize};
27
28use super::entities::UserExternalNameRef;
29use super::extname::UserFuncName;
30use super::{RelSourceLoc, SourceLoc, UserExternalName};
31
32/// A version marker used to ensure that serialized clif ir is never deserialized with a
33/// different version of Cranelift.
34#[derive(Default, Copy, Clone, Debug, PartialEq, Hash)]
35pub struct VersionMarker;
36
37#[cfg(feature = "enable-serde")]
38impl Serialize for VersionMarker {
39    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
40    where
41        S: Serializer,
42    {
43        crate::VERSION.serialize(serializer)
44    }
45}
46
47#[cfg(feature = "enable-serde")]
48impl<'de> Deserialize<'de> for VersionMarker {
49    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
50    where
51        D: Deserializer<'de>,
52    {
53        let version = String::deserialize(deserializer)?;
54        if version != crate::VERSION {
55            return Err(D::Error::custom(&format!(
56                "Expected a clif ir function for version {}, found one for version {}",
57                crate::VERSION,
58                version,
59            )));
60        }
61        Ok(VersionMarker)
62    }
63}
64
65/// Function parameters used when creating this function, and that will become applied after
66/// compilation to materialize the final `CompiledCode`.
67#[derive(Clone, PartialEq)]
68#[cfg_attr(
69    feature = "enable-serde",
70    derive(serde_derive::Serialize, serde_derive::Deserialize)
71)]
72pub struct FunctionParameters {
73    /// The first `SourceLoc` appearing in the function, serving as a base for every relative
74    /// source loc in the function.
75    base_srcloc: Option<SourceLoc>,
76
77    /// External user-defined function references.
78    user_named_funcs: PrimaryMap<UserExternalNameRef, UserExternalName>,
79
80    /// Inverted mapping of `user_named_funcs`, to deduplicate internally.
81    user_ext_name_to_ref: HashMap<UserExternalName, UserExternalNameRef>,
82}
83
84impl FunctionParameters {
85    /// Creates a new `FunctionParameters` with the given name.
86    pub fn new() -> Self {
87        Self {
88            base_srcloc: None,
89            user_named_funcs: Default::default(),
90            user_ext_name_to_ref: Default::default(),
91        }
92    }
93
94    /// Returns the base `SourceLoc`.
95    ///
96    /// If it was never explicitly set with `ensure_base_srcloc`, will return an invalid
97    /// `SourceLoc`.
98    pub fn base_srcloc(&self) -> SourceLoc {
99        self.base_srcloc.unwrap_or_default()
100    }
101
102    /// Sets the base `SourceLoc`, if not set yet, and returns the base value.
103    pub fn ensure_base_srcloc(&mut self, srcloc: SourceLoc) -> SourceLoc {
104        match self.base_srcloc {
105            Some(val) => val,
106            None => {
107                self.base_srcloc = Some(srcloc);
108                srcloc
109            }
110        }
111    }
112
113    /// Retrieve a `UserExternalNameRef` for the given name, or add a new one.
114    ///
115    /// This method internally deduplicates same `UserExternalName` so they map to the same
116    /// reference.
117    pub fn ensure_user_func_name(&mut self, name: UserExternalName) -> UserExternalNameRef {
118        if let Some(reff) = self.user_ext_name_to_ref.get(&name) {
119            *reff
120        } else {
121            let reff = self.user_named_funcs.push(name.clone());
122            self.user_ext_name_to_ref.insert(name, reff);
123            reff
124        }
125    }
126
127    /// Resets an already existing user function name to a new value.
128    pub fn reset_user_func_name(&mut self, index: UserExternalNameRef, name: UserExternalName) {
129        if let Some(prev_name) = self.user_named_funcs.get_mut(index) {
130            self.user_ext_name_to_ref.remove(prev_name);
131            *prev_name = name.clone();
132            self.user_ext_name_to_ref.insert(name, index);
133        }
134    }
135
136    /// Returns the internal mapping of `UserExternalNameRef` to `UserExternalName`.
137    pub fn user_named_funcs(&self) -> &PrimaryMap<UserExternalNameRef, UserExternalName> {
138        &self.user_named_funcs
139    }
140
141    fn clear(&mut self) {
142        self.base_srcloc = None;
143        self.user_named_funcs.clear();
144        self.user_ext_name_to_ref.clear();
145    }
146}
147
148/// Function fields needed when compiling a function.
149///
150/// Additionally, these fields can be the same for two functions that would be compiled the same
151/// way, and finalized by applying `FunctionParameters` onto their `CompiledCodeStencil`.
152#[derive(Clone, PartialEq, Hash)]
153#[cfg_attr(
154    feature = "enable-serde",
155    derive(serde_derive::Serialize, serde_derive::Deserialize)
156)]
157pub struct FunctionStencil {
158    /// A version marker used to ensure that serialized clif ir is never deserialized with a
159    /// different version of Cranelift.
160    // Note: This must be the first field to ensure that Serde will deserialize it before
161    // attempting to deserialize other fields that are potentially changed between versions.
162    pub version_marker: VersionMarker,
163
164    /// Signature of this function.
165    pub signature: Signature,
166
167    /// Sized stack slots allocated in this function.
168    pub sized_stack_slots: StackSlots,
169
170    /// Dynamic stack slots allocated in this function.
171    pub dynamic_stack_slots: DynamicStackSlots,
172
173    /// Global values referenced.
174    pub global_values: PrimaryMap<ir::GlobalValue, ir::GlobalValueData>,
175
176    /// Global value proof-carrying-code facts.
177    pub global_value_facts: SecondaryMap<ir::GlobalValue, Option<Fact>>,
178
179    /// Memory types for proof-carrying code.
180    pub memory_types: PrimaryMap<ir::MemoryType, ir::MemoryTypeData>,
181
182    /// Data flow graph containing the primary definition of all instructions, blocks and values.
183    pub dfg: DataFlowGraph,
184
185    /// Layout of blocks and instructions in the function body.
186    pub layout: Layout,
187
188    /// Source locations.
189    ///
190    /// Track the original source location for each instruction. The source locations are not
191    /// interpreted by Cranelift, only preserved.
192    pub srclocs: SourceLocs,
193
194    /// Opaque debug-info tags on sequence-point and call
195    /// instructions.
196    ///
197    /// These tags are not interpreted by Cranelift, and are passed
198    /// through to compilation-result metadata. The only semantic
199    /// structure that Cranelift imposes is that when inlining, it
200    /// prepends the callsite call instruction's tags to the tags on
201    /// inlined instructions.
202    ///
203    /// In order to ensure clarity around guaranteed compiler
204    /// behavior, tags are only permitted on instructions whose
205    /// presence and sequence will remain the same in the compiled
206    /// output: namely, `sequence_point` instructions and ordinary
207    /// call instructions.
208    pub debug_tags: DebugTags,
209
210    /// An optional global value which represents an expression evaluating to
211    /// the stack limit for this function. This `GlobalValue` will be
212    /// interpreted in the prologue, if necessary, to insert a stack check to
213    /// ensure that a trap happens if the stack pointer goes below the
214    /// threshold specified here.
215    pub stack_limit: Option<ir::GlobalValue>,
216}
217
218impl FunctionStencil {
219    fn clear(&mut self) {
220        self.signature.clear(CallConv::Fast);
221        self.sized_stack_slots.clear();
222        self.dynamic_stack_slots.clear();
223        self.global_values.clear();
224        self.global_value_facts.clear();
225        self.memory_types.clear();
226        self.dfg.clear();
227        self.layout.clear();
228        self.srclocs.clear();
229        self.debug_tags.clear();
230        self.stack_limit = None;
231    }
232
233    /// Creates a jump table in the function, to be used by `br_table` instructions.
234    pub fn create_jump_table(&mut self, data: JumpTableData) -> JumpTable {
235        self.dfg.jump_tables.push(data)
236    }
237
238    /// Creates a sized stack slot in the function, to be used by `stack_load`, `stack_store`
239    /// and `stack_addr` instructions.
240    pub fn create_sized_stack_slot(&mut self, data: StackSlotData) -> StackSlot {
241        self.sized_stack_slots.push(data)
242    }
243
244    /// Creates a dynamic stack slot in the function, to be used by `dynamic_stack_load`,
245    /// `dynamic_stack_store` and `dynamic_stack_addr` instructions.
246    pub fn create_dynamic_stack_slot(&mut self, data: DynamicStackSlotData) -> DynamicStackSlot {
247        self.dynamic_stack_slots.push(data)
248    }
249
250    /// Adds a signature which can later be used to declare an external function import.
251    pub fn import_signature(&mut self, signature: Signature) -> SigRef {
252        self.dfg.signatures.push(signature)
253    }
254
255    /// Declares a global value accessible to the function.
256    pub fn create_global_value(&mut self, data: GlobalValueData) -> GlobalValue {
257        self.global_values.push(data)
258    }
259
260    /// Declares a memory type for use by the function.
261    pub fn create_memory_type(&mut self, data: MemoryTypeData) -> MemoryType {
262        self.memory_types.push(data)
263    }
264
265    /// Find the global dyn_scale value associated with given DynamicType.
266    pub fn get_dyn_scale(&self, ty: DynamicType) -> GlobalValue {
267        self.dfg.dynamic_types.get(ty).unwrap().dynamic_scale
268    }
269
270    /// Find the global dyn_scale for the given stack slot.
271    pub fn get_dynamic_slot_scale(&self, dss: DynamicStackSlot) -> GlobalValue {
272        let dyn_ty = self.dynamic_stack_slots.get(dss).unwrap().dyn_ty;
273        self.get_dyn_scale(dyn_ty)
274    }
275
276    /// Get a concrete `Type` from a user defined `DynamicType`.
277    pub fn get_concrete_dynamic_ty(&self, ty: DynamicType) -> Option<Type> {
278        self.dfg
279            .dynamic_types
280            .get(ty)
281            .unwrap_or_else(|| panic!("Undeclared dynamic vector type: {ty}"))
282            .concrete()
283    }
284
285    /// Find a presumed unique special-purpose function parameter value.
286    ///
287    /// Returns the value of the last `purpose` parameter, or `None` if no such parameter exists.
288    pub fn special_param(&self, purpose: ir::ArgumentPurpose) -> Option<ir::Value> {
289        let entry = self.layout.entry_block().expect("Function is empty");
290        self.signature
291            .special_param_index(purpose)
292            .map(|i| self.dfg.block_params(entry)[i])
293    }
294
295    /// Starts collection of debug information.
296    pub fn collect_debug_info(&mut self) {
297        self.dfg.collect_debug_info();
298    }
299
300    /// Rewrite the branch destination to `new_dest` if the destination matches `old_dest`.
301    /// Does nothing if called with a non-jump or non-branch instruction.
302    pub fn rewrite_branch_destination(&mut self, inst: Inst, old_dest: Block, new_dest: Block) {
303        for dest in self.dfg.insts[inst]
304            .branch_destination_mut(&mut self.dfg.jump_tables, &mut self.dfg.exception_tables)
305        {
306            if dest.block(&self.dfg.value_lists) == old_dest {
307                dest.set_block(new_dest, &mut self.dfg.value_lists)
308            }
309        }
310    }
311
312    /// Checks that the specified block can be encoded as a basic block.
313    ///
314    /// On error, returns the first invalid instruction and an error message.
315    pub fn is_block_basic(&self, block: Block) -> Result<(), (Inst, &'static str)> {
316        let dfg = &self.dfg;
317        let inst_iter = self.layout.block_insts(block);
318
319        // Ignore all instructions prior to the first branch.
320        let mut inst_iter = inst_iter.skip_while(|&inst| !dfg.insts[inst].opcode().is_branch());
321
322        if let Some(_branch) = inst_iter.next() {
323            if let Some(next) = inst_iter.next() {
324                return Err((next, "post-terminator instruction"));
325            }
326        }
327
328        Ok(())
329    }
330
331    /// Returns an iterator over the blocks succeeding the given block.
332    pub fn block_successors(&self, block: Block) -> impl DoubleEndedIterator<Item = Block> + '_ {
333        self.layout.last_inst(block).into_iter().flat_map(|inst| {
334            self.dfg.insts[inst]
335                .branch_destination(&self.dfg.jump_tables, &self.dfg.exception_tables)
336                .iter()
337                .map(|block| block.block(&self.dfg.value_lists))
338        })
339    }
340
341    /// Replace the `dst` instruction's data with the `src` instruction's data
342    /// and then remove `src`.
343    ///
344    /// `src` and its result values should not be used at all, as any uses would
345    /// be left dangling after calling this method.
346    ///
347    /// `src` and `dst` must have the same number of resulting values, and
348    /// `src`'s i^th value must have the same type as `dst`'s i^th value.
349    pub fn transplant_inst(&mut self, dst: Inst, src: Inst) {
350        debug_assert_eq!(
351            self.dfg.inst_results(dst).len(),
352            self.dfg.inst_results(src).len()
353        );
354        debug_assert!(
355            self.dfg
356                .inst_results(dst)
357                .iter()
358                .zip(self.dfg.inst_results(src))
359                .all(|(a, b)| self.dfg.value_type(*a) == self.dfg.value_type(*b))
360        );
361
362        self.dfg.insts[dst] = self.dfg.insts[src];
363        self.layout.remove_inst(src);
364    }
365
366    /// Size occupied by all stack slots associated with this function.
367    ///
368    /// Does not include any padding necessary due to offsets
369    pub fn fixed_stack_size(&self) -> u32 {
370        self.sized_stack_slots.values().map(|ss| ss.size).sum()
371    }
372
373    /// Returns the list of relative source locations for this function.
374    pub(crate) fn rel_srclocs(&self) -> &SecondaryMap<Inst, RelSourceLoc> {
375        &self.srclocs
376    }
377}
378
379/// Functions can be cloned, but it is not a very fast operation.
380/// The clone will have all the same entity numbers as the original.
381#[derive(Clone, PartialEq)]
382#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
383pub struct Function {
384    /// Name of this function.
385    ///
386    /// Mostly used by `.clif` files, only there for debugging / naming purposes.
387    pub name: UserFuncName,
388
389    /// All the fields required for compiling a function, independently of details irrelevant to
390    /// compilation and that are stored in the `FunctionParameters` `params` field instead.
391    pub stencil: FunctionStencil,
392
393    /// All the parameters that can be applied onto the function stencil, that is, that don't
394    /// matter when caching compilation artifacts.
395    pub params: FunctionParameters,
396}
397
398impl core::ops::Deref for Function {
399    type Target = FunctionStencil;
400
401    fn deref(&self) -> &Self::Target {
402        &self.stencil
403    }
404}
405
406impl core::ops::DerefMut for Function {
407    fn deref_mut(&mut self) -> &mut Self::Target {
408        &mut self.stencil
409    }
410}
411
412impl Function {
413    /// Create a function with the given name and signature.
414    pub fn with_name_signature(name: UserFuncName, sig: Signature) -> Self {
415        Self {
416            name,
417            stencil: FunctionStencil {
418                version_marker: VersionMarker,
419                signature: sig,
420                sized_stack_slots: StackSlots::new(),
421                dynamic_stack_slots: DynamicStackSlots::new(),
422                global_values: PrimaryMap::new(),
423                global_value_facts: SecondaryMap::new(),
424                memory_types: PrimaryMap::new(),
425                dfg: DataFlowGraph::new(),
426                layout: Layout::new(),
427                srclocs: SecondaryMap::new(),
428                stack_limit: None,
429                debug_tags: DebugTags::default(),
430            },
431            params: FunctionParameters::new(),
432        }
433    }
434
435    /// Clear all data structures in this function.
436    pub fn clear(&mut self) {
437        self.stencil.clear();
438        self.params.clear();
439        self.name = UserFuncName::default();
440    }
441
442    /// Create a new empty, anonymous function with a Fast calling convention.
443    pub fn new() -> Self {
444        Self::with_name_signature(Default::default(), Signature::new(CallConv::Fast))
445    }
446
447    /// Return an object that can display this function with correct ISA-specific annotations.
448    pub fn display(&self) -> DisplayFunction<'_> {
449        DisplayFunction(self)
450    }
451
452    /// Return an object that can display this function's name and signature.
453    pub fn display_spec(&self) -> DisplayFunctionSpec<'_> {
454        DisplayFunctionSpec(self)
455    }
456
457    /// Sets an absolute source location for the given instruction.
458    ///
459    /// If no base source location has been set yet, records it at the same time.
460    pub fn set_srcloc(&mut self, inst: Inst, srcloc: SourceLoc) {
461        let base = self.params.ensure_base_srcloc(srcloc);
462        self.stencil.srclocs[inst] = RelSourceLoc::from_base_offset(base, srcloc);
463    }
464
465    /// Returns an absolute source location for the given instruction.
466    pub fn srcloc(&self, inst: Inst) -> SourceLoc {
467        let base = self.params.base_srcloc();
468        self.stencil.srclocs[inst].expand(base)
469    }
470
471    /// Declare a user-defined external function import, to be referenced in `ExtFuncData::User` later.
472    pub fn declare_imported_user_function(
473        &mut self,
474        name: UserExternalName,
475    ) -> UserExternalNameRef {
476        self.params.ensure_user_func_name(name)
477    }
478
479    /// Declare an external function import.
480    pub fn import_function(&mut self, data: ExtFuncData) -> FuncRef {
481        self.stencil.dfg.ext_funcs.push(data)
482    }
483}
484
485/// Wrapper type capable of displaying a `Function`.
486pub struct DisplayFunction<'a>(&'a Function);
487
488impl<'a> fmt::Display for DisplayFunction<'a> {
489    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
490        write_function(fmt, self.0)
491    }
492}
493
494impl fmt::Display for Function {
495    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
496        write_function(fmt, self)
497    }
498}
499
500impl fmt::Debug for Function {
501    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
502        write_function(fmt, self)
503    }
504}
505
506/// Wrapper type capable of displaying a 'Function's name and signature.
507pub struct DisplayFunctionSpec<'a>(&'a Function);
508
509impl<'a> fmt::Display for DisplayFunctionSpec<'a> {
510    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
511        write_function_spec(fmt, self.0)
512    }
513}
514
515impl<'a> fmt::Debug for DisplayFunctionSpec<'a> {
516    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
517        write_function_spec(fmt, self.0)
518    }
519}