Struct Function 

pub struct Function { /* private fields */ }

A machine function.

Blocks hold target instructions in order; the first block is the entry. Instructions name virtual registers (each typed by a register class) or physical registers, stack slots, and other functions by symbol. Control flow passes values between blocks through block parameters: a branch names its target with arguments, and on the edge every parameter receives its argument at once (a parallel copy). Block parameters are SSA’s phi nodes written at the edge, which is the form an SSA register allocator works on and the form ir-lang already uses; see the crate docs for the rationale.

Every table is a dense vector indexed by its id type; nothing is recursive.

Examples

Sum 1..=n with virtual registers:

use backend_lang::mir::{Function, Operand};
use backend_lang::x86_64::{self, op, GPR, SYSV};
use isa_lang::x86_64::Cond;

let mut f = Function::new("sum", &SYSV);
let entry = f.block()?;
let head = f.block()?;
let exit = f.block()?;
let n = f.vreg(GPR)?;
f.add_param(entry, n.into())?;
// Parameters come first: branches are checked against them.
let (acc, i) = (f.vreg(GPR)?, f.vreg(GPR)?);
f.add_param(head, acc.into())?;
f.add_param(head, i.into())?;
let result = f.vreg(GPR)?;
f.add_param(exit, result.into())?;

let zero = f.vreg(GPR)?;
f.push(entry, op::MOV64RI, &[zero.into(), Operand::Imm(0)])?;
let to_head = f.block_call(head, &[zero.into(), n.into()])?;
f.push(entry, op::JMP, &[to_head.into()])?;

let (acc2, i2) = (f.vreg(GPR)?, f.vreg(GPR)?);
f.push(head, op::ADD64, &[acc2.into(), acc.into(), i.into()])?;
f.push(head, op::SUB64, &[i2.into(), i.into(), Operand::Imm(1)])?;
let again = f.block_call(head, &[acc2.into(), i2.into()])?;
let done = f.block_call(exit, &[acc2.into()])?;
f.push(head, op::JCC, &[x86_64::cond(Cond::Ne).into(), again.into(), done.into()])?;

f.push(exit, op::RET, &[])?;

f.verify()?;
assert!(f.to_string().contains("%5:gpr = add64 %1, %2"));

Implementations

impl Function

pub fn verify_ssa(&self) -> Result<(), MirError>

Checks verify’s rules, then SSA dominance: in every block reachable from the entry, each use of a virtual register is dominated by its definition (a use in the defining block comes after the definition; a branch argument is a use at the end of its block). This is the register allocator’s precondition. Linear in the size of the function.

Errors

The first MirError: verify’s errors, then MirError::UndefinedVReg or MirError::NotDominated.

Examples

use backend_lang::mir::{Function, MirError, Operand};
use backend_lang::x86_64::{op, GPR, SYSV};

let mut f = Function::new("f", &SYSV);
let (a, b) = (f.block()?, f.block()?);
let v = f.vreg(GPR)?;
let to_b = f.block_call(b, &[])?;
f.push(a, op::JMP, &[to_b.into()])?;
let w = f.vreg(GPR)?;
f.push(b, op::MOV64, &[w.into(), v.into()])?; // v is never defined
f.push(b, op::RET, &[])?;
assert!(matches!(f.verify_ssa(), Err(MirError::UndefinedVReg { .. })));

impl Function

pub fn new(name: &str, abi: &'static Abi) -> Function

An empty function named name, under calling convention abi (which also fixes the target).

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::WIN64;

let f = Function::new("main", &WIN64);
assert_eq!(f.name(), "main");
assert_eq!(f.abi().name(), "win64");

pub fn with_capacity( name: &str, abi: &'static Abi, insts: usize, operands: usize, ) -> Function

An empty function with room for insts instructions and operands operands, so building a large function does not reallocate.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

let f = Function::with_capacity("big", &SYSV, 100_000, 300_000);
assert_eq!(f.inst_count(), 0);

pub fn name(&self) -> &str

The function’s name, which is also the symbol other functions call it by.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).name(), "f");

pub fn abi(&self) -> &'static Abi

