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