cranelift-codegen 0.133.0

//! Cranelift instruction builder.
//!
//! A `Builder` provides a convenient interface for inserting instructions into a Cranelift
//! function. Many of its methods are generated from the meta language instruction definitions.

use crate::ir;
use crate::ir::immediates::Imm64;
use crate::ir::instructions::InstructionFormat;
use crate::ir::types;
use crate::ir::{BlockArg, Inst, Layout, Opcode, Type, Value};
use crate::ir::{DataFlowGraph, InstructionData};

/// Base trait for instruction builders.
///
/// The `InstBuilderBase` trait provides the basic functionality required by the methods of the
/// generated `InstBuilder` trait. These methods should not normally be used directly. Use the
/// methods in the `InstBuilder` trait instead.
///
/// Any data type that implements `InstBuilderBase` also gets all the methods of the `InstBuilder`
/// trait.
pub trait InstBuilderBase<'f>: Sized {
    /// Get an immutable reference to the data flow graph that will hold the constructed
    /// instructions.
    fn data_flow_graph(&self) -> &DataFlowGraph;
    /// Get a mutable reference to the data flow graph that will hold the constructed
    /// instructions.
    fn data_flow_graph_mut(&mut self) -> &mut DataFlowGraph;

    /// Insert an instruction and return a reference to it, consuming the builder.
    ///
    /// The result types may depend on a controlling type variable. For non-polymorphic
    /// instructions with multiple results, pass `INVALID` for the `ctrl_typevar` argument.
    fn build(self, data: InstructionData, ctrl_typevar: Type) -> (Inst, &'f mut DataFlowGraph);

    /// Build and insert an auxiliary instruction.
    ///
    /// This auxiliary instruction must be inserted before the instruction
    /// this builder will ultimately build.
    ///
    /// This method returns the new instruction, without consuming the builder.
    fn build_aux_inst(&mut self, data: InstructionData, ctrl_typevar: Type) -> Inst;

    /// Materialize an immediate integer constant as an `iconst` (and possibly an
    /// extension), inserting it before the instruction this builder will build,
    /// and return its result value.
    ///
    /// The constant's type is `controlling_type`, or, for vector controlling
    /// types, its lane type. Because `iconst` only supports `i8` through `i64`,
    /// an `i128` constant is built as an `iconst.i64` that is then sign- or
    /// zero-extended.
    ///
    /// Whether the immediate is sign- or zero-extended matches the historical
    /// semantics of the `*_imm` instruction for `base_opcode`:
    ///
    /// * Sign-extended: `iadd`, `imul`, `sdiv`, `srem`, and `icmp`
    /// * Zero-extended: Everything else
    fn build_imm_const(
        &mut self,
        controlling_type: Type,
        imm: Imm64,
        base_opcode: Opcode,
    ) -> Value {
        if controlling_type == types::I128 {
            let mut data = InstructionData::UnaryImm {
                opcode: Opcode::Iconst,
                imm,
            };
            data.mask_immediates(types::I64);
            let lo = self.build_aux_inst(data, types::I64);
            let lo = self.data_flow_graph().first_result(lo);

            // The immediates of these instructions were historically sign-extended
            // by their `*_imm` variants; all the others were zero-extended.
            let opcode = if matches!(
                base_opcode,
                Opcode::Iadd | Opcode::Imul | Opcode::Sdiv | Opcode::Srem | Opcode::Icmp
            ) {
                Opcode::Sextend
            } else {
                Opcode::Uextend
            };
            let ext_inst =
                self.build_aux_inst(InstructionData::Unary { opcode, arg: lo }, types::I128);
            self.data_flow_graph().first_result(ext_inst)
        } else {
            let lane_type = controlling_type.lane_type();
            let mut data = InstructionData::UnaryImm {
                opcode: Opcode::Iconst,
                imm,
            };
            data.mask_immediates(lane_type);
            let inst = self.build_aux_inst(data, lane_type);
            self.data_flow_graph().first_result(inst)
        }
    }
}