The calling convention.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).abi().name(), "sysv64");

pub fn target(&self) -> &'static Target

The target (the calling convention’s).

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).target().name(), "x86-64");

pub fn vreg(&mut self, class: RegClass) -> Result<Reg, MirError>

A new virtual register of class.

Errors

MirError::UnknownClass if the target has no such class, MirError::Limit past VReg::MAX registers.

Examples

use backend_lang::RegClass;
use backend_lang::mir::{Function, MirError};
use backend_lang::x86_64::{SYSV, VEC};

let mut f = Function::new("f", &SYSV);
assert!(f.vreg(VEC)?.is_virtual());
assert_eq!(f.vreg(RegClass::new(7)), Err(MirError::UnknownClass(RegClass::new(7))));

pub fn vreg_class(&self, vreg: VReg) -> Option<RegClass>

The class of a virtual register, or None if the function does not have it.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::{GPR, SYSV};

let mut f = Function::new("f", &SYSV);
let v = f.vreg(GPR)?.as_virt().unwrap();
assert_eq!(f.vreg_class(v), Some(GPR));

pub fn vreg_count(&self) -> usize

The number of virtual registers.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::{GPR, SYSV};

let mut f = Function::new("f", &SYSV);
let _ = f.vreg(GPR)?;
assert_eq!(f.vreg_count(), 1);

pub fn reg_class(&self, reg: Reg) -> Option<RegClass>

The class of any register: a virtual register’s declared class, or a physical register’s class in the target.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::{GPR, SYSV, VEC, XMM2};

let mut f = Function::new("f", &SYSV);
let v = f.vreg(GPR)?;
assert_eq!(f.reg_class(v), Some(GPR));
assert_eq!(f.reg_class(XMM2.into()), Some(VEC));

pub fn block(&mut self) -> Result<Block, MirError>

A new, empty block. The first block is the entry.

Errors

MirError::Limit past u32::MAX - 1 blocks.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
let entry = f.block()?;
assert_eq!(f.entry(), Some(entry));

pub fn entry(&self) -> Option<Block>

The entry block, if any block exists.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).entry(), None);

pub fn blocks(&self) -> impl ExactSizeIterator<Item = Block> + '_

The blocks, in layout order (the order emission lays them out).

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
let a = f.block()?;
let b = f.block()?;
assert_eq!(f.blocks().collect::<Vec<_>>(), [a, b]);

pub fn block_count(&self) -> usize

The number of blocks.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).block_count(), 0);

pub fn add_param( &mut self, block: Block, param: Operand, ) -> Result<(), MirError>

Appends a parameter to block: a register (virtual before allocation, physical after) or a whole stack slot (Operand::slot). The entry block’s parameters are the function’s incoming arguments.

Errors

MirError::UnknownBlock for a block the function does not have, MirError::BadParam for any other operand shape (including a slot operand with an offset), MirError::UnknownVReg, MirError::UnknownPReg, or MirError::UnknownSlot for a register or slot the function or target does not have.

Examples

use backend_lang::mir::{Function, Operand};
use backend_lang::x86_64::{RDI, SYSV};

let mut f = Function::new("f", &SYSV);
let entry = f.block()?;
f.add_param(entry, RDI.into())?;
assert_eq!(f.params(entry), [Operand::from(RDI)]);
assert!(f.add_param(entry, Operand::Imm(1)).is_err());

pub fn params(&self, block: Block) -> &[Operand]

A block’s parameters (empty for a block the function does not have).

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
assert!(f.params(b).is_empty());

pub fn stack_slot(&mut self, kind: SlotKind) -> Result<StackSlot, MirError>

A new stack slot.

Errors

MirError::Limit past u32::MAX - 1 slots. Sizes and alignments are checked when the frame is laid out.

Examples

use backend_lang::mir::{Function, SlotKind};
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
let s = f.stack_slot(SlotKind::Local { size: 16, align: 16 })?;
assert_eq!(f.slot(s).map(SlotKind::size), Some(16));

pub fn spill_slot(&mut self, class: RegClass) -> Result<StackSlot, MirError>

A new stack slot sized and aligned to hold one value of class.

Errors

