1 //! This module implements lowering (instruction selection) from Cranelift IR 2 //! to machine instructions with virtual registers. This is *almost* the final 3 //! machine code, except for register allocation. 4 5 // TODO: separate the IR-query core of `LowerCtx` from the lowering logic built 6 // on top of it, e.g. the side-effect/coloring analysis and the scan support. 7 8 use crate::data_value::DataValue; 9 use crate::entity::SecondaryMap; 10 use crate::fx::{FxHashMap, FxHashSet}; 11 use crate::inst_predicates::{has_lowering_side_effect, is_constant_64bit}; 12 use crate::ir::{ 13 types::{FFLAGS, IFLAGS}, 14 ArgumentPurpose, Block, Constant, ConstantData, DataFlowGraph, ExternalName, Function, 15 GlobalValue, GlobalValueData, Immediate, Inst, InstructionData, MemFlags, Opcode, Signature, 16 SourceLoc, Type, Value, ValueDef, ValueLabelAssignments, ValueLabelStart, 17 }; 18 use crate::machinst::{ 19 non_writable_value_regs, writable_value_regs, ABICallee, BlockIndex, BlockLoweringOrder, 20 LoweredBlock, MachLabel, Reg, VCode, VCodeBuilder, VCodeConstant, VCodeConstantData, 21 VCodeConstants, VCodeInst, ValueRegs, Writable, 22 }; 23 use crate::{trace, CodegenResult}; 24 use alloc::boxed::Box; 25 use alloc::vec::Vec; 26 use core::convert::TryInto; 27 use regalloc2::VReg; 28 use smallvec::{smallvec, SmallVec}; 29 use std::fmt::Debug; 30 31 use super::{first_user_vreg_index, VCodeBuildDirection}; 32 33 /// An "instruction color" partitions CLIF instructions by side-effecting ops. 34 /// All instructions with the same "color" are guaranteed not to be separated by 35 /// any side-effecting op (for this purpose, loads are also considered 36 /// side-effecting, to avoid subtle questions w.r.t. the memory model), and 37 /// furthermore, it is guaranteed that for any two instructions A and B such 38 /// that color(A) == color(B), either A dominates B and B postdominates A, or 39 /// vice-versa. (For now, in practice, only ops in the same basic block can ever 40 /// have the same color, trivially providing the second condition.) Intuitively, 41 /// this means that the ops of the same color must always execute "together", as 42 /// part of one atomic contiguous section of the dynamic execution trace, and 43 /// they can be freely permuted (modulo true dataflow dependencies) without 44 /// affecting program behavior. 45 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] 46 struct InstColor(u32); 47 impl InstColor { 48 fn new(n: u32) -> InstColor { 49 InstColor(n) 50 } 51 52 /// Get an arbitrary index representing this color. The index is unique 53 /// *within a single function compilation*, but indices may be reused across 54 /// functions. 55 pub fn get(self) -> u32 { 56 self.0 57 } 58 } 59 60 /// A context that machine-specific lowering code can use to emit lowered 61 /// instructions. This is the view of the machine-independent per-function 62 /// lowering context that is seen by the machine backend. 63 pub trait LowerCtx { 64 /// The instruction type for which this lowering framework is instantiated. 65 type I: VCodeInst; 66 67 fn dfg(&self) -> &DataFlowGraph; 68 69 // Function-level queries: 70 71 /// Get the `ABICallee`. 72 fn abi(&mut self) -> &mut dyn ABICallee<I = Self::I>; 73 /// Get the (virtual) register that receives the return value. A return 74 /// instruction should lower into a sequence that fills this register. (Why 75 /// not allow the backend to specify its own result register for the return? 76 /// Because there may be multiple return points.) 77 fn retval(&self, idx: usize) -> ValueRegs<Writable<Reg>>; 78 /// Returns the vreg containing the VmContext parameter, if there's one. 79 fn get_vm_context(&self) -> Option<Reg>; 80 81 // General instruction queries: 82 83 /// Get the instdata for a given IR instruction. 84 fn data(&self, ir_inst: Inst) -> &InstructionData; 85 /// Get the controlling type for a polymorphic IR instruction. 86 fn ty(&self, ir_inst: Inst) -> Type; 87 /// Get the target for a call instruction, as an `ExternalName`. Returns a tuple 88 /// providing this name and the "relocation distance", i.e., whether the backend 89 /// can assume the target will be "nearby" (within some small offset) or an 90 /// arbitrary address. (This comes from the `colocated` bit in the CLIF.) 91 fn call_target<'b>(&'b self, ir_inst: Inst) -> Option<(&'b ExternalName, RelocDistance)>; 92 /// Get the signature for a call or call-indirect instruction. 93 fn call_sig<'b>(&'b self, ir_inst: Inst) -> Option<&'b Signature>; 94 /// Get the symbol name, relocation distance estimate, and offset for a 95 /// symbol_value instruction. 96 fn symbol_value<'b>(&'b self, ir_inst: Inst) -> Option<(&'b ExternalName, RelocDistance, i64)>; 97 /// Likewise, but starting with a GlobalValue identifier. 98 fn symbol_value_data<'b>( 99 &'b self, 100 global_value: GlobalValue, 101 ) -> Option<(&'b ExternalName, RelocDistance, i64)>; 102 /// Returns the memory flags of a given memory access. 103 fn memflags(&self, ir_inst: Inst) -> Option<MemFlags>; 104 /// Get the source location for a given instruction. 105 fn srcloc(&self, ir_inst: Inst) -> SourceLoc; 106 107 // Instruction input/output queries: 108 109 /// Get the number of inputs to the given IR instruction. 110 fn num_inputs(&self, ir_inst: Inst) -> usize; 111 /// Get the number of outputs to the given IR instruction. 112 fn num_outputs(&self, ir_inst: Inst) -> usize; 113 /// Get the type for an instruction's input. 114 fn input_ty(&self, ir_inst: Inst, idx: usize) -> Type; 115 /// Get the type for a value. 116 fn value_ty(&self, val: Value) -> Type; 117 /// Get the type for an instruction's output. 118 fn output_ty(&self, ir_inst: Inst, idx: usize) -> Type; 119 /// Get the value of a constant instruction (`iconst`, etc.) as a 64-bit 120 /// value, if possible. 121 fn get_constant(&self, ir_inst: Inst) -> Option<u64>; 122 /// Get the input as one of two options other than a direct register: 123 /// 124 /// - An instruction, given that it is effect-free or able to sink its 125 /// effect to the current instruction being lowered, and given it has only 126 /// one output, and if effect-ful, given that this is the only use; 127 /// - A constant, if the value is a constant. 128 /// 129 /// The instruction input may be available in either of these forms. It may 130 /// be available in neither form, if the conditions are not met; if so, use 131 /// `put_input_in_regs()` instead to get it in a register. 132 /// 133 /// If the backend merges the effect of a side-effecting instruction, it 134 /// must call `sink_inst()`. When this is called, it indicates that the 135 /// effect has been sunk to the current scan location. The sunk 136 /// instruction's result(s) must have *no* uses remaining, because it will 137 /// not be codegen'd (it has been integrated into the current instruction). 138 fn get_input_as_source_or_const(&self, ir_inst: Inst, idx: usize) -> NonRegInput; 139 /// Like `get_input_as_source_or_const` but with a `Value`. 140 fn get_value_as_source_or_const(&self, value: Value) -> NonRegInput; 141 /// Resolves a particular input of an instruction to the `Value` that it is 142 /// represented with. 143 fn input_as_value(&self, ir_inst: Inst, idx: usize) -> Value; 144 /// Increment the reference count for the Value, ensuring that it gets lowered. 145 fn increment_lowered_uses(&mut self, val: Value); 146 /// Put the `idx`th input into register(s) and return the assigned register. 147 fn put_input_in_regs(&mut self, ir_inst: Inst, idx: usize) -> ValueRegs<Reg>; 148 /// Put the given value into register(s) and return the assigned register. 149 fn put_value_in_regs(&mut self, value: Value) -> ValueRegs<Reg>; 150 /// Get the `idx`th output register(s) of the given IR instruction. When 151 /// `backend.lower_inst_to_regs(ctx, inst)` is called, it is expected that 152 /// the backend will write results to these output register(s). This 153 /// register will always be "fresh"; it is guaranteed not to overlap with 154 /// any of the inputs, and can be freely used as a scratch register within 155 /// the lowered instruction sequence, as long as its final value is the 156 /// result of the computation. 157 fn get_output(&self, ir_inst: Inst, idx: usize) -> ValueRegs<Writable<Reg>>; 158 159 // Codegen primitives: allocate temps, emit instructions, set result registers, 160 // ask for an input to be gen'd into a register. 161 162 /// Get a new temp. 163 fn alloc_tmp(&mut self, ty: Type) -> ValueRegs<Writable<Reg>>; 164 /// Emit a machine instruction. 165 fn emit(&mut self, mach_inst: Self::I); 166 /// Indicate that the side-effect of an instruction has been sunk to the 167 /// current scan location. This should only be done with the instruction's 168 /// original results are not used (i.e., `put_input_in_regs` is not invoked 169 /// for the input produced by the sunk instruction), otherwise the 170 /// side-effect will occur twice. 171 fn sink_inst(&mut self, ir_inst: Inst); 172 /// Retrieve immediate data given a handle. 173 fn get_immediate_data(&self, imm: Immediate) -> &ConstantData; 174 /// Retrieve constant data given a handle. 175 fn get_constant_data(&self, constant_handle: Constant) -> &ConstantData; 176 /// Indicate that a constant should be emitted. 177 fn use_constant(&mut self, constant: VCodeConstantData) -> VCodeConstant; 178 /// Retrieve the value immediate from an instruction. This will perform necessary lookups on the 179 /// `DataFlowGraph` to retrieve even large immediates. 180 fn get_immediate(&self, ir_inst: Inst) -> Option<DataValue>; 181 /// Cause the value in `reg` to be in a virtual reg, by copying it into a new virtual reg 182 /// if `reg` is a real reg. `ty` describes the type of the value in `reg`. 183 fn ensure_in_vreg(&mut self, reg: Reg, ty: Type) -> Reg; 184 185 /// Note that one vreg is to be treated as an alias of another. 186 fn set_vreg_alias(&mut self, from: Reg, to: Reg); 187 } 188 189 /// A representation of all of the ways in which a value is available, aside 190 /// from as a direct register. 191 /// 192 /// - An instruction, if it would be allowed to occur at the current location 193 /// instead (see [LowerCtx::get_input_as_source_or_const()] for more 194 /// details). 195 /// 196 /// - A constant, if the value is known to be a constant. 197 #[derive(Clone, Copy, Debug)] 198 pub struct NonRegInput { 199 /// An instruction produces this value (as the given output), and its 200 /// computation (and side-effect if applicable) could occur at the 201 /// current instruction's location instead. 202 /// 203 /// If this instruction's operation is merged into the current 204 /// instruction, the backend must call [LowerCtx::sink_inst()]. 205 /// 206 /// This enum indicates whether this use of the source instruction 207 /// is unique or not. 208 pub inst: InputSourceInst, 209 /// The value is a known constant. 210 pub constant: Option<u64>, 211 } 212 213 /// When examining an input to an instruction, this enum provides one 214 /// of several options: there is or isn't a single instruction (that 215 /// we can see and merge with) that produces that input's value, and 216 /// we are or aren't the single user of that instruction. 217 #[derive(Clone, Copy, Debug)] 218 pub enum InputSourceInst { 219 /// The input in question is the single, unique use of the given 220 /// instruction and output index, and it can be sunk to the 221 /// location of this input. 222 UniqueUse(Inst, usize), 223 /// The input in question is one of multiple uses of the given 224 /// instruction. It can still be sunk to the location of this 225 /// input. 226 Use(Inst, usize), 227 /// We cannot determine which instruction produced the input, or 228 /// it is one of several instructions (e.g., due to a control-flow 229 /// merge and blockparam), or the source instruction cannot be 230 /// allowed to sink to the current location due to side-effects. 231 None, 232 } 233 234 impl InputSourceInst { 235 /// Get the instruction and output index for this source, whether 236 /// we are its single or one of many users. 237 pub fn as_inst(&self) -> Option<(Inst, usize)> { 238 match self { 239 &InputSourceInst::UniqueUse(inst, output_idx) 240 | &InputSourceInst::Use(inst, output_idx) => Some((inst, output_idx)), 241 &InputSourceInst::None => None, 242 } 243 } 244 } 245 246 /// A machine backend. 247 pub trait LowerBackend { 248 /// The machine instruction type. 249 type MInst: VCodeInst; 250 251 /// Lower a single instruction. 252 /// 253 /// For a branch, this function should not generate the actual branch 254 /// instruction. However, it must force any values it needs for the branch 255 /// edge (block-param actuals) into registers, because the actual branch 256 /// generation (`lower_branch_group()`) happens *after* any possible merged 257 /// out-edge. 258 fn lower<C: LowerCtx<I = Self::MInst>>(&self, ctx: &mut C, inst: Inst) -> CodegenResult<()>; 259 260 /// Lower a block-terminating group of branches (which together can be seen 261 /// as one N-way branch), given a vcode MachLabel for each target. 262 fn lower_branch_group<C: LowerCtx<I = Self::MInst>>( 263 &self, 264 ctx: &mut C, 265 insts: &[Inst], 266 targets: &[MachLabel], 267 ) -> CodegenResult<()>; 268 269 /// A bit of a hack: give a fixed register that always holds the result of a 270 /// `get_pinned_reg` instruction, if known. This allows elision of moves 271 /// into the associated vreg, instead using the real reg directly. 272 fn maybe_pinned_reg(&self) -> Option<Reg> { 273 None 274 } 275 } 276 277 /// Machine-independent lowering driver / machine-instruction container. Maintains a correspondence 278 /// from original Inst to MachInsts. 279 pub struct Lower<'func, I: VCodeInst> { 280 /// The function to lower. 281 f: &'func Function, 282 283 /// Lowered machine instructions. 284 vcode: VCodeBuilder<I>, 285 286 /// Mapping from `Value` (SSA value in IR) to virtual register. 287 value_regs: SecondaryMap<Value, ValueRegs<Reg>>, 288 289 /// Return-value vregs. 290 retval_regs: Vec<ValueRegs<Reg>>, 291 292 /// Instruction colors at block exits. From this map, we can recover all 293 /// instruction colors by scanning backward from the block end and 294 /// decrementing on any color-changing (side-effecting) instruction. 295 block_end_colors: SecondaryMap<Block, InstColor>, 296 297 /// Instruction colors at side-effecting ops. This is the *entry* color, 298 /// i.e., the version of global state that exists before an instruction 299 /// executes. For each side-effecting instruction, the *exit* color is its 300 /// entry color plus one. 301 side_effect_inst_entry_colors: FxHashMap<Inst, InstColor>, 302 303 /// Current color as we scan during lowering. While we are lowering an 304 /// instruction, this is equal to the color *at entry to* the instruction. 305 cur_scan_entry_color: Option<InstColor>, 306 307 /// Current instruction as we scan during lowering. 308 cur_inst: Option<Inst>, 309 310 /// Instruction constant values, if known. 311 inst_constants: FxHashMap<Inst, u64>, 312 313 /// Use-counts per SSA value, as counted in the input IR. These 314 /// are "coarsened", in the abstract-interpretation sense: we only 315 /// care about "0, 1, many" states, as this is all we need and 316 /// this lets us do an efficient fixpoint analysis. 317 /// 318 /// See doc comment on `ValueUseState` for more details. 319 value_ir_uses: SecondaryMap<Value, ValueUseState>, 320 321 /// Actual uses of each SSA value so far, incremented while lowering. 322 value_lowered_uses: SecondaryMap<Value, u32>, 323 324 /// Effectful instructions that have been sunk; they are not codegen'd at 325 /// their original locations. 326 inst_sunk: FxHashSet<Inst>, 327 328 /// Next virtual register number to allocate. 329 next_vreg: usize, 330 331 /// Instructions collected for the CLIF inst in progress, in forward order. 332 ir_insts: Vec<I>, 333 334 /// The register to use for GetPinnedReg, if any, on this architecture. 335 pinned_reg: Option<Reg>, 336 337 /// The vreg containing the special VmContext parameter, if it is present in the current 338 /// function's signature. 339 vm_context: Option<Reg>, 340 } 341 342 /// How is a value used in the IR? 343 /// 344 /// This can be seen as a coarsening of an integer count. We only need 345 /// distinct states for zero, one, or many. 346 /// 347 /// This analysis deserves further explanation. The basic idea is that 348 /// we want to allow instruction lowering to know whether a value that 349 /// an instruction references is *only* referenced by that one use, or 350 /// by others as well. This is necessary to know when we might want to 351 /// move a side-effect: we cannot, for example, duplicate a load, so 352 /// we cannot let instruction lowering match a load as part of a 353 /// subpattern and potentially incorporate it. 354 /// 355 /// Note that a lot of subtlety comes into play once we have 356 /// *indirect* uses. The classical example of this in our development 357 /// history was the x86 compare instruction, which is incorporated 358 /// into flags users (e.g. `selectif`, `trueif`, branches) and can 359 /// subsequently incorporate loads, or at least we would like it 360 /// to. However, danger awaits: the compare might be the only user of 361 /// a load, so we might think we can just move the load (and nothing 362 /// is duplicated -- success!), except that the compare itself is 363 /// codegen'd in multiple places, where it is incorporated as a 364 /// subpattern itself. 365 /// 366 /// So we really want a notion of "unique all the way along the 367 /// matching path". Rust's `&T` and `&mut T` offer a partial analogy 368 /// to the semantics that we want here: we want to know when we've 369 /// matched a unique use of an instruction, and that instruction's 370 /// unique use of another instruction, etc, just as `&mut T` can only 371 /// be obtained by going through a chain of `&mut T`. If one has a 372 /// `&T` to a struct containing `&mut T` (one of several uses of an 373 /// instruction that itself has a unique use of an instruction), one 374 /// can only get a `&T` (one can only get a "I am one of several users 375 /// of this instruction" result). 376 /// 377 /// We could track these paths, either dynamically as one "looks up 378 /// the operand tree" or precomputed. But the former requires state 379 /// and means that the `LowerCtx` API carries that state implicitly, 380 /// which we'd like to avoid if we can. And the latter implies O(n^2) 381 /// storage: it is an all-pairs property (is inst `i` unique from the 382 /// point of view of `j`). 383 /// 384 /// To make matters even a little more complex still, a value that is 385 /// not uniquely used when initially viewing the IR can *become* 386 /// uniquely used, at least as a root allowing further unique uses of 387 /// e.g. loads to merge, if no other instruction actually merges 388 /// it. To be more concrete, if we have `v1 := load; v2 := op v1; v3 389 /// := op v2; v4 := op v2` then `v2` is non-uniquely used, so from the 390 /// point of view of lowering `v4` or `v3`, we cannot merge the load 391 /// at `v1`. But if we decide just to use the assigned register for 392 /// `v2` at both `v3` and `v4`, then we only actually codegen `v2` 393 /// once, so it *is* a unique root at that point and we *can* merge 394 /// the load. 395 /// 396 /// Note also that the color scheme is not sufficient to give us this 397 /// information, for various reasons: reasoning about side-effects 398 /// does not tell us about potential duplication of uses through pure 399 /// ops. 400 /// 401 /// To keep things simple and avoid error-prone lowering APIs that 402 /// would extract more information about whether instruction merging 403 /// happens or not (we don't have that info now, and it would be 404 /// difficult to refactor to get it and make that refactor 100% 405 /// correct), we give up on the above "can become unique if not 406 /// actually merged" point. Instead, we compute a 407 /// transitive-uniqueness. That is what this enum represents. 408 /// 409 /// To define it plainly: a value is `Unused` if no references exist 410 /// to it; `Once` if only one other op refers to it, *and* that other 411 /// op is `Unused` or `Once`; and `Multiple` otherwise. In other 412 /// words, `Multiple` is contagious: even if an op's result value is 413 /// directly used only once in the CLIF, that value is `Multiple` if 414 /// the op that uses it is itself used multiple times (hence could be 415 /// codegen'd multiple times). In brief, this analysis tells us 416 /// whether, if every op merged all of its operand tree, a given op 417 /// could be codegen'd in more than one place. 418 /// 419 /// To compute this, we first consider direct uses. At this point 420 /// `Unused` answers are correct, `Multiple` answers are correct, but 421 /// some `Once`s may change to `Multiple`s. Then we propagate 422 /// `Multiple` transitively using a workqueue/fixpoint algorithm. 423 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 424 enum ValueUseState { 425 /// Not used at all. 426 Unused, 427 /// Used exactly once. 428 Once, 429 /// Used multiple times. 430 Multiple, 431 } 432 433 impl ValueUseState { 434 /// Add one use. 435 fn inc(&mut self) { 436 let new = match self { 437 Self::Unused => Self::Once, 438 Self::Once | Self::Multiple => Self::Multiple, 439 }; 440 *self = new; 441 } 442 } 443 444 /// Notion of "relocation distance". This gives an estimate of how far away a symbol will be from a 445 /// reference. 446 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 447 pub enum RelocDistance { 448 /// Target of relocation is "nearby". The threshold for this is fuzzy but should be interpreted 449 /// as approximately "within the compiled output of one module"; e.g., within AArch64's +/- 450 /// 128MB offset. If unsure, use `Far` instead. 451 Near, 452 /// Target of relocation could be anywhere in the address space. 453 Far, 454 } 455 456 fn alloc_vregs<I: VCodeInst>( 457 ty: Type, 458 next_vreg: &mut usize, 459 vcode: &mut VCodeBuilder<I>, 460 ) -> CodegenResult<ValueRegs<Reg>> { 461 let v = *next_vreg; 462 let (regclasses, tys) = I::rc_for_type(ty)?; 463 *next_vreg += regclasses.len(); 464 let regs: ValueRegs<Reg> = match regclasses { 465 &[rc0] => ValueRegs::one(VReg::new(v, rc0).into()), 466 &[rc0, rc1] => ValueRegs::two(VReg::new(v, rc0).into(), VReg::new(v + 1, rc1).into()), 467 // We can extend this if/when we support 32-bit targets; e.g., 468 // an i128 on a 32-bit machine will need up to four machine regs 469 // for a `Value`. 470 _ => panic!("Value must reside in 1 or 2 registers"), 471 }; 472 for (®_ty, ®) in tys.iter().zip(regs.regs().iter()) { 473 vcode.set_vreg_type(reg.to_virtual_reg().unwrap(), reg_ty); 474 } 475 Ok(regs) 476 } 477 478 impl<'func, I: VCodeInst> Lower<'func, I> { 479 /// Prepare a new lowering context for the given IR function. 480 pub fn new( 481 f: &'func Function, 482 abi: Box<dyn ABICallee<I = I>>, 483 emit_info: I::Info, 484 block_order: BlockLoweringOrder, 485 ) -> CodegenResult<Lower<'func, I>> { 486 let constants = VCodeConstants::with_capacity(f.dfg.constants.len()); 487 let mut vcode = VCodeBuilder::new( 488 abi, 489 emit_info, 490 block_order, 491 constants, 492 VCodeBuildDirection::Backward, 493 ); 494 495 let mut next_vreg: usize = first_user_vreg_index(); 496 497 let mut value_regs = SecondaryMap::with_default(ValueRegs::invalid()); 498 499 // Assign a vreg to each block param and each inst result. 500 for bb in f.layout.blocks() { 501 for ¶m in f.dfg.block_params(bb) { 502 let ty = f.dfg.value_type(param); 503 if value_regs[param].is_invalid() { 504 let regs = alloc_vregs(ty, &mut next_vreg, &mut vcode)?; 505 value_regs[param] = regs; 506 trace!("bb {} param {}: regs {:?}", bb, param, regs); 507 } 508 } 509 for inst in f.layout.block_insts(bb) { 510 for &result in f.dfg.inst_results(inst) { 511 let ty = f.dfg.value_type(result); 512 if value_regs[result].is_invalid() { 513 let regs = alloc_vregs(ty, &mut next_vreg, &mut vcode)?; 514 value_regs[result] = regs; 515 trace!( 516 "bb {} inst {} ({:?}): result {} regs {:?}", 517 bb, 518 inst, 519 f.dfg[inst], 520 result, 521 regs, 522 ); 523 } 524 } 525 } 526 } 527 528 let vm_context = vcode 529 .abi() 530 .signature() 531 .special_param_index(ArgumentPurpose::VMContext) 532 .map(|vm_context_index| { 533 let entry_block = f.layout.entry_block().unwrap(); 534 let param = f.dfg.block_params(entry_block)[vm_context_index]; 535 value_regs[param].only_reg().unwrap() 536 }); 537 538 // Assign vreg(s) to each return value. 539 let mut retval_regs = vec![]; 540 for ret in &vcode.abi().signature().returns.clone() { 541 let regs = alloc_vregs(ret.value_type, &mut next_vreg, &mut vcode)?; 542 retval_regs.push(regs); 543 trace!("retval gets regs {:?}", regs); 544 } 545 546 // Compute instruction colors, find constant instructions, and find instructions with 547 // side-effects, in one combined pass. 548 let mut cur_color = 0; 549 let mut block_end_colors = SecondaryMap::with_default(InstColor::new(0)); 550 let mut side_effect_inst_entry_colors = FxHashMap::default(); 551 let mut inst_constants = FxHashMap::default(); 552 for bb in f.layout.blocks() { 553 cur_color += 1; 554 for inst in f.layout.block_insts(bb) { 555 let side_effect = has_lowering_side_effect(f, inst); 556 557 trace!("bb {} inst {} has color {}", bb, inst, cur_color); 558 if side_effect { 559 side_effect_inst_entry_colors.insert(inst, InstColor::new(cur_color)); 560 trace!(" -> side-effecting; incrementing color for next inst"); 561 cur_color += 1; 562 } 563 564 // Determine if this is a constant; if so, add to the table. 565 if let Some(c) = is_constant_64bit(f, inst) { 566 trace!(" -> constant: {}", c); 567 inst_constants.insert(inst, c); 568 } 569 } 570 571 block_end_colors[bb] = InstColor::new(cur_color); 572 } 573 574 let value_ir_uses = Self::compute_use_states(f); 575 576 Ok(Lower { 577 f, 578 vcode, 579 value_regs, 580 retval_regs, 581 block_end_colors, 582 side_effect_inst_entry_colors, 583 inst_constants, 584 next_vreg, 585 value_ir_uses, 586 value_lowered_uses: SecondaryMap::default(), 587 inst_sunk: FxHashSet::default(), 588 cur_scan_entry_color: None, 589 cur_inst: None, 590 ir_insts: vec![], 591 pinned_reg: None, 592 vm_context, 593 }) 594 } 595 596 /// Pre-analysis: compute `value_ir_uses`. See comment on 597 /// `ValueUseState` for a description of what this analysis 598 /// computes. 599 fn compute_use_states<'a>(f: &'a Function) -> SecondaryMap<Value, ValueUseState> { 600 // We perform the analysis without recursion, so we don't 601 // overflow the stack on long chains of ops in the input. 602 // 603 // This is sort of a hybrid of a "shallow use-count" pass and 604 // a DFS. We iterate over all instructions and mark their args 605 // as used. However when we increment a use-count to 606 // "Multiple" we push its args onto the stack and do a DFS, 607 // immediately marking the whole dependency tree as 608 // Multiple. Doing both (shallow use-counting over all insts, 609 // and deep Multiple propagation) lets us trim both 610 // traversals, stopping recursion when a node is already at 611 // the appropriate state. 612 // 613 // In particular, note that the *coarsening* into {Unused, 614 // Once, Multiple} is part of what makes this pass more 615 // efficient than a full indirect-use-counting pass. 616 617 let mut value_ir_uses: SecondaryMap<Value, ValueUseState> = 618 SecondaryMap::with_default(ValueUseState::Unused); 619 620 // Stack of iterators over Values as we do DFS to mark 621 // Multiple-state subtrees. 622 type StackVec<'a> = SmallVec<[std::slice::Iter<'a, Value>; 16]>; 623 let mut stack: StackVec = smallvec![]; 624 625 // Push args for a given inst onto the DFS stack. 626 let push_args_on_stack = |stack: &mut StackVec<'a>, value| { 627 trace!(" -> pushing args for {} onto stack", value); 628 if let ValueDef::Result(src_inst, _) = f.dfg.value_def(value) { 629 stack.push(f.dfg.inst_args(src_inst).iter()); 630 } 631 }; 632 633 // Do a DFS through `value_ir_uses` to mark a subtree as 634 // Multiple. 635 let mark_all_uses_as_multiple = 636 |value_ir_uses: &mut SecondaryMap<Value, ValueUseState>, stack: &mut StackVec<'a>| { 637 while let Some(iter) = stack.last_mut() { 638 if let Some(&value) = iter.next() { 639 let value = f.dfg.resolve_aliases(value); 640 trace!(" -> DFS reaches {}", value); 641 if value_ir_uses[value] == ValueUseState::Multiple { 642 // Truncate DFS here: no need to go further, 643 // as whole subtree must already be Multiple. 644 #[cfg(debug_assertions)] 645 { 646 // With debug asserts, check one level 647 // of that invariant at least. 648 if let ValueDef::Result(src_inst, _) = f.dfg.value_def(value) { 649 debug_assert!(f.dfg.inst_args(src_inst).iter().all(|&arg| { 650 let arg = f.dfg.resolve_aliases(arg); 651 value_ir_uses[arg] == ValueUseState::Multiple 652 })); 653 } 654 } 655 continue; 656 } 657 value_ir_uses[value] = ValueUseState::Multiple; 658 trace!(" -> became Multiple"); 659 push_args_on_stack(stack, value); 660 } else { 661 // Empty iterator, discard. 662 stack.pop(); 663 } 664 } 665 }; 666 667 for inst in f 668 .layout 669 .blocks() 670 .flat_map(|block| f.layout.block_insts(block)) 671 { 672 // If this inst produces multiple values, we must mark all 673 // of its args as Multiple, because otherwise two uses 674 // could come in as Once on our two different results. 675 let force_multiple = f.dfg.inst_results(inst).len() > 1; 676 677 // Iterate over all args of all instructions, noting an 678 // additional use on each operand. If an operand becomes Multiple, 679 for &arg in f.dfg.inst_args(inst) { 680 let arg = f.dfg.resolve_aliases(arg); 681 let old = value_ir_uses[arg]; 682 if force_multiple { 683 trace!( 684 "forcing arg {} to Multiple because of multiple results of user inst", 685 arg 686 ); 687 value_ir_uses[arg] = ValueUseState::Multiple; 688 } else { 689 value_ir_uses[arg].inc(); 690 } 691 let new = value_ir_uses[arg]; 692 trace!("arg {} used, old state {:?}, new {:?}", arg, old, new,); 693 // On transition to Multiple, do DFS. 694 if old != ValueUseState::Multiple && new == ValueUseState::Multiple { 695 push_args_on_stack(&mut stack, arg); 696 mark_all_uses_as_multiple(&mut value_ir_uses, &mut stack); 697 } 698 } 699 } 700 701 value_ir_uses 702 } 703 704 fn gen_arg_setup(&mut self) { 705 if let Some(entry_bb) = self.f.layout.entry_block() { 706 trace!( 707 "gen_arg_setup: entry BB {} args are:\n{:?}", 708 entry_bb, 709 self.f.dfg.block_params(entry_bb) 710 ); 711 712 // Make the vmctx available in debuginfo. 713 if let Some(vmctx_val) = self.f.special_param(ArgumentPurpose::VMContext) { 714 self.emit_value_label_marks_for_value(vmctx_val); 715 } 716 717 for (i, param) in self.f.dfg.block_params(entry_bb).iter().enumerate() { 718 if !self.vcode.abi().arg_is_needed_in_body(i) { 719 continue; 720 } 721 let regs = writable_value_regs(self.value_regs[*param]); 722 for insn in self.vcode.abi().gen_copy_arg_to_regs(i, regs).into_iter() { 723 self.emit(insn); 724 } 725 if self.abi().signature().params[i].purpose == ArgumentPurpose::StructReturn { 726 assert!(regs.len() == 1); 727 let ty = self.abi().signature().params[i].value_type; 728 // The ABI implementation must have ensured that a StructReturn 729 // arg is present in the return values. 730 let struct_ret_idx = self 731 .abi() 732 .signature() 733 .returns 734 .iter() 735 .position(|ret| ret.purpose == ArgumentPurpose::StructReturn) 736 .expect("StructReturn return value not present!"); 737 self.emit(I::gen_move( 738 Writable::from_reg(self.retval_regs[struct_ret_idx].regs()[0]), 739 regs.regs()[0].to_reg(), 740 ty, 741 )); 742 } 743 } 744 if let Some(insn) = self.vcode.abi().gen_retval_area_setup() { 745 self.emit(insn); 746 } 747 } 748 } 749 750 fn gen_retval_setup(&mut self) { 751 let retval_regs = self.retval_regs.clone(); 752 for (i, regs) in retval_regs.into_iter().enumerate() { 753 let regs = writable_value_regs(regs); 754 for insn in self 755 .vcode 756 .abi() 757 .gen_copy_regs_to_retval(i, regs) 758 .into_iter() 759 { 760 self.emit(insn); 761 } 762 } 763 let inst = self.vcode.abi().gen_ret(); 764 self.emit(inst); 765 766 // Hack: generate a virtual instruction that uses vmctx in 767 // order to keep it alive for the duration of the function, 768 // for the benefit of debuginfo. 769 if self.f.dfg.values_labels.is_some() { 770 if let Some(vmctx_val) = self.f.special_param(ArgumentPurpose::VMContext) { 771 let vmctx_reg = self.value_regs[vmctx_val].only_reg().unwrap(); 772 self.emit(I::gen_dummy_use(vmctx_reg)); 773 } 774 } 775 } 776 777 /// Has this instruction been sunk to a use-site (i.e., away from its 778 /// original location)? 779 fn is_inst_sunk(&self, inst: Inst) -> bool { 780 self.inst_sunk.contains(&inst) 781 } 782 783 // Is any result of this instruction needed? 784 fn is_any_inst_result_needed(&self, inst: Inst) -> bool { 785 self.f 786 .dfg 787 .inst_results(inst) 788 .iter() 789 .any(|&result| self.value_lowered_uses[result] > 0) 790 } 791 792 fn lower_clif_block<B: LowerBackend<MInst = I>>( 793 &mut self, 794 backend: &B, 795 block: Block, 796 ) -> CodegenResult<()> { 797 self.cur_scan_entry_color = Some(self.block_end_colors[block]); 798 // Lowering loop: 799 // - For each non-branch instruction, in reverse order: 800 // - If side-effecting (load, store, branch/call/return, 801 // possible trap), or if used outside of this block, or if 802 // demanded by another inst, then lower. 803 // 804 // That's it! Lowering of side-effecting ops will force all 805 // *needed* (live) non-side-effecting ops to be lowered at the 806 // right places, via the `use_input_reg()` callback on the 807 // `LowerCtx` (that's us). That's because `use_input_reg()` 808 // sets the eager/demand bit for any insts whose result 809 // registers are used. 810 // 811 // We set the VCodeBuilder to "backward" mode, so we emit 812 // blocks in reverse order wrt the BlockIndex sequence, and 813 // emit instructions in reverse order within blocks. Because 814 // the machine backend calls `ctx.emit()` in forward order, we 815 // collect per-IR-inst lowered instructions in `ir_insts`, 816 // then reverse these and append to the VCode at the end of 817 // each IR instruction. 818 for inst in self.f.layout.block_insts(block).rev() { 819 let data = &self.f.dfg[inst]; 820 let has_side_effect = has_lowering_side_effect(self.f, inst); 821 // If inst has been sunk to another location, skip it. 822 if self.is_inst_sunk(inst) { 823 continue; 824 } 825 // Are any outputs used at least once? 826 let value_needed = self.is_any_inst_result_needed(inst); 827 trace!( 828 "lower_clif_block: block {} inst {} ({:?}) is_branch {} side_effect {} value_needed {}", 829 block, 830 inst, 831 data, 832 data.opcode().is_branch(), 833 has_side_effect, 834 value_needed, 835 ); 836 837 // Update scan state to color prior to this inst (as we are scanning 838 // backward). 839 self.cur_inst = Some(inst); 840 if has_side_effect { 841 let entry_color = *self 842 .side_effect_inst_entry_colors 843 .get(&inst) 844 .expect("every side-effecting inst should have a color-map entry"); 845 self.cur_scan_entry_color = Some(entry_color); 846 } 847 848 // Skip lowering branches; these are handled separately 849 // (see `lower_clif_branches()` below). 850 if self.f.dfg[inst].opcode().is_branch() { 851 continue; 852 } 853 854 // Normal instruction: codegen if the instruction is side-effecting 855 // or any of its outputs its used. 856 if has_side_effect || value_needed { 857 trace!("lowering: inst {}: {:?}", inst, self.f.dfg[inst]); 858 backend.lower(self, inst)?; 859 } 860 if data.opcode().is_return() { 861 // Return: handle specially, using ABI-appropriate sequence. 862 self.gen_retval_setup(); 863 } 864 865 let loc = self.srcloc(inst); 866 self.finish_ir_inst(loc); 867 868 // Emit value-label markers if needed, to later recover 869 // debug mappings. This must happen before the instruction 870 // (so after we emit, in bottom-to-top pass). 871 self.emit_value_label_markers_for_inst(inst); 872 } 873 874 // Add the block params to this block. 875 self.add_block_params(block)?; 876 877 self.cur_scan_entry_color = None; 878 Ok(()) 879 } 880 881 fn add_block_params(&mut self, block: Block) -> CodegenResult<()> { 882 for ¶m in self.f.dfg.block_params(block) { 883 let ty = self.f.dfg.value_type(param); 884 let (_reg_rcs, reg_tys) = I::rc_for_type(ty)?; 885 debug_assert_eq!(reg_tys.len(), self.value_regs[param].len()); 886 for (®, &rty) in self.value_regs[param].regs().iter().zip(reg_tys.iter()) { 887 self.vcode 888 .add_block_param(reg.to_virtual_reg().unwrap(), rty); 889 } 890 } 891 Ok(()) 892 } 893 894 fn get_value_labels<'a>(&'a self, val: Value, depth: usize) -> Option<&'a [ValueLabelStart]> { 895 if let Some(ref values_labels) = self.f.dfg.values_labels { 896 trace!( 897 "get_value_labels: val {} -> {} -> {:?}", 898 val, 899 self.f.dfg.resolve_aliases(val), 900 values_labels.get(&self.f.dfg.resolve_aliases(val)) 901 ); 902 let val = self.f.dfg.resolve_aliases(val); 903 match values_labels.get(&val) { 904 Some(&ValueLabelAssignments::Starts(ref list)) => Some(&list[..]), 905 Some(&ValueLabelAssignments::Alias { value, .. }) if depth < 10 => { 906 self.get_value_labels(value, depth + 1) 907 } 908 _ => None, 909 } 910 } else { 911 None 912 } 913 } 914 915 fn emit_value_label_marks_for_value(&mut self, val: Value) { 916 let regs = self.value_regs[val]; 917 if regs.len() > 1 { 918 return; 919 } 920 let reg = regs.only_reg().unwrap(); 921 922 if let Some(label_starts) = self.get_value_labels(val, 0) { 923 let labels = label_starts 924 .iter() 925 .map(|&ValueLabelStart { label, .. }| label) 926 .collect::<FxHashSet<_>>(); 927 for label in labels { 928 trace!( 929 "value labeling: defines val {:?} -> reg {:?} -> label {:?}", 930 val, 931 reg, 932 label, 933 ); 934 self.vcode.add_value_label(reg, label); 935 } 936 } 937 } 938 939 fn emit_value_label_markers_for_inst(&mut self, inst: Inst) { 940 if self.f.dfg.values_labels.is_none() { 941 return; 942 } 943 944 trace!( 945 "value labeling: srcloc {}: inst {}", 946 self.srcloc(inst), 947 inst 948 ); 949 for &val in self.f.dfg.inst_results(inst) { 950 self.emit_value_label_marks_for_value(val); 951 } 952 } 953 954 fn emit_value_label_markers_for_block_args(&mut self, block: Block) { 955 if self.f.dfg.values_labels.is_none() { 956 return; 957 } 958 959 trace!("value labeling: block {}", block); 960 for &arg in self.f.dfg.block_params(block) { 961 self.emit_value_label_marks_for_value(arg); 962 } 963 self.finish_ir_inst(SourceLoc::default()); 964 } 965 966 fn finish_ir_inst(&mut self, loc: SourceLoc) { 967 self.vcode.set_srcloc(loc); 968 // The VCodeBuilder builds in reverse order (and reverses at 969 // the end), but `ir_insts` is in forward order, so reverse 970 // it. 971 for inst in self.ir_insts.drain(..).rev() { 972 self.vcode.push(inst); 973 } 974 } 975 976 fn finish_bb(&mut self) { 977 self.vcode.end_bb(); 978 } 979 980 fn lower_clif_branches<B: LowerBackend<MInst = I>>( 981 &mut self, 982 backend: &B, 983 // Lowered block index: 984 bindex: BlockIndex, 985 // Original CLIF block: 986 block: Block, 987 branches: &SmallVec<[Inst; 2]>, 988 targets: &SmallVec<[MachLabel; 2]>, 989 ) -> CodegenResult<()> { 990 trace!( 991 "lower_clif_branches: block {} branches {:?} targets {:?}", 992 block, 993 branches, 994 targets, 995 ); 996 // When considering code-motion opportunities, consider the current 997 // program point to be the first branch. 998 self.cur_inst = Some(branches[0]); 999 backend.lower_branch_group(self, branches, targets)?; 1000 let loc = self.srcloc(branches[0]); 1001 self.finish_ir_inst(loc); 1002 // Add block param outputs for current block. 1003 self.lower_branch_blockparam_args(bindex); 1004 Ok(()) 1005 } 1006 1007 fn lower_branch_blockparam_args(&mut self, block: BlockIndex) { 1008 for succ_idx in 0..self.vcode.block_order().succ_indices(block).len() { 1009 // Avoid immutable borrow by explicitly indexing. 1010 let (inst, succ) = self.vcode.block_order().succ_indices(block)[succ_idx]; 1011 // Get branch args and convert to Regs. 1012 let branch_args = self.f.dfg.inst_variable_args(inst); 1013 let mut branch_arg_vregs: SmallVec<[Reg; 16]> = smallvec![]; 1014 for &arg in branch_args { 1015 let arg = self.f.dfg.resolve_aliases(arg); 1016 let regs = self.put_value_in_regs(arg); 1017 for &vreg in regs.regs() { 1018 let vreg = self.vcode.resolve_vreg_alias(vreg.into()); 1019 branch_arg_vregs.push(vreg.into()); 1020 } 1021 } 1022 self.vcode.add_succ(succ, &branch_arg_vregs[..]); 1023 } 1024 self.finish_ir_inst(SourceLoc::default()); 1025 } 1026 1027 fn collect_branches_and_targets( 1028 &self, 1029 bindex: BlockIndex, 1030 _bb: Block, 1031 branches: &mut SmallVec<[Inst; 2]>, 1032 targets: &mut SmallVec<[MachLabel; 2]>, 1033 ) { 1034 branches.clear(); 1035 targets.clear(); 1036 let mut last_inst = None; 1037 for &(inst, succ) in self.vcode.block_order().succ_indices(bindex) { 1038 // Avoid duplicates: this ensures a br_table is only inserted once. 1039 if last_inst != Some(inst) { 1040 branches.push(inst); 1041 } else { 1042 debug_assert!(self.f.dfg[inst].opcode() == Opcode::BrTable); 1043 debug_assert!(branches.len() == 1); 1044 } 1045 last_inst = Some(inst); 1046 targets.push(MachLabel::from_block(succ)); 1047 } 1048 } 1049 1050 /// Lower the function. 1051 pub fn lower<B: LowerBackend<MInst = I>>(mut self, backend: &B) -> CodegenResult<VCode<I>> { 1052 trace!("about to lower function: {:?}", self.f); 1053 1054 // Initialize the ABI object, giving it temps if requested. 1055 let temps = self 1056 .vcode 1057 .abi() 1058 .temps_needed() 1059 .into_iter() 1060 .map(|temp_ty| self.alloc_tmp(temp_ty).only_reg().unwrap()) 1061 .collect::<Vec<_>>(); 1062 self.vcode.abi().init(temps); 1063 1064 // Get the pinned reg here (we only parameterize this function on `B`, 1065 // not the whole `Lower` impl). 1066 self.pinned_reg = backend.maybe_pinned_reg(); 1067 1068 self.vcode.set_entry(BlockIndex::new(0)); 1069 1070 // Reused vectors for branch lowering. 1071 let mut branches: SmallVec<[Inst; 2]> = SmallVec::new(); 1072 let mut targets: SmallVec<[MachLabel; 2]> = SmallVec::new(); 1073 1074 // get a copy of the lowered order; we hold this separately because we 1075 // need a mut ref to the vcode to mutate it below. 1076 let lowered_order: SmallVec<[LoweredBlock; 64]> = self 1077 .vcode 1078 .block_order() 1079 .lowered_order() 1080 .iter() 1081 .cloned() 1082 .collect(); 1083 1084 // Main lowering loop over lowered blocks. 1085 for (bindex, lb) in lowered_order.iter().enumerate().rev() { 1086 let bindex = BlockIndex::new(bindex); 1087 1088 // Lower the block body in reverse order (see comment in 1089 // `lower_clif_block()` for rationale). 1090 1091 // End branches. 1092 if let Some(bb) = lb.orig_block() { 1093 self.collect_branches_and_targets(bindex, bb, &mut branches, &mut targets); 1094 if branches.len() > 0 { 1095 self.lower_clif_branches(backend, bindex, bb, &branches, &targets)?; 1096 self.finish_ir_inst(self.srcloc(branches[0])); 1097 } 1098 } else { 1099 // If no orig block, this must be a pure edge block; 1100 // get the successor and emit a jump. Add block params 1101 // according to the one successor, and pass them 1102 // through; note that the successor must have an 1103 // original block. 1104 let (_, succ) = self.vcode.block_order().succ_indices(bindex)[0]; 1105 1106 let orig_succ = lowered_order[succ.index()]; 1107 let orig_succ = orig_succ 1108 .orig_block() 1109 .expect("Edge block succ must be body block"); 1110 1111 let mut branch_arg_vregs: SmallVec<[Reg; 16]> = smallvec![]; 1112 for ty in self.f.dfg.block_param_types(orig_succ) { 1113 let regs = alloc_vregs(ty, &mut self.next_vreg, &mut self.vcode)?; 1114 for ® in regs.regs() { 1115 branch_arg_vregs.push(reg); 1116 let vreg = reg.to_virtual_reg().unwrap(); 1117 self.vcode 1118 .add_block_param(vreg, self.vcode.get_vreg_type(vreg)); 1119 } 1120 } 1121 self.vcode.add_succ(succ, &branch_arg_vregs[..]); 1122 1123 self.emit(I::gen_jump(MachLabel::from_block(succ))); 1124 self.finish_ir_inst(SourceLoc::default()); 1125 } 1126 1127 // Original block body. 1128 if let Some(bb) = lb.orig_block() { 1129 self.lower_clif_block(backend, bb)?; 1130 self.emit_value_label_markers_for_block_args(bb); 1131 } 1132 1133 if bindex.index() == 0 { 1134 // Set up the function with arg vreg inits. 1135 self.gen_arg_setup(); 1136 self.finish_ir_inst(SourceLoc::default()); 1137 } 1138 1139 self.finish_bb(); 1140 } 1141 1142 // Now that we've emitted all instructions into the 1143 // VCodeBuilder, let's build the VCode. 1144 let vcode = self.vcode.build(); 1145 trace!("built vcode: {:?}", vcode); 1146 1147 Ok(vcode) 1148 } 1149 } 1150 1151 impl<'func, I: VCodeInst> LowerCtx for Lower<'func, I> { 1152 type I = I; 1153 1154 fn dfg(&self) -> &DataFlowGraph { 1155 &self.f.dfg 1156 } 1157 1158 fn abi(&mut self) -> &mut dyn ABICallee<I = I> { 1159 self.vcode.abi() 1160 } 1161 1162 fn retval(&self, idx: usize) -> ValueRegs<Writable<Reg>> { 1163 writable_value_regs(self.retval_regs[idx]) 1164 } 1165 1166 fn get_vm_context(&self) -> Option<Reg> { 1167 self.vm_context 1168 } 1169 1170 fn data(&self, ir_inst: Inst) -> &InstructionData { 1171 &self.f.dfg[ir_inst] 1172 } 1173 1174 fn ty(&self, ir_inst: Inst) -> Type { 1175 self.f.dfg.ctrl_typevar(ir_inst) 1176 } 1177 1178 fn call_target<'b>(&'b self, ir_inst: Inst) -> Option<(&'b ExternalName, RelocDistance)> { 1179 match &self.f.dfg[ir_inst] { 1180 &InstructionData::Call { func_ref, .. } 1181 | &InstructionData::FuncAddr { func_ref, .. } => { 1182 let funcdata = &self.f.dfg.ext_funcs[func_ref]; 1183 let dist = funcdata.reloc_distance(); 1184 Some((&funcdata.name, dist)) 1185 } 1186 _ => None, 1187 } 1188 } 1189 1190 fn call_sig<'b>(&'b self, ir_inst: Inst) -> Option<&'b Signature> { 1191 match &self.f.dfg[ir_inst] { 1192 &InstructionData::Call { func_ref, .. } => { 1193 let funcdata = &self.f.dfg.ext_funcs[func_ref]; 1194 Some(&self.f.dfg.signatures[funcdata.signature]) 1195 } 1196 &InstructionData::CallIndirect { sig_ref, .. } => Some(&self.f.dfg.signatures[sig_ref]), 1197 _ => None, 1198 } 1199 } 1200 1201 fn symbol_value<'b>(&'b self, ir_inst: Inst) -> Option<(&'b ExternalName, RelocDistance, i64)> { 1202 match &self.f.dfg[ir_inst] { 1203 &InstructionData::UnaryGlobalValue { global_value, .. } => { 1204 self.symbol_value_data(global_value) 1205 } 1206 _ => None, 1207 } 1208 } 1209 1210 fn symbol_value_data<'b>( 1211 &'b self, 1212 global_value: GlobalValue, 1213 ) -> Option<(&'b ExternalName, RelocDistance, i64)> { 1214 let gvdata = &self.f.global_values[global_value]; 1215 match gvdata { 1216 &GlobalValueData::Symbol { 1217 ref name, 1218 ref offset, 1219 .. 1220 } => { 1221 let offset = offset.bits(); 1222 let dist = gvdata.maybe_reloc_distance().unwrap(); 1223 Some((name, dist, offset)) 1224 } 1225 _ => None, 1226 } 1227 } 1228 1229 fn memflags(&self, ir_inst: Inst) -> Option<MemFlags> { 1230 match &self.f.dfg[ir_inst] { 1231 &InstructionData::AtomicCas { flags, .. } => Some(flags), 1232 &InstructionData::AtomicRmw { flags, .. } => Some(flags), 1233 &InstructionData::Load { flags, .. } 1234 | &InstructionData::LoadNoOffset { flags, .. } 1235 | &InstructionData::Store { flags, .. } => Some(flags), 1236 &InstructionData::StoreNoOffset { flags, .. } => Some(flags), 1237 _ => None, 1238 } 1239 } 1240 1241 fn srcloc(&self, ir_inst: Inst) -> SourceLoc { 1242 self.f.srclocs[ir_inst] 1243 } 1244 1245 fn num_inputs(&self, ir_inst: Inst) -> usize { 1246 self.f.dfg.inst_args(ir_inst).len() 1247 } 1248 1249 fn num_outputs(&self, ir_inst: Inst) -> usize { 1250 self.f.dfg.inst_results(ir_inst).len() 1251 } 1252 1253 fn input_ty(&self, ir_inst: Inst, idx: usize) -> Type { 1254 self.value_ty(self.input_as_value(ir_inst, idx)) 1255 } 1256 1257 fn value_ty(&self, val: Value) -> Type { 1258 self.f.dfg.value_type(val) 1259 } 1260 1261 fn output_ty(&self, ir_inst: Inst, idx: usize) -> Type { 1262 self.f.dfg.value_type(self.f.dfg.inst_results(ir_inst)[idx]) 1263 } 1264 1265 fn get_constant(&self, ir_inst: Inst) -> Option<u64> { 1266 self.inst_constants.get(&ir_inst).cloned() 1267 } 1268 1269 fn input_as_value(&self, ir_inst: Inst, idx: usize) -> Value { 1270 let val = self.f.dfg.inst_args(ir_inst)[idx]; 1271 self.f.dfg.resolve_aliases(val) 1272 } 1273 1274 fn get_input_as_source_or_const(&self, ir_inst: Inst, idx: usize) -> NonRegInput { 1275 let val = self.input_as_value(ir_inst, idx); 1276 self.get_value_as_source_or_const(val) 1277 } 1278 1279 fn get_value_as_source_or_const(&self, val: Value) -> NonRegInput { 1280 trace!( 1281 "get_input_for_val: val {} at cur_inst {:?} cur_scan_entry_color {:?}", 1282 val, 1283 self.cur_inst, 1284 self.cur_scan_entry_color, 1285 ); 1286 let inst = match self.f.dfg.value_def(val) { 1287 // OK to merge source instruction if (i) we have a source 1288 // instruction, and: 1289 // - It has no side-effects, OR 1290 // - It has a side-effect, has one output value, that one 1291 // output has only one use, directly or indirectly (so 1292 // cannot be duplicated -- see comment on 1293 // `ValueUseState`), and the instruction's color is *one 1294 // less than* the current scan color. 1295 // 1296 // This latter set of conditions is testing whether a 1297 // side-effecting instruction can sink to the current scan 1298 // location; this is possible if the in-color of this inst is 1299 // equal to the out-color of the producing inst, so no other 1300 // side-effecting ops occur between them (which will only be true 1301 // if they are in the same BB, because color increments at each BB 1302 // start). 1303 // 1304 // If it is actually sunk, then in `merge_inst()`, we update the 1305 // scan color so that as we scan over the range past which the 1306 // instruction was sunk, we allow other instructions (that came 1307 // prior to the sunk instruction) to sink. 1308 ValueDef::Result(src_inst, result_idx) => { 1309 let src_side_effect = has_lowering_side_effect(self.f, src_inst); 1310 trace!(" -> src inst {}", src_inst); 1311 trace!(" -> has lowering side effect: {}", src_side_effect); 1312 if !src_side_effect { 1313 // Pure instruction: always possible to 1314 // sink. Let's determine whether we are the only 1315 // user or not. 1316 if self.value_ir_uses[val] == ValueUseState::Once { 1317 InputSourceInst::UniqueUse(src_inst, result_idx) 1318 } else { 1319 InputSourceInst::Use(src_inst, result_idx) 1320 } 1321 } else { 1322 // Side-effect: test whether this is the only use of the 1323 // only result of the instruction, and whether colors allow 1324 // the code-motion. 1325 trace!( 1326 " -> side-effecting op {} for val {}: use state {:?}", 1327 src_inst, 1328 val, 1329 self.value_ir_uses[val] 1330 ); 1331 if self.cur_scan_entry_color.is_some() 1332 && self.value_ir_uses[val] == ValueUseState::Once 1333 && self.num_outputs(src_inst) == 1 1334 && self 1335 .side_effect_inst_entry_colors 1336 .get(&src_inst) 1337 .unwrap() 1338 .get() 1339 + 1 1340 == self.cur_scan_entry_color.unwrap().get() 1341 { 1342 InputSourceInst::UniqueUse(src_inst, 0) 1343 } else { 1344 InputSourceInst::None 1345 } 1346 } 1347 } 1348 _ => InputSourceInst::None, 1349 }; 1350 let constant = inst.as_inst().and_then(|(inst, _)| self.get_constant(inst)); 1351 1352 NonRegInput { inst, constant } 1353 } 1354 1355 fn increment_lowered_uses(&mut self, val: Value) { 1356 self.value_lowered_uses[val] += 1 1357 } 1358 1359 fn put_input_in_regs(&mut self, ir_inst: Inst, idx: usize) -> ValueRegs<Reg> { 1360 let val = self.f.dfg.inst_args(ir_inst)[idx]; 1361 self.put_value_in_regs(val) 1362 } 1363 1364 fn put_value_in_regs(&mut self, val: Value) -> ValueRegs<Reg> { 1365 let val = self.f.dfg.resolve_aliases(val); 1366 trace!("put_value_in_regs: val {}", val); 1367 1368 // Assert that the value is not `iflags`/`fflags`-typed; these 1369 // cannot be reified into normal registers. TODO(#3249) 1370 // eventually remove the `iflags` type altogether! 1371 let ty = self.f.dfg.value_type(val); 1372 assert!(ty != IFLAGS && ty != FFLAGS); 1373 1374 // If the value is a constant, then (re)materialize it at each use. This 1375 // lowers register pressure. 1376 if let Some(c) = self 1377 .f 1378 .dfg 1379 .value_def(val) 1380 .inst() 1381 .and_then(|inst| self.get_constant(inst)) 1382 { 1383 let regs = self.alloc_tmp(ty); 1384 trace!(" -> regs {:?}", regs); 1385 assert!(regs.is_valid()); 1386 1387 let insts = I::gen_constant(regs, c.into(), ty, |ty| { 1388 self.alloc_tmp(ty).only_reg().unwrap() 1389 }); 1390 for inst in insts { 1391 self.emit(inst); 1392 } 1393 return non_writable_value_regs(regs); 1394 } 1395 1396 let mut regs = self.value_regs[val]; 1397 trace!(" -> regs {:?}", regs); 1398 assert!(regs.is_valid()); 1399 1400 self.value_lowered_uses[val] += 1; 1401 1402 // Pinned-reg hack: if backend specifies a fixed pinned register, use it 1403 // directly when we encounter a GetPinnedReg op, rather than lowering 1404 // the actual op, and do not return the source inst to the caller; the 1405 // value comes "out of the ether" and we will not force generation of 1406 // the superfluous move. 1407 if let ValueDef::Result(i, 0) = self.f.dfg.value_def(val) { 1408 if self.f.dfg[i].opcode() == Opcode::GetPinnedReg { 1409 if let Some(pr) = self.pinned_reg { 1410 regs = ValueRegs::one(pr); 1411 } 1412 } 1413 } 1414 1415 regs 1416 } 1417 1418 fn get_output(&self, ir_inst: Inst, idx: usize) -> ValueRegs<Writable<Reg>> { 1419 let val = self.f.dfg.inst_results(ir_inst)[idx]; 1420 writable_value_regs(self.value_regs[val]) 1421 } 1422 1423 fn alloc_tmp(&mut self, ty: Type) -> ValueRegs<Writable<Reg>> { 1424 writable_value_regs(alloc_vregs(ty, &mut self.next_vreg, &mut self.vcode).unwrap()) 1425 } 1426 1427 fn emit(&mut self, mach_inst: I) { 1428 trace!("emit: {:?}", mach_inst); 1429 self.ir_insts.push(mach_inst); 1430 } 1431 1432 fn sink_inst(&mut self, ir_inst: Inst) { 1433 assert!(has_lowering_side_effect(self.f, ir_inst)); 1434 assert!(self.cur_scan_entry_color.is_some()); 1435 1436 let sunk_inst_entry_color = self 1437 .side_effect_inst_entry_colors 1438 .get(&ir_inst) 1439 .cloned() 1440 .unwrap(); 1441 let sunk_inst_exit_color = InstColor::new(sunk_inst_entry_color.get() + 1); 1442 assert!(sunk_inst_exit_color == self.cur_scan_entry_color.unwrap()); 1443 self.cur_scan_entry_color = Some(sunk_inst_entry_color); 1444 self.inst_sunk.insert(ir_inst); 1445 } 1446 1447 fn get_immediate_data(&self, imm: Immediate) -> &ConstantData { 1448 self.f.dfg.immediates.get(imm).unwrap() 1449 } 1450 1451 fn get_constant_data(&self, constant_handle: Constant) -> &ConstantData { 1452 self.f.dfg.constants.get(constant_handle) 1453 } 1454 1455 fn use_constant(&mut self, constant: VCodeConstantData) -> VCodeConstant { 1456 self.vcode.constants().insert(constant) 1457 } 1458 1459 fn get_immediate(&self, ir_inst: Inst) -> Option<DataValue> { 1460 let inst_data = self.data(ir_inst); 1461 match inst_data { 1462 InstructionData::Shuffle { imm, .. } => { 1463 let buffer = self.f.dfg.immediates.get(imm.clone()).unwrap().as_slice(); 1464 let value = DataValue::V128(buffer.try_into().expect("a 16-byte data buffer")); 1465 Some(value) 1466 } 1467 InstructionData::UnaryConst { 1468 constant_handle, .. 1469 } => { 1470 let buffer = self.f.dfg.constants.get(constant_handle.clone()).as_slice(); 1471 let value = DataValue::V128(buffer.try_into().expect("a 16-byte data buffer")); 1472 Some(value) 1473 } 1474 _ => inst_data.imm_value(), 1475 } 1476 } 1477 1478 fn ensure_in_vreg(&mut self, reg: Reg, ty: Type) -> Reg { 1479 if reg.to_virtual_reg().is_some() { 1480 reg 1481 } else { 1482 let new_reg = self.alloc_tmp(ty).only_reg().unwrap(); 1483 self.emit(I::gen_move(new_reg, reg, ty)); 1484 new_reg.to_reg() 1485 } 1486 } 1487 1488 fn set_vreg_alias(&mut self, from: Reg, to: Reg) { 1489 trace!("set vreg alias: from {:?} to {:?}", from, to); 1490 self.vcode.set_vreg_alias(from, to); 1491 } 1492 } 1493