// Include trait code generated by `cranelift-codegen/meta/src/gen_inst.rs`.
//
// This file defines the `InstBuilder` trait as an extension of `InstBuilderBase` with methods per
// instruction format and per opcode.
include!(concat!(env!("OUT_DIR"), "/inst_builder.rs"));

/// Any type implementing `InstBuilderBase` gets all the `InstBuilder` methods for free.
impl<'f, T: InstBuilderBase<'f>> InstBuilder<'f> for T {}

/// Base trait for instruction inserters.
///
/// This is an alternative base trait for an instruction builder to implement.
///
/// An instruction inserter can be adapted into an instruction builder by wrapping it in an
/// `InsertBuilder`. This provides some common functionality for instruction builders that insert
/// new instructions, as opposed to the `ReplaceBuilder` which overwrites existing instructions.
pub trait InstInserterBase<'f>: Sized {
    /// Get an immutable reference to the data flow graph.
    fn data_flow_graph(&self) -> &DataFlowGraph;

    /// Get a mutable reference to the data flow graph.
    fn data_flow_graph_mut(&mut self) -> &mut DataFlowGraph;

    /// Insert a new instruction which belongs to the DFG.
    fn insert_built_inst(self, inst: Inst) -> &'f mut DataFlowGraph;

    /// Insert `inst` into the layout at the current position without consuming
    /// the inserter, so that further instructions may be inserted afterward.
    ///
    /// This backs [`InstBuilderBase::build_aux_inst`] for the insertion-based
    /// builders.
    fn insert_aux_inst(&mut self, inst: Inst);
}

use core::marker::PhantomData;

/// Builder that inserts an instruction at the current position.
///
/// An `InsertBuilder` is a wrapper for an `InstInserterBase` that turns it into an instruction
/// builder with some additional facilities for creating instructions that reuse existing values as
/// their results.
pub struct InsertBuilder<'f, IIB: InstInserterBase<'f>> {
    inserter: IIB,
    unused: PhantomData<&'f u32>,
}

impl<'f, IIB: InstInserterBase<'f>> InsertBuilder<'f, IIB> {
    /// Create a new builder which inserts instructions at `pos`.
    /// The `dfg` and `pos.layout` references should be from the same `Function`.
    pub fn new(inserter: IIB) -> Self {
        Self {
            inserter,
            unused: PhantomData,
        }
    }

    /// Reuse result values in `reuse`.
    ///
    /// Convert this builder into one that will reuse the provided result values instead of
    /// allocating new ones. The provided values for reuse must not be attached to anything. Any
    /// missing result values will be allocated as normal.
    ///
    /// The `reuse` argument is expected to be an array of `Option<Value>`.
    pub fn with_results<Array>(self, reuse: Array) -> InsertReuseBuilder<'f, IIB, Array>
    where
        Array: AsRef<[Option<Value>]>,
    {
        InsertReuseBuilder {
            inserter: self.inserter,
            reuse,
            unused: PhantomData,
        }
    }

    /// Reuse a single result value.
    ///
    /// Convert this into a builder that will reuse `v` as the single result value. The reused
    /// result value `v` must not be attached to anything.
    ///
    /// This method should only be used when building an instruction with exactly one result. Use
    /// `with_results()` for the more general case.
    pub fn with_result(self, v: Value) -> InsertReuseBuilder<'f, IIB, [Option<Value>; 1]> {
        // TODO: Specialize this to return a different builder that just attaches `v` instead of
        // calling `make_inst_results_reusing()`.
        self.with_results([Some(v)])
    }
}

impl<'f, IIB: InstInserterBase<'f>> InstBuilderBase<'f> for InsertBuilder<'f, IIB> {
    fn data_flow_graph(&self) -> &DataFlowGraph {
        self.inserter.data_flow_graph()
    }

    fn data_flow_graph_mut(&mut self) -> &mut DataFlowGraph {
        self.inserter.data_flow_graph_mut()
    }

    fn build(mut self, data: InstructionData, ctrl_typevar: Type) -> (Inst, &'f mut DataFlowGraph) {
        let dfg = self.inserter.data_flow_graph_mut();
        let inst = dfg.make_inst(data);
        dfg.make_inst_results(inst, ctrl_typevar);
        (inst, self.inserter.insert_built_inst(inst))
    }