MirError::UnknownClass for a class the target does not have, MirError::Limit past u32::MAX - 1 slots.

Examples

use backend_lang::mir::{Function, SlotKind};
use backend_lang::x86_64::{SYSV, VEC};

let mut f = Function::new("f", &SYSV);
let s = f.spill_slot(VEC)?;
assert_eq!(f.slot(s), Some(SlotKind::Local { size: 16, align: 16 }));

pub fn slot(&self, slot: StackSlot) -> Option<SlotKind>

A slot’s kind, or None if the function does not have it.

Examples

use backend_lang::mir::{Function, StackSlot};
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).slot(StackSlot::new(0)), None);

pub fn slots(&self) -> &[SlotKind]

Every slot’s kind, indexed by StackSlot::index.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert!(Function::new("f", &SYSV).slots().is_empty());

pub fn symbol(&mut self, name: &str) -> Result<Symbol, MirError>

A new reference to the function named name.

Errors

MirError::Limit past u32::MAX - 1 symbols.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
let callee = f.symbol("g")?;
assert_eq!(f.symbol_name(callee), Some("g"));

pub fn symbol_name(&self, symbol: Symbol) -> Option<&str>

A symbol’s name, or None if the function does not have it.

Examples

use backend_lang::mir::{Function, Symbol};
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).symbol_name(Symbol::new(0)), None);

pub fn block_call( &mut self, block: Block, args: &[Operand], ) -> Result<BlockCall, MirError>

A branch target: block with args for its parameters, as an operand for a jump or branch. The arguments are registers, whole stack slots, or immediates.

Errors

MirError::UnknownBlock, MirError::BadArg for another operand shape, the Unknown* errors for registers or slots the function does not have, and MirError::Limit when the argument pool is full. Argument counts and classes are checked when the branch is pushed.

Examples

use backend_lang::mir::{Function, Operand};
use backend_lang::x86_64::{op, SYSV};

let mut f = Function::new("f", &SYSV);
let entry = f.block()?;
let target = f.block()?;
let call = f.block_call(target, &[])?;
f.push(entry, op::JMP, &[call.into()])?;

pub fn args(&self, call: BlockCall) -> &[Operand]

The arguments of a branch target (empty for one this function did not make).

Examples

use backend_lang::mir::{Function, Operand};
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let call = f.block_call(b, &[Operand::Imm(7)])?;
assert_eq!(f.args(call), [Operand::Imm(7)]);

pub fn push( &mut self, block: Block, opcode: Opcode, operands: &[Operand], ) -> Result<Inst, MirError>

Appends an instruction to block.

The operands are checked against the opcode’s description at once: their count, each one’s shape and class, immediate ranges, branch argument counts against the target block’s parameters (so a block’s parameters must be added before branches to it), and the target’s memory-operand limit.

Errors

A MirError naming the problem; nothing is appended then.

Examples

use backend_lang::mir::{Function, MirError, Operand};
use backend_lang::x86_64::{op, GPR, SYSV};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let (a, c) = (f.vreg(GPR)?, f.vreg(GPR)?);
f.push(b, op::MOV64RI, &[a.into(), Operand::Imm(40)])?;
f.push(b, op::ADD64, &[c.into(), a.into(), Operand::Imm(2)])?;
// add64 takes a 32-bit immediate at most.
let err = f.push(b, op::ADD64, &[c.into(), a.into(), Operand::Imm(1 << 40)]).unwrap_err();
assert!(matches!(err, MirError::ImmediateRange { .. }));

pub fn push_with( &mut self, block: Block, opcode: Opcode, operands: &[Operand], effects: Effects<'_>, ) -> Result<Inst, MirError>

Appends an instruction with extra implicit operands (see Effects).

Errors

As for Function::push, plus MirError::UnknownPReg for an implicit register the target does not have.

Examples

use backend_lang::mir::{Effects, Function, Operand};
use backend_lang::x86_64::{op, SYSV, RAX, RDI};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
f.push(b, op::MOV64RI, &[RAX.into(), Operand::Imm(60)])?;
f.push_with(b, op::SYSCALL, &[], Effects::new().uses(&[RDI]))?;
f.push(b, op::UD2, &[])?;
assert!(f.to_string().contains("syscall implicit(rdi)"));

pub fn insts(&self, block: Block) -> &[Inst]

The instructions of block, in order (empty for a block the function does not have).

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::{op, SYSV};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let r = f.push(b, op::RET, &[])?;
assert_eq!(f.insts(b), [r]);

pub fn inst_count(&self) -> usize

The number of instructions in the function.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).inst_count(), 0);

