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