    fn build_aux_inst(&mut self, data: InstructionData, ctrl_typevar: Type) -> Inst {
        let dfg = self.inserter.data_flow_graph_mut();
        let inst = dfg.make_inst(data);
        dfg.make_inst_results(inst, ctrl_typevar);
        self.inserter.insert_aux_inst(inst);
        inst
    }
}

/// Builder that inserts a new instruction like `InsertBuilder`, but reusing result values.
pub struct InsertReuseBuilder<'f, IIB, Array>
where
    IIB: InstInserterBase<'f>,
    Array: AsRef<[Option<Value>]>,
{
    inserter: IIB,
    reuse: Array,
    unused: PhantomData<&'f u32>,
}

impl<'f, IIB, Array> InstBuilderBase<'f> for InsertReuseBuilder<'f, IIB, Array>
where
    IIB: InstInserterBase<'f>,
    Array: AsRef<[Option<Value>]>,
{
    fn data_flow_graph(&self) -> &DataFlowGraph {
        self.inserter.data_flow_graph()
    }

    fn data_flow_graph_mut(&mut self) -> &mut DataFlowGraph {
        self.inserter.data_flow_graph_mut()
    }

    fn build(mut self, data: InstructionData, ctrl_typevar: Type) -> (Inst, &'f mut DataFlowGraph) {
        let dfg = self.inserter.data_flow_graph_mut();
        let inst = dfg.make_inst(data);
        let reuse = self.reuse.as_ref().iter().cloned();
        dfg.make_inst_results_reusing(inst, ctrl_typevar, reuse);
        (inst, self.inserter.insert_built_inst(inst))
    }

    fn build_aux_inst(&mut self, data: InstructionData, ctrl_typevar: Type) -> Inst {
        // Result reuse only applies to the final, builder-consuming instruction;
        // auxiliary instructions always get freshly allocated results.
        let inst;
        {
            let dfg = self.inserter.data_flow_graph_mut();
            inst = dfg.make_inst(data);
            dfg.make_inst_results(inst, ctrl_typevar);
        }
        self.inserter.insert_aux_inst(inst);
        inst
    }
}

/// Instruction builder that replaces an existing instruction.
///
/// The inserted instruction will have the same `Inst` number as the old one.
///
/// If the old instruction still has result values attached, it is assumed that the new instruction
/// produces the same number and types of results. The old result values are preserved. If the
/// replacement instruction format does not support multiple results, the builder panics. It is a
/// bug to leave result values dangling.
pub struct ReplaceBuilder<'f> {
    dfg: &'f mut DataFlowGraph,
    layout: &'f mut Layout,
    inst: Inst,
}

impl<'f> ReplaceBuilder<'f> {
    /// Create a `ReplaceBuilder` that will overwrite `inst`.
    pub fn new(dfg: &'f mut DataFlowGraph, layout: &'f mut Layout, inst: Inst) -> Self {
        Self { dfg, layout, inst }
    }
}

impl<'f> InstBuilderBase<'f> for ReplaceBuilder<'f> {
    fn data_flow_graph(&self) -> &DataFlowGraph {
        self.dfg
    }

    fn data_flow_graph_mut(&mut self) -> &mut DataFlowGraph {
        self.dfg
    }

    fn build(self, data: InstructionData, ctrl_typevar: Type) -> (Inst, &'f mut DataFlowGraph) {
        // Splat the new instruction on top of the old one.
        self.dfg.insts[self.inst] = data;

        if !self.dfg.has_results(self.inst) {
            // The old result values were either detached or non-existent.
            // Construct new ones.
            self.dfg.make_inst_results(self.inst, ctrl_typevar);
        }

        (self.inst, self.dfg)
    }

    fn build_aux_inst(&mut self, data: InstructionData, ctrl_typevar: Type) -> Inst {
        // Auxiliary instructions are inserted into the layout immediately
        // before the instruction being replaced.
        let inst = self.dfg.make_inst(data);
        self.dfg.make_inst_results(inst, ctrl_typevar);
        self.layout.insert_inst(inst, self.inst);
        inst
    }
}

