diff options
Diffstat (limited to 'third_party/rust/cranelift-codegen/src/isa/constraints.rs')
| -rw-r--r-- | third_party/rust/cranelift-codegen/src/isa/constraints.rs | 207 |
1 files changed, 207 insertions, 0 deletions
diff --git a/third_party/rust/cranelift-codegen/src/isa/constraints.rs b/third_party/rust/cranelift-codegen/src/isa/constraints.rs new file mode 100644 index 0000000000..c87c3bd9d4 --- /dev/null +++ b/third_party/rust/cranelift-codegen/src/isa/constraints.rs @@ -0,0 +1,207 @@ +//! Register constraints for instruction operands. +//! +//! An encoding recipe specifies how an instruction is encoded as binary machine code, but it only +//! works if the operands and results satisfy certain constraints. Constraints on immediate +//! operands are checked by instruction predicates when the recipe is chosen. +//! +//! It is the register allocator's job to make sure that the register constraints on value operands +//! are satisfied. + +use crate::binemit::CodeOffset; +use crate::ir::{Function, Inst, ValueLoc}; +use crate::isa::{RegClass, RegUnit}; +use crate::regalloc::RegDiversions; + +/// Register constraint for a single value operand or instruction result. +#[derive(PartialEq, Debug)] +pub struct OperandConstraint { + /// The kind of constraint. + pub kind: ConstraintKind, + + /// The register class of the operand. + /// + /// This applies to all kinds of constraints, but with slightly different meaning. + pub regclass: RegClass, +} + +impl OperandConstraint { + /// Check if this operand constraint is satisfied by the given value location. + /// For tied constraints, this only checks the register class, not that the + /// counterpart operand has the same value location. + pub fn satisfied(&self, loc: ValueLoc) -> bool { + match self.kind { + ConstraintKind::Reg | ConstraintKind::Tied(_) => { + if let ValueLoc::Reg(reg) = loc { + self.regclass.contains(reg) + } else { + false + } + } + ConstraintKind::FixedReg(reg) | ConstraintKind::FixedTied(reg) => { + loc == ValueLoc::Reg(reg) && self.regclass.contains(reg) + } + ConstraintKind::Stack => { + if let ValueLoc::Stack(_) = loc { + true + } else { + false + } + } + } + } +} + +/// The different kinds of operand constraints. +#[derive(Clone, Copy, PartialEq, Eq, Debug)] +pub enum ConstraintKind { + /// This operand or result must be a register from the given register class. + Reg, + + /// This operand or result must be a fixed register. + /// + /// The constraint's `regclass` field is the top-level register class containing the fixed + /// register. + FixedReg(RegUnit), + + /// This result value must use the same register as an input value operand. + /// + /// The associated number is the index of the input value operand this result is tied to. The + /// constraint's `regclass` field is the same as the tied operand's register class. + /// + /// When an (in, out) operand pair is tied, this constraint kind appears in both the `ins` and + /// the `outs` arrays. The constraint for the in operand is `Tied(out)`, and the constraint for + /// the out operand is `Tied(in)`. + Tied(u8), + + /// This operand must be a fixed register, and it has a tied counterpart. + /// + /// This works just like `FixedReg`, but additionally indicates that there are identical + /// input/output operands for this fixed register. For an input operand, this means that the + /// value will be clobbered by the instruction + FixedTied(RegUnit), + + /// This operand must be a value in a stack slot. + /// + /// The constraint's `regclass` field is the register class that would normally be used to load + /// and store values of this type. + Stack, +} + +/// Value operand constraints for an encoding recipe. +#[derive(PartialEq, Clone)] +pub struct RecipeConstraints { + /// Constraints for the instruction's fixed value operands. + /// + /// If the instruction takes a variable number of operands, the register constraints for those + /// operands must be computed dynamically. + /// + /// - For branches and jumps, block arguments must match the expectations of the destination block. + /// - For calls and returns, the calling convention ABI specifies constraints. + pub ins: &'static [OperandConstraint], + + /// Constraints for the instruction's fixed results. + /// + /// If the instruction produces a variable number of results, it's probably a call and the + /// constraints must be derived from the calling convention ABI. + pub outs: &'static [OperandConstraint], + + /// Are any of the input constraints `FixedReg` or `FixedTied`? + pub fixed_ins: bool, + + /// Are any of the output constraints `FixedReg` or `FixedTied`? + pub fixed_outs: bool, + + /// Are any of the input/output constraints `Tied` (but not `FixedTied`)? + pub tied_ops: bool, + + /// Does this instruction clobber the CPU flags? + /// + /// When true, SSA values of type `iflags` or `fflags` can not be live across the instruction. + pub clobbers_flags: bool, +} + +impl RecipeConstraints { + /// Check that these constraints are satisfied by the operands on `inst`. + pub fn satisfied(&self, inst: Inst, divert: &RegDiversions, func: &Function) -> bool { + for (&arg, constraint) in func.dfg.inst_args(inst).iter().zip(self.ins) { + let loc = divert.get(arg, &func.locations); + + if let ConstraintKind::Tied(out_index) = constraint.kind { + let out_val = func.dfg.inst_results(inst)[out_index as usize]; + let out_loc = func.locations[out_val]; + if loc != out_loc { + return false; + } + } + + if !constraint.satisfied(loc) { + return false; + } + } + + for (&arg, constraint) in func.dfg.inst_results(inst).iter().zip(self.outs) { + let loc = divert.get(arg, &func.locations); + if !constraint.satisfied(loc) { + return false; + } + } + + true + } +} + +/// Constraints on the range of a branch instruction. +/// +/// A branch instruction usually encodes its destination as a signed n-bit offset from an origin. +/// The origin depends on the ISA and the specific instruction: +/// +/// - RISC-V and ARM Aarch64 use the address of the branch instruction, `origin = 0`. +/// - x86 uses the address of the instruction following the branch, `origin = 2` for a 2-byte +/// branch instruction. +/// - ARM's A32 encoding uses the address of the branch instruction + 8 bytes, `origin = 8`. +#[derive(Clone, Copy, Debug)] +pub struct BranchRange { + /// Offset in bytes from the address of the branch instruction to the origin used for computing + /// the branch displacement. This is the destination of a branch that encodes a 0 displacement. + pub origin: u8, + + /// Number of bits in the signed byte displacement encoded in the instruction. This does not + /// account for branches that can only target aligned addresses. + pub bits: u8, +} + +impl BranchRange { + /// Determine if this branch range can represent the range from `branch` to `dest`, where + /// `branch` is the code offset of the branch instruction itself and `dest` is the code offset + /// of the destination block header. + /// + /// This method does not detect if the range is larger than 2 GB. + pub fn contains(self, branch: CodeOffset, dest: CodeOffset) -> bool { + let d = dest.wrapping_sub(branch + CodeOffset::from(self.origin)) as i32; + let s = 32 - self.bits; + d == d << s >> s + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn branch_range() { + // ARM T1 branch. + let t1 = BranchRange { origin: 4, bits: 9 }; + assert!(t1.contains(0, 0)); + assert!(t1.contains(0, 2)); + assert!(t1.contains(2, 0)); + assert!(t1.contains(1000, 1000)); + + // Forward limit. + assert!(t1.contains(1000, 1258)); + assert!(!t1.contains(1000, 1260)); + + // Backward limit + assert!(t1.contains(1000, 748)); + assert!(!t1.contains(1000, 746)); + } +} |