pub fn opcode(&self, inst: Inst) -> Option<Opcode>

An instruction’s opcode, or None for one the function does not have.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::{op, SYSV};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let r = f.push(b, op::RET, &[])?;
assert_eq!(f.opcode(r), Some(op::RET));

pub fn inst_block(&self, inst: Inst) -> Option<Block>

The block an instruction is in.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::{op, SYSV};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let r = f.push(b, op::RET, &[])?;
assert_eq!(f.inst_block(r), Some(b));

pub fn operands(&self, inst: Inst) -> &[Operand]

An instruction’s explicit operands (empty for one the function does not have).

Examples

use backend_lang::mir::{Function, Operand};
use backend_lang::x86_64::{op, SYSV, RAX};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let i = f.push(b, op::MOV64RI, &[RAX.into(), Operand::Imm(5)])?;
assert_eq!(f.operands(i), [Operand::from(RAX), Operand::Imm(5)]);

pub fn implicit(&self, inst: Inst) -> &[Implicit]

An instruction’s extra implicit operands, uses first (empty for one the function does not have). The opcode’s own implicit operands are in its InstDesc.

Examples

use backend_lang::mir::{Effects, Function};
use backend_lang::x86_64::{op, SYSV, RAX};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let r = f.push_with(b, op::RET, &[], Effects::new().uses(&[RAX]))?;
assert_eq!(f.implicit(r).len(), 1);

pub fn clobbers(&self, inst: Inst) -> RegSet

An instruction’s extra clobbers (empty for one the function does not have).

Examples

use backend_lang::mir::{Effects, Function};
use backend_lang::x86_64::{op, SYSV};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let callee = f.symbol("g")?;
let c = f.push_with(b, op::CALL, &[callee.into()], Effects::new().clobbers(SYSV.call_clobbers()))?;
assert_eq!(f.clobbers(c), SYSV.call_clobbers());

pub fn set_call_site( &mut self, inst: Inst, gc_slots: &[StackSlot], landing_pad: Option<Block>, ) -> Result<(), MirError>

Records what a call instruction carries besides its operands: the stack slots holding its GC roots (its stack map: a collector running during the call finds the references there and may update them), and the block control reaches if the callee unwinds. Setting it again replaces the record.

A landing pad is a successor of the call’s block for liveness: the values it uses are live across the call.

Errors

MirError::NotACall if inst is not a call, MirError::UnknownSlot or MirError::UnknownBlock for a slot or block the function does not have, MirError::Limit past 32-bit tables.

Examples

use backend_lang::mir::{Function, MirError, SlotKind};
use backend_lang::x86_64::{op, SYSV};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let root = f.stack_slot(SlotKind::Local { size: 8, align: 8 })?;
let g = f.symbol("g")?;
let call = f.push(b, op::CALL, &[g.into()])?;
let ret = f.push(b, op::RET, &[])?;
f.set_call_site(call, &[root], None)?;
assert_eq!(f.set_call_site(ret, &[], None), Err(MirError::NotACall { inst: ret }));

pub fn call_site(&self, inst: Inst) -> Option<CallSite<'_>>

The call-site record of inst, if it has one.

Examples

use backend_lang::mir::{Function, Inst};
use backend_lang::x86_64::SYSV;

assert!(Function::new("f", &SYSV).call_site(Inst::new(0)).is_none());

pub fn call_sites(&self) -> impl ExactSizeIterator<Item = CallSite<'_>> + '_

Every call-site record, by instruction.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).call_sites().count(), 0);

pub fn reserve_outgoing(&mut self, bytes: u32)