#[cfg(test)]
mod tests {
    use crate::cursor::{Cursor, FuncCursor};
    use crate::ir::condcodes::*;
    use crate::ir::types::*;
    use crate::ir::{Function, InstBuilder, Opcode, ValueDef};

    #[test]
    fn types() {
        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let arg0 = func.dfg.append_block_param(block0, I32);
        let mut pos = FuncCursor::new(&mut func);
        pos.insert_block(block0);

        // Explicit types.
        let v0 = pos.ins().iconst(I32, 3);
        assert_eq!(pos.func.dfg.value_type(v0), I32);

        // Inferred from inputs.
        let v1 = pos.ins().iadd(arg0, v0);
        assert_eq!(pos.func.dfg.value_type(v1), I32);

        // Formula.
        let cmp = pos.ins().icmp(IntCC::Equal, arg0, v0);
        assert_eq!(pos.func.dfg.value_type(cmp), I8);
    }

    #[test]
    fn reuse_results() {
        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let arg0 = func.dfg.append_block_param(block0, I32);
        let mut pos = FuncCursor::new(&mut func);
        pos.insert_block(block0);

        let v0 = pos.ins().iadd_imm(arg0, 17);
        assert_eq!(pos.func.dfg.value_type(v0), I32);
        let iadd = pos.prev_inst().unwrap();
        assert_eq!(pos.func.dfg.value_def(v0), ValueDef::Result(iadd, 0));

        // Detach v0 and reuse it for a different instruction.
        pos.func.dfg.clear_results(iadd);
        let v0b = pos.ins().with_result(v0).iconst(I32, 3);
        assert_eq!(v0, v0b);
        assert_eq!(pos.current_inst(), Some(iadd));
        let iconst = pos.prev_inst().unwrap();
        assert!(iadd != iconst);
        assert_eq!(pos.func.dfg.value_def(v0), ValueDef::Result(iconst, 0));
    }

    #[test]
    fn replace_with_imm_method() {
        // Replacing an instruction with a generated `*_imm` convenience method
        // (here `icmp_imm`) must materialize its `iconst` immediately before the
        // replaced instruction via `ReplaceBuilder::build_aux_inst`.
        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let arg0 = func.dfg.append_block_param(block0, I32);
        {
            let mut pos = FuncCursor::new(&mut func);
            pos.insert_block(block0);
            // A placeholder `icmp` (also `i8`-typed) to be replaced.
            pos.ins().icmp(IntCC::Equal, arg0, arg0);
        }

        let inst = func.layout.last_inst(block0).unwrap();
        assert_eq!(func.dfg.insts[inst].opcode(), Opcode::Icmp);

        let result = func.replace(inst).icmp_imm(IntCC::Equal, arg0, 42);

        // The replaced instruction is still an `icmp`, now comparing against a
        // freshly materialized constant.
        assert_eq!(func.dfg.insts[inst].opcode(), Opcode::Icmp);
        assert_eq!(func.dfg.value_type(result), I8);

        // An `iconst.i32 42` was inserted immediately before the replaced inst.
        let iconst = func.layout.prev_inst(inst).unwrap();
        assert_eq!(func.dfg.insts[iconst].opcode(), Opcode::Iconst);
        let iconst_result = func.dfg.first_result(iconst);
        assert_eq!(func.dfg.value_type(iconst_result), I32);
        assert_eq!(func.dfg.inst_args(inst), &[arg0, iconst_result]);
    }

    #[test]
    #[should_panic]
    #[cfg(debug_assertions)]
    fn panics_when_inserting_wrong_opcode() {
        use crate::ir::{Opcode, TrapCode};

        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let mut pos = FuncCursor::new(&mut func);
        pos.insert_block(block0);

        // We are trying to create a Opcode::Return with the InstData::Trap, which is obviously wrong
        pos.ins()
            .Trap(Opcode::Return, I32, TrapCode::BAD_CONVERSION_TO_INTEGER);
    }
}