1 //! This module exposes the machine-specific backend definition pieces. 2 //! 3 //! The MachInst infrastructure is the compiler backend, from CLIF 4 //! (ir::Function) to machine code. The purpose of this infrastructure is, at a 5 //! high level, to do instruction selection/lowering (to machine instructions), 6 //! register allocation, and then perform all the fixups to branches, constant 7 //! data references, etc., needed to actually generate machine code. 8 //! 9 //! The container for machine instructions, at various stages of construction, 10 //! is the `VCode` struct. We refer to a sequence of machine instructions organized 11 //! into basic blocks as "vcode". This is short for "virtual-register code", though 12 //! it's a bit of a misnomer because near the end of the pipeline, vcode has all 13 //! real registers. Nevertheless, the name is catchy and we like it. 14 //! 15 //! The compilation pipeline, from an `ir::Function` (already optimized as much as 16 //! you like by machine-independent optimization passes) onward, is as follows. 17 //! (N.B.: though we show the VCode separately at each stage, the passes 18 //! mutate the VCode in place; these are not separate copies of the code.) 19 //! 20 //! ```plain 21 //! 22 //! ir::Function (SSA IR, machine-independent opcodes) 23 //! | 24 //! | [lower] 25 //! | 26 //! VCode<arch_backend::Inst> (machine instructions: 27 //! | - mostly virtual registers. 28 //! | - cond branches in two-target form. 29 //! | - branch targets are block indices. 30 //! | - in-memory constants held by insns, 31 //! | with unknown offsets. 32 //! | - critical edges (actually all edges) 33 //! | are split.) 34 //! | [regalloc] 35 //! | 36 //! VCode<arch_backend::Inst> (machine instructions: 37 //! | - all real registers. 38 //! | - new instruction sequence returned 39 //! | out-of-band in RegAllocResult. 40 //! | - instruction sequence has spills, 41 //! | reloads, and moves inserted. 42 //! | - other invariants same as above.) 43 //! | 44 //! | [preamble/postamble] 45 //! | 46 //! VCode<arch_backend::Inst> (machine instructions: 47 //! | - stack-frame size known. 48 //! | - out-of-band instruction sequence 49 //! | has preamble prepended to entry 50 //! | block, and postamble injected before 51 //! | every return instruction. 52 //! | - all symbolic stack references to 53 //! | stackslots and spillslots are resolved 54 //! | to concrete FP-offset mem addresses.) 55 //! | 56 //! | [binary emission via MachBuffer 57 //! | with streaming branch resolution/simplification] 58 //! | 59 //! Vec<u8> (machine code!) 60 //! 61 //! ``` 62 63 use crate::binemit::{CodeInfo, CodeOffset, StackMap}; 64 use crate::ir::condcodes::IntCC; 65 use crate::ir::{Function, SourceLoc, StackSlot, Type, ValueLabel}; 66 use crate::result::CodegenResult; 67 use crate::settings::{self, Flags}; 68 use crate::value_label::ValueLabelsRanges; 69 use alloc::boxed::Box; 70 use alloc::vec::Vec; 71 use core::fmt::Debug; 72 use core::hash::Hasher; 73 use cranelift_entity::PrimaryMap; 74 use regalloc::RegUsageCollector; 75 use regalloc::{ 76 RealReg, RealRegUniverse, Reg, RegClass, RegUsageMapper, SpillSlot, VirtualReg, Writable, 77 }; 78 use smallvec::{smallvec, SmallVec}; 79 use std::string::String; 80 use target_lexicon::Triple; 81 82 #[cfg(feature = "unwind")] 83 use crate::isa::unwind::systemv::RegisterMappingError; 84 85 pub mod lower; 86 pub use lower::*; 87 pub mod vcode; 88 pub use vcode::*; 89 pub mod compile; 90 pub use compile::*; 91 pub mod blockorder; 92 pub use blockorder::*; 93 pub mod abi; 94 pub use abi::*; 95 pub mod abi_impl; 96 pub use abi_impl::*; 97 pub mod buffer; 98 pub use buffer::*; 99 pub mod adapter; 100 pub use adapter::*; 101 pub mod helpers; 102 pub use helpers::*; 103 pub mod inst_common; 104 pub use inst_common::*; 105 pub mod valueregs; 106 pub use valueregs::*; 107 pub mod debug; 108 109 /// A machine instruction. 110 pub trait MachInst: Clone + Debug { 111 /// Return the registers referenced by this machine instruction along with 112 /// the modes of reference (use, def, modify). get_regs(&self, collector: &mut RegUsageCollector)113 fn get_regs(&self, collector: &mut RegUsageCollector); 114 115 /// Map virtual registers to physical registers using the given virt->phys 116 /// maps corresponding to the program points prior to, and after, this instruction. map_regs<RUM: RegUsageMapper>(&mut self, maps: &RUM)117 fn map_regs<RUM: RegUsageMapper>(&mut self, maps: &RUM); 118 119 /// If this is a simple move, return the (source, destination) tuple of registers. is_move(&self) -> Option<(Writable<Reg>, Reg)>120 fn is_move(&self) -> Option<(Writable<Reg>, Reg)>; 121 122 /// Is this a terminator (branch or ret)? If so, return its type 123 /// (ret/uncond/cond) and target if applicable. is_term<'a>(&'a self) -> MachTerminator<'a>124 fn is_term<'a>(&'a self) -> MachTerminator<'a>; 125 126 /// Returns true if the instruction is an epilogue placeholder. is_epilogue_placeholder(&self) -> bool127 fn is_epilogue_placeholder(&self) -> bool; 128 129 /// Should this instruction be included in the clobber-set? is_included_in_clobbers(&self) -> bool130 fn is_included_in_clobbers(&self) -> bool { 131 true 132 } 133 134 /// If this is a load or store to the stack, return that info. stack_op_info(&self) -> Option<MachInstStackOpInfo>135 fn stack_op_info(&self) -> Option<MachInstStackOpInfo> { 136 None 137 } 138 139 /// Generate a move. gen_move(to_reg: Writable<Reg>, from_reg: Reg, ty: Type) -> Self140 fn gen_move(to_reg: Writable<Reg>, from_reg: Reg, ty: Type) -> Self; 141 142 /// Generate a constant into a reg. gen_constant<F: FnMut(Type) -> Writable<Reg>>( to_regs: ValueRegs<Writable<Reg>>, value: u128, ty: Type, alloc_tmp: F, ) -> SmallVec<[Self; 4]>143 fn gen_constant<F: FnMut(Type) -> Writable<Reg>>( 144 to_regs: ValueRegs<Writable<Reg>>, 145 value: u128, 146 ty: Type, 147 alloc_tmp: F, 148 ) -> SmallVec<[Self; 4]>; 149 150 /// Possibly operate on a value directly in a spill-slot rather than a 151 /// register. Useful if the machine has register-memory instruction forms 152 /// (e.g., add directly from or directly to memory), like x86. maybe_direct_reload(&self, reg: VirtualReg, slot: SpillSlot) -> Option<Self>153 fn maybe_direct_reload(&self, reg: VirtualReg, slot: SpillSlot) -> Option<Self>; 154 155 /// Determine register class(es) to store the given Cranelift type, and the 156 /// Cranelift type actually stored in the underlying register(s). May return 157 /// an error if the type isn't supported by this backend. 158 /// 159 /// If the type requires multiple registers, then the list of registers is 160 /// returned in little-endian order. 161 /// 162 /// Note that the type actually stored in the register(s) may differ in the 163 /// case that a value is split across registers: for example, on a 32-bit 164 /// target, an I64 may be stored in two registers, each of which holds an 165 /// I32. The actually-stored types are used only to inform the backend when 166 /// generating spills and reloads for individual registers. rc_for_type(ty: Type) -> CodegenResult<(&'static [RegClass], &'static [Type])>167 fn rc_for_type(ty: Type) -> CodegenResult<(&'static [RegClass], &'static [Type])>; 168 169 /// Generate a jump to another target. Used during lowering of 170 /// control flow. gen_jump(target: MachLabel) -> Self171 fn gen_jump(target: MachLabel) -> Self; 172 173 /// Generate a NOP. The `preferred_size` parameter allows the caller to 174 /// request a NOP of that size, or as close to it as possible. The machine 175 /// backend may return a NOP whose binary encoding is smaller than the 176 /// preferred size, but must not return a NOP that is larger. However, 177 /// the instruction must have a nonzero size if preferred_size is nonzero. gen_nop(preferred_size: usize) -> Self178 fn gen_nop(preferred_size: usize) -> Self; 179 180 /// Get the register universe for this backend. reg_universe(flags: &Flags) -> RealRegUniverse181 fn reg_universe(flags: &Flags) -> RealRegUniverse; 182 183 /// Align a basic block offset (from start of function). By default, no 184 /// alignment occurs. align_basic_block(offset: CodeOffset) -> CodeOffset185 fn align_basic_block(offset: CodeOffset) -> CodeOffset { 186 offset 187 } 188 189 /// What is the worst-case instruction size emitted by this instruction type? worst_case_size() -> CodeOffset190 fn worst_case_size() -> CodeOffset; 191 192 /// What is the register class used for reference types (GC-observable pointers)? Can 193 /// be dependent on compilation flags. ref_type_regclass(_flags: &Flags) -> RegClass194 fn ref_type_regclass(_flags: &Flags) -> RegClass; 195 196 /// Does this instruction define a ValueLabel? Returns the `Reg` whose value 197 /// becomes the new value of the `ValueLabel` after this instruction. defines_value_label(&self) -> Option<(ValueLabel, Reg)>198 fn defines_value_label(&self) -> Option<(ValueLabel, Reg)> { 199 None 200 } 201 202 /// Create a marker instruction that defines a value label. gen_value_label_marker(_label: ValueLabel, _reg: Reg) -> Self203 fn gen_value_label_marker(_label: ValueLabel, _reg: Reg) -> Self { 204 Self::gen_nop(0) 205 } 206 207 /// A label-use kind: a type that describes the types of label references that 208 /// can occur in an instruction. 209 type LabelUse: MachInstLabelUse; 210 } 211 212 /// A descriptor of a label reference (use) in an instruction set. 213 pub trait MachInstLabelUse: Clone + Copy + Debug + Eq { 214 /// Required alignment for any veneer. Usually the required instruction 215 /// alignment (e.g., 4 for a RISC with 32-bit instructions, or 1 for x86). 216 const ALIGN: CodeOffset; 217 218 /// What is the maximum PC-relative range (positive)? E.g., if `1024`, a 219 /// label-reference fixup at offset `x` is valid if the label resolves to `x 220 /// + 1024`. max_pos_range(self) -> CodeOffset221 fn max_pos_range(self) -> CodeOffset; 222 /// What is the maximum PC-relative range (negative)? This is the absolute 223 /// value; i.e., if `1024`, then a label-reference fixup at offset `x` is 224 /// valid if the label resolves to `x - 1024`. max_neg_range(self) -> CodeOffset225 fn max_neg_range(self) -> CodeOffset; 226 /// What is the size of code-buffer slice this label-use needs to patch in 227 /// the label's value? patch_size(self) -> CodeOffset228 fn patch_size(self) -> CodeOffset; 229 /// Perform a code-patch, given the offset into the buffer of this label use 230 /// and the offset into the buffer of the label's definition. 231 /// It is guaranteed that, given `delta = offset - label_offset`, we will 232 /// have `offset >= -self.max_neg_range()` and `offset <= 233 /// self.max_pos_range()`. patch(self, buffer: &mut [u8], use_offset: CodeOffset, label_offset: CodeOffset)234 fn patch(self, buffer: &mut [u8], use_offset: CodeOffset, label_offset: CodeOffset); 235 /// Can the label-use be patched to a veneer that supports a longer range? 236 /// Usually valid for jumps (a short-range jump can jump to a longer-range 237 /// jump), but not for e.g. constant pool references, because the constant 238 /// load would require different code (one more level of indirection). supports_veneer(self) -> bool239 fn supports_veneer(self) -> bool; 240 /// How many bytes are needed for a veneer? veneer_size(self) -> CodeOffset241 fn veneer_size(self) -> CodeOffset; 242 /// Generate a veneer. The given code-buffer slice is `self.veneer_size()` 243 /// bytes long at offset `veneer_offset` in the buffer. The original 244 /// label-use will be patched to refer to this veneer's offset. A new 245 /// (offset, LabelUse) is returned that allows the veneer to use the actual 246 /// label. For veneers to work properly, it is expected that the new veneer 247 /// has a larger range; on most platforms this probably means either a 248 /// "long-range jump" (e.g., on ARM, the 26-bit form), or if already at that 249 /// stage, a jump that supports a full 32-bit range, for example. generate_veneer(self, buffer: &mut [u8], veneer_offset: CodeOffset) -> (CodeOffset, Self)250 fn generate_veneer(self, buffer: &mut [u8], veneer_offset: CodeOffset) -> (CodeOffset, Self); 251 } 252 253 /// Describes a block terminator (not call) in the vcode, when its branches 254 /// have not yet been finalized (so a branch may have two targets). 255 #[derive(Clone, Debug, PartialEq, Eq)] 256 pub enum MachTerminator<'a> { 257 /// Not a terminator. 258 None, 259 /// A return instruction. 260 Ret, 261 /// An unconditional branch to another block. 262 Uncond(MachLabel), 263 /// A conditional branch to one of two other blocks. 264 Cond(MachLabel, MachLabel), 265 /// An indirect branch with known possible targets. 266 Indirect(&'a [MachLabel]), 267 } 268 269 impl<'a> MachTerminator<'a> { 270 /// Get the successor labels named in a `MachTerminator`. get_succs(&self) -> SmallVec<[MachLabel; 2]>271 pub fn get_succs(&self) -> SmallVec<[MachLabel; 2]> { 272 let mut ret = smallvec![]; 273 match self { 274 &MachTerminator::Uncond(l) => { 275 ret.push(l); 276 } 277 &MachTerminator::Cond(l1, l2) => { 278 ret.push(l1); 279 ret.push(l2); 280 } 281 &MachTerminator::Indirect(ls) => { 282 ret.extend(ls.iter().cloned()); 283 } 284 _ => {} 285 } 286 ret 287 } 288 289 /// Is this a terminator? is_term(&self) -> bool290 pub fn is_term(&self) -> bool { 291 match self { 292 MachTerminator::None => false, 293 _ => true, 294 } 295 } 296 } 297 298 /// A trait describing the ability to encode a MachInst into binary machine code. 299 pub trait MachInstEmit: MachInst { 300 /// Persistent state carried across `emit` invocations. 301 type State: MachInstEmitState<Self>; 302 /// Constant information used in `emit` invocations. 303 type Info: MachInstEmitInfo; 304 /// Emit the instruction. emit(&self, code: &mut MachBuffer<Self>, info: &Self::Info, state: &mut Self::State)305 fn emit(&self, code: &mut MachBuffer<Self>, info: &Self::Info, state: &mut Self::State); 306 /// Pretty-print the instruction. pretty_print(&self, mb_rru: Option<&RealRegUniverse>, state: &mut Self::State) -> String307 fn pretty_print(&self, mb_rru: Option<&RealRegUniverse>, state: &mut Self::State) -> String; 308 } 309 310 /// Constant information used to emit an instruction. 311 pub trait MachInstEmitInfo { 312 /// Return the target-independent settings used for the compilation of this 313 /// particular function. flags(&self) -> &Flags314 fn flags(&self) -> &Flags; 315 } 316 317 /// A trait describing the emission state carried between MachInsts when 318 /// emitting a function body. 319 pub trait MachInstEmitState<I: MachInst>: Default + Clone + Debug { 320 /// Create a new emission state given the ABI object. new(abi: &dyn ABICallee<I = I>) -> Self321 fn new(abi: &dyn ABICallee<I = I>) -> Self; 322 /// Update the emission state before emitting an instruction that is a 323 /// safepoint. pre_safepoint(&mut self, _stack_map: StackMap)324 fn pre_safepoint(&mut self, _stack_map: StackMap) {} 325 /// Update the emission state to indicate instructions are associated with a 326 /// particular SourceLoc. pre_sourceloc(&mut self, _srcloc: SourceLoc)327 fn pre_sourceloc(&mut self, _srcloc: SourceLoc) {} 328 } 329 330 /// The result of a `MachBackend::compile_function()` call. Contains machine 331 /// code (as bytes) and a disassembly, if requested. 332 pub struct MachCompileResult { 333 /// Machine code. 334 pub buffer: MachBufferFinalized, 335 /// Size of stack frame, in bytes. 336 pub frame_size: u32, 337 /// Disassembly, if requested. 338 pub disasm: Option<String>, 339 /// Debug info: value labels to registers/stackslots at code offsets. 340 pub value_labels_ranges: ValueLabelsRanges, 341 /// Debug info: stackslots to stack pointer offsets. 342 pub stackslot_offsets: PrimaryMap<StackSlot, u32>, 343 } 344 345 impl MachCompileResult { 346 /// Get a `CodeInfo` describing section sizes from this compilation result. code_info(&self) -> CodeInfo347 pub fn code_info(&self) -> CodeInfo { 348 let code_size = self.buffer.total_size(); 349 CodeInfo { 350 code_size, 351 jumptables_size: 0, 352 rodata_size: 0, 353 total_size: code_size, 354 } 355 } 356 } 357 358 /// Top-level machine backend trait, which wraps all monomorphized code and 359 /// allows a virtual call from the machine-independent `Function::compile()`. 360 pub trait MachBackend { 361 /// Compile the given function. compile_function( &self, func: &Function, want_disasm: bool, ) -> CodegenResult<MachCompileResult>362 fn compile_function( 363 &self, 364 func: &Function, 365 want_disasm: bool, 366 ) -> CodegenResult<MachCompileResult>; 367 368 /// Return flags for this backend. flags(&self) -> &Flags369 fn flags(&self) -> &Flags; 370 371 /// Get the ISA-dependent flag values that were used to make this trait object. isa_flags(&self) -> Vec<settings::Value>372 fn isa_flags(&self) -> Vec<settings::Value>; 373 374 /// Hashes all flags, both ISA-independent and ISA-dependent, into the specified hasher. hash_all_flags(&self, hasher: &mut dyn Hasher)375 fn hash_all_flags(&self, hasher: &mut dyn Hasher); 376 377 /// Return triple for this backend. triple(&self) -> Triple378 fn triple(&self) -> Triple; 379 380 /// Return name for this backend. name(&self) -> &'static str381 fn name(&self) -> &'static str; 382 383 /// Return the register universe for this backend. reg_universe(&self) -> &RealRegUniverse384 fn reg_universe(&self) -> &RealRegUniverse; 385 386 /// Machine-specific condcode info needed by TargetIsa. 387 /// Condition that will be true when an IaddIfcout overflows. unsigned_add_overflow_condition(&self) -> IntCC388 fn unsigned_add_overflow_condition(&self) -> IntCC; 389 390 /// Machine-specific condcode info needed by TargetIsa. 391 /// Condition that will be true when an IsubIfcout overflows. unsigned_sub_overflow_condition(&self) -> IntCC392 fn unsigned_sub_overflow_condition(&self) -> IntCC; 393 394 /// Produces unwind info based on backend results. 395 #[cfg(feature = "unwind")] emit_unwind_info( &self, _result: &MachCompileResult, _kind: UnwindInfoKind, ) -> CodegenResult<Option<crate::isa::unwind::UnwindInfo>>396 fn emit_unwind_info( 397 &self, 398 _result: &MachCompileResult, 399 _kind: UnwindInfoKind, 400 ) -> CodegenResult<Option<crate::isa::unwind::UnwindInfo>> { 401 // By default, an backend cannot produce unwind info. 402 Ok(None) 403 } 404 405 /// Creates a new System V Common Information Entry for the ISA. 406 #[cfg(feature = "unwind")] create_systemv_cie(&self) -> Option<gimli::write::CommonInformationEntry>407 fn create_systemv_cie(&self) -> Option<gimli::write::CommonInformationEntry> { 408 // By default, an ISA cannot create a System V CIE 409 None 410 } 411 /// Maps a regalloc::Reg to a DWARF register number. 412 #[cfg(feature = "unwind")] map_reg_to_dwarf(&self, _: Reg) -> Result<u16, RegisterMappingError>413 fn map_reg_to_dwarf(&self, _: Reg) -> Result<u16, RegisterMappingError> { 414 Err(RegisterMappingError::UnsupportedArchitecture) 415 } 416 } 417 418 /// Expected unwind info type. 419 #[derive(Debug, Clone, Copy, PartialEq, Eq)] 420 #[non_exhaustive] 421 pub enum UnwindInfoKind { 422 /// No unwind info. 423 None, 424 /// SystemV CIE/FDE unwind info. 425 #[cfg(feature = "unwind")] 426 SystemV, 427 /// Windows X64 Unwind info 428 #[cfg(feature = "unwind")] 429 Windows, 430 } 431 432 /// Info about an operation that loads or stores from/to the stack. 433 #[derive(Clone, Copy, Debug)] 434 pub enum MachInstStackOpInfo { 435 /// Load from an offset from the nominal stack pointer into the given reg. 436 LoadNomSPOff(Reg, i64), 437 /// Store to an offset from the nominal stack pointer from the given reg. 438 StoreNomSPOff(Reg, i64), 439 /// Adjustment of nominal-SP up or down. This value is added to subsequent 440 /// offsets in loads/stores above to produce real-SP offsets. 441 NomSPAdj(i64), 442 } 443