Reserves bytes of outgoing argument area at the bottom of the frame (the largest over all calls; see Abi::assign_args). Stack arguments are stored to [sp + offset] before a call. Calling it again keeps the larger value.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
f.reserve_outgoing(24);
f.reserve_outgoing(8);
assert_eq!(f.outgoing(), 24);

pub fn outgoing(&self) -> u32

The outgoing argument area reserved.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert_eq!(Function::new("f", &SYSV).outgoing(), 0);

pub fn omit_frame_pointer(&mut self)

Lays the frame out without a frame pointer, which frees the frame pointer register for the body (it is then saved like any other callee-saved register it writes). The frame pointer is kept by default.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

let mut f = Function::new("f", &SYSV);
f.omit_frame_pointer();
assert!(!f.frame_pointer());
assert!(f.frame_layout().unwrap().prologue().is_empty());

pub fn frame_pointer(&self) -> bool

Whether the frame keeps a frame pointer.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert!(Function::new("f", &SYSV).frame_pointer());

pub fn reserved(&self) -> RegSet

The registers reserved for the frame, which the body may read but not write: the stack pointer, and the frame pointer when it is kept.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::{SYSV, RBP, RSP};

let f = Function::new("f", &SYSV);
assert!(f.reserved().contains(RSP) && f.reserved().contains(RBP));

pub fn has_calls(&self) -> bool

Whether any instruction is a call.

Examples

use backend_lang::mir::Function;
use backend_lang::x86_64::SYSV;

assert!(!Function::new("f", &SYSV).has_calls());

pub fn written_regs(&self) -> RegSet

Every physical register the function’s instructions may write: explicit and implicit definitions, clobbers, and physical block parameters (written by the moves on the edges into them). The callee-saved registers among them are what the prologue saves.

Examples

use backend_lang::mir::{Function, Operand};
use backend_lang::x86_64::{op, SYSV, RBX, RDX, RAX, FLAGS};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
f.push(b, op::MOV64RI, &[RBX.into(), Operand::Imm(1)])?;
f.push(b, op::CQO, &[])?;
let w = f.written_regs();
assert!(w.contains(RBX) && w.contains(RDX));
assert!(!w.contains(RAX));

pub fn frame_layout(&self) -> Result<FrameLayout, FrameError>

Lays out the function’s frame under its calling convention.

Errors

FrameError for a slot alignment the frame cannot provide, overlapping incoming slots, or a frame beyond 32-bit offsets.

Examples

use backend_lang::mir::{Function, SlotKind};
use backend_lang::x86_64::WIN64;

let mut f = Function::new("f", &WIN64);
let s = f.stack_slot(SlotKind::Local { size: 8, align: 8 })?;
let frame = f.frame_layout().unwrap();
// Win64 has no red zone; after the rbp push the stack pointer is
// 16-aligned, so 8 bytes of locals round up to 16.
assert_eq!(frame.alloc(), 16);
assert_eq!(frame.slot_offset(s), Some(0));

impl Function

pub fn verify(&self) -> Result<(), MirError>

Checks the whole function: every instruction against its opcode (again, since block parameters may have been added after branches to them), every block ends with exactly one terminator, and every virtual register is defined at most once (MIR before register allocation is SSA; block parameters count as definitions).

Runs in time linear in the function’s size. Dominance (every use defined on every path to it) is the register allocator’s precondition and is checked with it (backend-lang 0.5).

Errors

The first MirError found, in block order.

Examples

use backend_lang::mir::{Function, MirError, Operand};
use backend_lang::x86_64::{op, GPR, SYSV};

let mut f = Function::new("f", &SYSV);
let b = f.block()?;
let v = f.vreg(GPR)?;
f.push(b, op::MOV64RI, &[v.into(), Operand::Imm(1)])?;
assert_eq!(f.verify(), Err(MirError::MissingTerminator { block: b }));
f.push(b, op::MOV64RI, &[v.into(), Operand::Imm(2)])?;
f.push(b, op::RET, &[])?;
assert_eq!(f.verify(), Err(MirError::MultipleDefs { vreg: v.as_virt().unwrap() }));

Trait Implementations

impl Clone for Function

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Function

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for Function

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.