cranelift_codegen/machinst/
lower.rs

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 `Lower` from the lowering logic built on
6// top of it, e.g. the side-effect/coloring analysis and the scan support.
7
8use crate::entity::SecondaryMap;
9use crate::inst_predicates::{has_lowering_side_effect, is_constant_64bit};
10use crate::ir::pcc::{Fact, FactContext, PccError, PccResult};
11use crate::ir::{
12    ArgumentPurpose, Block, BlockArg, Constant, ConstantData, DataFlowGraph, ExternalName,
13    Function, GlobalValue, GlobalValueData, Immediate, Inst, InstructionData, MemFlags,
14    RelSourceLoc, SigRef, Signature, Type, Value, ValueDef, ValueLabelAssignments, ValueLabelStart,
15};
16use crate::machinst::valueregs::InvalidSentinel;
17use crate::machinst::{
18    ABIMachineSpec, BackwardsInsnIndex, BlockIndex, BlockLoweringOrder, CallArgList, CallInfo,
19    CallRetList, Callee, InsnIndex, LoweredBlock, MachLabel, Reg, Sig, SigSet, TryCallInfo, VCode,
20    VCodeBuilder, VCodeConstant, VCodeConstantData, VCodeConstants, VCodeInst, ValueRegs, Writable,
21    writable_value_regs,
22};
23use crate::settings::Flags;
24use crate::{CodegenError, CodegenResult, trace};
25use alloc::vec::Vec;
26use cranelift_control::ControlPlane;
27use rustc_hash::{FxHashMap, FxHashSet};
28use smallvec::{SmallVec, smallvec};
29use std::fmt::Debug;
30
31use super::{VCodeBuildDirection, VRegAllocator};
32
33/// A vector of ValueRegs, used to represent the outputs of an instruction.
34pub type InstOutput = SmallVec<[ValueRegs<Reg>; 2]>;
35
36/// An "instruction color" partitions CLIF instructions by side-effecting ops.
37/// All instructions with the same "color" are guaranteed not to be separated by
38/// any side-effecting op (for this purpose, loads are also considered
39/// side-effecting, to avoid subtle questions w.r.t. the memory model), and
40/// furthermore, it is guaranteed that for any two instructions A and B such
41/// that color(A) == color(B), either A dominates B and B postdominates A, or
42/// vice-versa. (For now, in practice, only ops in the same basic block can ever
43/// have the same color, trivially providing the second condition.) Intuitively,
44/// this means that the ops of the same color must always execute "together", as
45/// part of one atomic contiguous section of the dynamic execution trace, and
46/// they can be freely permuted (modulo true dataflow dependencies) without
47/// affecting program behavior.
48#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
49struct InstColor(u32);
50impl InstColor {
51    fn new(n: u32) -> InstColor {
52        InstColor(n)
53    }
54
55    /// Get an arbitrary index representing this color. The index is unique
56    /// *within a single function compilation*, but indices may be reused across
57    /// functions.
58    pub fn get(self) -> u32 {
59        self.0
60    }
61}
62
63/// A representation of all of the ways in which a value is available, aside
64/// from as a direct register.
65///
66/// - An instruction, if it would be allowed to occur at the current location
67///   instead (see [Lower::get_input_as_source_or_const()] for more details).
68///
69/// - A constant, if the value is known to be a constant.
70#[derive(Clone, Copy, Debug)]
71pub struct NonRegInput {
72    /// An instruction produces this value (as the given output), and its
73    /// computation (and side-effect if applicable) could occur at the
74    /// current instruction's location instead.
75    ///
76    /// If this instruction's operation is merged into the current instruction,
77    /// the backend must call [Lower::sink_inst()].
78    ///
79    /// This enum indicates whether this use of the source instruction
80    /// is unique or not.
81    pub inst: InputSourceInst,
82    /// The value is a known constant.
83    pub constant: Option<u64>,
84}
85
86/// When examining an input to an instruction, this enum provides one
87/// of several options: there is or isn't a single instruction (that
88/// we can see and merge with) that produces that input's value, and
89/// we are or aren't the single user of that instruction.
90#[derive(Clone, Copy, Debug)]
91pub enum InputSourceInst {
92    /// The input in question is the single, unique use of the given
93    /// instruction and output index, and it can be sunk to the
94    /// location of this input.
95    UniqueUse(Inst, usize),
96    /// The input in question is one of multiple uses of the given
97    /// instruction. It can still be sunk to the location of this
98    /// input.
99    Use(Inst, usize),
100    /// We cannot determine which instruction produced the input, or
101    /// it is one of several instructions (e.g., due to a control-flow
102    /// merge and blockparam), or the source instruction cannot be
103    /// allowed to sink to the current location due to side-effects.
104    None,
105}
106
107impl InputSourceInst {
108    /// Get the instruction and output index for this source, whether
109    /// we are its single or one of many users.
110    pub fn as_inst(&self) -> Option<(Inst, usize)> {
111        match self {
112            &InputSourceInst::UniqueUse(inst, output_idx)
113            | &InputSourceInst::Use(inst, output_idx) => Some((inst, output_idx)),
114            &InputSourceInst::None => None,
115        }
116    }
117}
118
119/// A machine backend.
120pub trait LowerBackend {
121    /// The machine instruction type.
122    type MInst: VCodeInst;
123
124    /// Lower a single instruction.
125    ///
126    /// For a branch, this function should not generate the actual branch
127    /// instruction. However, it must force any values it needs for the branch
128    /// edge (block-param actuals) into registers, because the actual branch
129    /// generation (`lower_branch()`) happens *after* any possible merged
130    /// out-edge.
131    ///
132    /// Returns `None` if no lowering for the instruction was found.
133    fn lower(&self, ctx: &mut Lower<Self::MInst>, inst: Inst) -> Option<InstOutput>;
134
135    /// Lower a block-terminating group of branches (which together can be seen
136    /// as one N-way branch), given a vcode MachLabel for each target.
137    ///
138    /// Returns `None` if no lowering for the branch was found.
139    fn lower_branch(
140        &self,
141        ctx: &mut Lower<Self::MInst>,
142        inst: Inst,
143        targets: &[MachLabel],
144    ) -> Option<()>;
145
146    /// A bit of a hack: give a fixed register that always holds the result of a
147    /// `get_pinned_reg` instruction, if known.  This allows elision of moves
148    /// into the associated vreg, instead using the real reg directly.
149    fn maybe_pinned_reg(&self) -> Option<Reg> {
150        None
151    }
152
153    /// The type of state carried between `check_fact` invocations.
154    type FactFlowState: Default + Clone + Debug;
155
156    /// Check any facts about an instruction, given VCode with facts
157    /// on VRegs. Takes mutable `VCode` so that it can propagate some
158    /// kinds of facts automatically.
159    fn check_fact(
160        &self,
161        _ctx: &FactContext<'_>,
162        _vcode: &mut VCode<Self::MInst>,
163        _inst: InsnIndex,
164        _state: &mut Self::FactFlowState,
165    ) -> PccResult<()> {
166        Err(PccError::UnimplementedBackend)
167    }
168}
169
170/// Machine-independent lowering driver / machine-instruction container. Maintains a correspondence
171/// from original Inst to MachInsts.
172pub struct Lower<'func, I: VCodeInst> {
173    /// The function to lower.
174    pub(crate) f: &'func Function,
175
176    /// Lowered machine instructions.
177    vcode: VCodeBuilder<I>,
178
179    /// VReg allocation context, given to the vcode field at build time to finalize the vcode.
180    vregs: VRegAllocator<I>,
181
182    /// Mapping from `Value` (SSA value in IR) to virtual register.
183    value_regs: SecondaryMap<Value, ValueRegs<Reg>>,
184
185    /// sret registers, if needed.
186    sret_reg: Option<ValueRegs<Reg>>,
187
188    /// Instruction colors at block exits. From this map, we can recover all
189    /// instruction colors by scanning backward from the block end and
190    /// decrementing on any color-changing (side-effecting) instruction.
191    block_end_colors: SecondaryMap<Block, InstColor>,
192
193    /// Instruction colors at side-effecting ops. This is the *entry* color,
194    /// i.e., the version of global state that exists before an instruction
195    /// executes.  For each side-effecting instruction, the *exit* color is its
196    /// entry color plus one.
197    side_effect_inst_entry_colors: FxHashMap<Inst, InstColor>,
198
199    /// Current color as we scan during lowering. While we are lowering an
200    /// instruction, this is equal to the color *at entry to* the instruction.
201    cur_scan_entry_color: Option<InstColor>,
202
203    /// Current instruction as we scan during lowering.
204    cur_inst: Option<Inst>,
205
206    /// Instruction constant values, if known.
207    inst_constants: FxHashMap<Inst, u64>,
208
209    /// Use-counts per SSA value, as counted in the input IR. These
210    /// are "coarsened", in the abstract-interpretation sense: we only
211    /// care about "0, 1, many" states, as this is all we need and
212    /// this lets us do an efficient fixpoint analysis.
213    ///
214    /// See doc comment on `ValueUseState` for more details.
215    value_ir_uses: SecondaryMap<Value, ValueUseState>,
216
217    /// Actual uses of each SSA value so far, incremented while lowering.
218    value_lowered_uses: SecondaryMap<Value, u32>,
219
220    /// Effectful instructions that have been sunk; they are not codegen'd at
221    /// their original locations.
222    inst_sunk: FxHashSet<Inst>,
223
224    /// Instructions collected for the CLIF inst in progress, in forward order.
225    ir_insts: Vec<I>,
226
227    /// Try-call block arg normal-return values, indexed by instruction.
228    try_call_rets: FxHashMap<Inst, SmallVec<[ValueRegs<Writable<Reg>>; 2]>>,
229
230    /// Try-call block arg exceptional-return payloads, indexed by
231    /// instruction. Payloads are carried in registers per the ABI and
232    /// can only be one register each.
233    try_call_payloads: FxHashMap<Inst, SmallVec<[Writable<Reg>; 2]>>,
234
235    /// The register to use for GetPinnedReg, if any, on this architecture.
236    pinned_reg: Option<Reg>,
237
238    /// Compilation flags.
239    flags: Flags,
240}
241
242/// How is a value used in the IR?
243///
244/// This can be seen as a coarsening of an integer count. We only need
245/// distinct states for zero, one, or many.
246///
247/// This analysis deserves further explanation. The basic idea is that
248/// we want to allow instruction lowering to know whether a value that
249/// an instruction references is *only* referenced by that one use, or
250/// by others as well. This is necessary to know when we might want to
251/// move a side-effect: we cannot, for example, duplicate a load, so
252/// we cannot let instruction lowering match a load as part of a
253/// subpattern and potentially incorporate it.
254///
255/// Note that a lot of subtlety comes into play once we have
256/// *indirect* uses. The classical example of this in our development
257/// history was the x86 compare instruction, which is incorporated
258/// into flags users (e.g. `selectif`, `trueif`, branches) and can
259/// subsequently incorporate loads, or at least we would like it
260/// to. However, danger awaits: the compare might be the only user of
261/// a load, so we might think we can just move the load (and nothing
262/// is duplicated -- success!), except that the compare itself is
263/// codegen'd in multiple places, where it is incorporated as a
264/// subpattern itself.
265///
266/// So we really want a notion of "unique all the way along the
267/// matching path". Rust's `&T` and `&mut T` offer a partial analogy
268/// to the semantics that we want here: we want to know when we've
269/// matched a unique use of an instruction, and that instruction's
270/// unique use of another instruction, etc, just as `&mut T` can only
271/// be obtained by going through a chain of `&mut T`. If one has a
272/// `&T` to a struct containing `&mut T` (one of several uses of an
273/// instruction that itself has a unique use of an instruction), one
274/// can only get a `&T` (one can only get a "I am one of several users
275/// of this instruction" result).
276///
277/// We could track these paths, either dynamically as one "looks up the operand
278/// tree" or precomputed. But the former requires state and means that the
279/// `Lower` API carries that state implicitly, which we'd like to avoid if we
280/// can. And the latter implies O(n^2) storage: it is an all-pairs property (is
281/// inst `i` unique from the point of view of `j`).
282///
283/// To make matters even a little more complex still, a value that is
284/// not uniquely used when initially viewing the IR can *become*
285/// uniquely used, at least as a root allowing further unique uses of
286/// e.g. loads to merge, if no other instruction actually merges
287/// it. To be more concrete, if we have `v1 := load; v2 := op v1; v3
288/// := op v2; v4 := op v2` then `v2` is non-uniquely used, so from the
289/// point of view of lowering `v4` or `v3`, we cannot merge the load
290/// at `v1`. But if we decide just to use the assigned register for
291/// `v2` at both `v3` and `v4`, then we only actually codegen `v2`
292/// once, so it *is* a unique root at that point and we *can* merge
293/// the load.
294///
295/// Note also that the color scheme is not sufficient to give us this
296/// information, for various reasons: reasoning about side-effects
297/// does not tell us about potential duplication of uses through pure
298/// ops.
299///
300/// To keep things simple and avoid error-prone lowering APIs that
301/// would extract more information about whether instruction merging
302/// happens or not (we don't have that info now, and it would be
303/// difficult to refactor to get it and make that refactor 100%
304/// correct), we give up on the above "can become unique if not
305/// actually merged" point. Instead, we compute a
306/// transitive-uniqueness. That is what this enum represents.
307///
308/// There is one final caveat as well to the result of this analysis.  Notably,
309/// we define some instructions to be "root" instructions, which means that we
310/// assume they will always be codegen'd at the root of a matching tree, and not
311/// matched. (This comes with the caveat that we actually enforce this property
312/// by making them "opaque" to subtree matching in
313/// `get_value_as_source_or_const`). Because they will always be codegen'd once,
314/// they in some sense "reset" multiplicity: these root instructions can be used
315/// many times, but because their result(s) are only computed once, they only
316/// use their inputs once.
317///
318/// We currently define all multi-result instructions to be "root" instructions,
319/// because it is too complex to reason about matching through them, and they
320/// cause too-coarse-grained approximation of multiplicity otherwise: the
321/// analysis would have to assume (as it used to!) that they are always
322/// multiply-used, simply because they have multiple outputs even if those
323/// outputs are used only once.
324///
325/// In the future we could define other instructions to be "root" instructions
326/// as well, if we make the corresponding change to get_value_as_source_or_const
327/// as well.
328///
329/// To define `ValueUseState` more plainly: a value is `Unused` if no references
330/// exist to it; `Once` if only one other op refers to it, *and* that other op
331/// is `Unused` or `Once`; and `Multiple` otherwise. In other words, `Multiple`
332/// is contagious (except through root instructions): even if an op's result
333/// value is directly used only once in the CLIF, that value is `Multiple` if
334/// the op that uses it is itself used multiple times (hence could be codegen'd
335/// multiple times). In brief, this analysis tells us whether, if every op
336/// merged all of its operand tree, a given op could be codegen'd in more than
337/// one place.
338///
339/// To compute this, we first consider direct uses. At this point
340/// `Unused` answers are correct, `Multiple` answers are correct, but
341/// some `Once`s may change to `Multiple`s. Then we propagate
342/// `Multiple` transitively using a workqueue/fixpoint algorithm.
343#[derive(Clone, Copy, Debug, PartialEq, Eq)]
344enum ValueUseState {
345    /// Not used at all.
346    Unused,
347    /// Used exactly once.
348    Once,
349    /// Used multiple times.
350    Multiple,
351}
352
353impl ValueUseState {
354    /// Add one use.
355    fn inc(&mut self) {
356        let new = match self {
357            Self::Unused => Self::Once,
358            Self::Once | Self::Multiple => Self::Multiple,
359        };
360        *self = new;
361    }
362}
363
364/// Notion of "relocation distance". This gives an estimate of how far away a symbol will be from a
365/// reference.
366#[derive(Clone, Copy, Debug, PartialEq, Eq)]
367pub enum RelocDistance {
368    /// Target of relocation is "nearby". The threshold for this is fuzzy but should be interpreted
369    /// as approximately "within the compiled output of one module"; e.g., within AArch64's +/-
370    /// 128MB offset. If unsure, use `Far` instead.
371    Near,
372    /// Target of relocation could be anywhere in the address space.
373    Far,
374}
375
376impl<'func, I: VCodeInst> Lower<'func, I> {
377    /// Prepare a new lowering context for the given IR function.
378    pub fn new(
379        f: &'func Function,
380        abi: Callee<I::ABIMachineSpec>,
381        emit_info: I::Info,
382        block_order: BlockLoweringOrder,
383        sigs: SigSet,
384        flags: Flags,
385    ) -> CodegenResult<Self> {
386        let constants = VCodeConstants::with_capacity(f.dfg.constants.len());
387        let vcode = VCodeBuilder::new(
388            sigs,
389            abi,
390            emit_info,
391            block_order,
392            constants,
393            VCodeBuildDirection::Backward,
394            flags.log2_min_function_alignment(),
395        );
396
397        // We usually need two VRegs per instruction result, plus extras for
398        // various temporaries, but two per Value is a good starting point.
399        let mut vregs = VRegAllocator::with_capacity(f.dfg.num_values() * 2);
400
401        let mut value_regs = SecondaryMap::with_default(ValueRegs::invalid());
402        let mut try_call_rets = FxHashMap::default();
403        let mut try_call_payloads = FxHashMap::default();
404
405        // Assign a vreg to each block param, each inst result, and
406        // each edge-defined block-call arg.
407        for bb in f.layout.blocks() {
408            for &param in f.dfg.block_params(bb) {
409                let ty = f.dfg.value_type(param);
410                if value_regs[param].is_invalid() {
411                    let regs = vregs.alloc_with_maybe_fact(ty, f.dfg.facts[param].clone())?;
412                    value_regs[param] = regs;
413                    trace!("bb {} param {}: regs {:?}", bb, param, regs);
414                }
415            }
416            for inst in f.layout.block_insts(bb) {
417                for &result in f.dfg.inst_results(inst) {
418                    let ty = f.dfg.value_type(result);
419                    if value_regs[result].is_invalid() && !ty.is_invalid() {
420                        let regs = vregs.alloc_with_maybe_fact(ty, f.dfg.facts[result].clone())?;
421                        value_regs[result] = regs;
422                        trace!(
423                            "bb {} inst {} ({:?}): result {} regs {:?}",
424                            bb, inst, f.dfg.insts[inst], result, regs,
425                        );
426                    }
427                }
428
429                if let Some(et) = f.dfg.insts[inst].exception_table() {
430                    let exdata = &f.dfg.exception_tables[et];
431                    let sig = &f.dfg.signatures[exdata.signature()];
432
433                    let mut rets = smallvec![];
434                    for ty in sig.returns.iter().map(|ret| ret.value_type) {
435                        rets.push(vregs.alloc(ty)?.map(|r| Writable::from_reg(r)));
436                    }
437                    try_call_rets.insert(inst, rets);
438
439                    let mut payloads = smallvec![];
440                    // Note that this is intentionally using the calling
441                    // convention of the callee to determine what payload types
442                    // are available. The callee defines that, not the calling
443                    // convention of the caller.
444                    for &ty in sig
445                        .call_conv
446                        .exception_payload_types(I::ABIMachineSpec::word_type())
447                    {
448                        payloads.push(Writable::from_reg(vregs.alloc(ty)?.only_reg().unwrap()));
449                    }
450                    try_call_payloads.insert(inst, payloads);
451                }
452            }
453        }
454
455        // Find the sret register, if it's used.
456        let mut sret_param = None;
457        for ret in vcode.abi().signature().returns.iter() {
458            if ret.purpose == ArgumentPurpose::StructReturn {
459                let entry_bb = f.stencil.layout.entry_block().unwrap();
460                for (&param, sig_param) in f
461                    .dfg
462                    .block_params(entry_bb)
463                    .iter()
464                    .zip(vcode.abi().signature().params.iter())
465                {
466                    if sig_param.purpose == ArgumentPurpose::StructReturn {
467                        assert!(sret_param.is_none());
468                        sret_param = Some(param);
469                    }
470                }
471
472                assert!(sret_param.is_some());
473            }
474        }
475
476        let sret_reg = sret_param.map(|param| {
477            let regs = value_regs[param];
478            assert!(regs.len() == 1);
479            regs
480        });
481
482        // Compute instruction colors, find constant instructions, and find instructions with
483        // side-effects, in one combined pass.
484        let mut cur_color = 0;
485        let mut block_end_colors = SecondaryMap::with_default(InstColor::new(0));
486        let mut side_effect_inst_entry_colors = FxHashMap::default();
487        let mut inst_constants = FxHashMap::default();
488        for bb in f.layout.blocks() {
489            cur_color += 1;
490            for inst in f.layout.block_insts(bb) {
491                let side_effect = has_lowering_side_effect(f, inst);
492
493                trace!("bb {} inst {} has color {}", bb, inst, cur_color);
494                if side_effect {
495                    side_effect_inst_entry_colors.insert(inst, InstColor::new(cur_color));
496                    trace!(" -> side-effecting; incrementing color for next inst");
497                    cur_color += 1;
498                }
499
500                // Determine if this is a constant; if so, add to the table.
501                if let Some(c) = is_constant_64bit(f, inst) {
502                    trace!(" -> constant: {}", c);
503                    inst_constants.insert(inst, c);
504                }
505            }
506
507            block_end_colors[bb] = InstColor::new(cur_color);
508        }
509
510        let value_ir_uses = compute_use_states(f, sret_param);
511
512        Ok(Lower {
513            f,
514            vcode,
515            vregs,
516            value_regs,
517            sret_reg,
518            block_end_colors,
519            side_effect_inst_entry_colors,
520            inst_constants,
521            value_ir_uses,
522            value_lowered_uses: SecondaryMap::default(),
523            inst_sunk: FxHashSet::default(),
524            cur_scan_entry_color: None,
525            cur_inst: None,
526            ir_insts: vec![],
527            try_call_rets,
528            try_call_payloads,
529            pinned_reg: None,
530            flags,
531        })
532    }
533
534    pub fn sigs(&self) -> &SigSet {
535        self.vcode.sigs()
536    }
537
538    pub fn sigs_mut(&mut self) -> &mut SigSet {
539        self.vcode.sigs_mut()
540    }
541
542    pub fn vregs_mut(&mut self) -> &mut VRegAllocator<I> {
543        &mut self.vregs
544    }
545
546    fn gen_arg_setup(&mut self) {
547        if let Some(entry_bb) = self.f.layout.entry_block() {
548            trace!(
549                "gen_arg_setup: entry BB {} args are:\n{:?}",
550                entry_bb,
551                self.f.dfg.block_params(entry_bb)
552            );
553
554            for (i, param) in self.f.dfg.block_params(entry_bb).iter().enumerate() {
555                if self.value_ir_uses[*param] == ValueUseState::Unused {
556                    continue;
557                }
558                let regs = writable_value_regs(self.value_regs[*param]);
559                for insn in self
560                    .vcode
561                    .vcode
562                    .abi
563                    .gen_copy_arg_to_regs(&self.vcode.vcode.sigs, i, regs, &mut self.vregs)
564                    .into_iter()
565                {
566                    self.emit(insn);
567                }
568            }
569            if let Some(insn) = self
570                .vcode
571                .vcode
572                .abi
573                .gen_retval_area_setup(&self.vcode.vcode.sigs, &mut self.vregs)
574            {
575                self.emit(insn);
576            }
577
578            // The `args` instruction below must come first. Finish
579            // the current "IR inst" (with a default source location,
580            // as for other special instructions inserted during
581            // lowering) and continue the scan backward.
582            self.finish_ir_inst(Default::default());
583
584            if let Some(insn) = self.vcode.vcode.abi.take_args() {
585                self.emit(insn);
586            }
587        }
588    }
589
590    /// Generate the return instruction.
591    pub fn gen_return(&mut self, rets: &[ValueRegs<Reg>]) {
592        let mut out_rets = vec![];
593
594        let mut rets = rets.into_iter();
595        for (i, ret) in self
596            .abi()
597            .signature()
598            .returns
599            .clone()
600            .into_iter()
601            .enumerate()
602        {
603            let regs = if ret.purpose == ArgumentPurpose::StructReturn {
604                self.sret_reg.unwrap()
605            } else {
606                *rets.next().unwrap()
607            };
608
609            let (regs, insns) = self.vcode.abi().gen_copy_regs_to_retval(
610                self.vcode.sigs(),
611                i,
612                regs,
613                &mut self.vregs,
614            );
615            out_rets.extend(regs);
616            for insn in insns {
617                self.emit(insn);
618            }
619        }
620
621        // Hack: generate a virtual instruction that uses vmctx in
622        // order to keep it alive for the duration of the function,
623        // for the benefit of debuginfo.
624        if self.f.dfg.values_labels.is_some() {
625            if let Some(vmctx_val) = self.f.special_param(ArgumentPurpose::VMContext) {
626                if self.value_ir_uses[vmctx_val] != ValueUseState::Unused {
627                    let vmctx_reg = self.value_regs[vmctx_val].only_reg().unwrap();
628                    self.emit(I::gen_dummy_use(vmctx_reg));
629                }
630            }
631        }
632
633        let inst = self.abi().gen_rets(out_rets);
634        self.emit(inst);
635    }
636
637    /// Generate list of registers to hold the output of a call with
638    /// signature `sig`.
639    pub fn gen_call_output(&mut self, sig: &Signature) -> InstOutput {
640        let mut rets = smallvec![];
641        for ty in sig.returns.iter().map(|ret| ret.value_type) {
642            rets.push(self.vregs.alloc_with_deferred_error(ty));
643        }
644        rets
645    }
646
647    /// Likewise, but for a `SigRef` instead.
648    pub fn gen_call_output_from_sig_ref(&mut self, sig_ref: SigRef) -> InstOutput {
649        self.gen_call_output(&self.f.dfg.signatures[sig_ref])
650    }
651
652    /// Set up arguments values `args` for a call with signature `sig`.
653    pub fn gen_call_args(&mut self, sig: Sig, args: &[ValueRegs<Reg>]) -> CallArgList {
654        let (uses, insts) = self.vcode.abi().gen_call_args(
655            self.vcode.sigs(),
656            sig,
657            args,
658            /* is_tail_call */ false,
659            &self.flags,
660            &mut self.vregs,
661        );
662        for insn in insts {
663            self.emit(insn);
664        }
665        uses
666    }
667
668    /// Likewise, but for a `return_call`.
669    pub fn gen_return_call_args(&mut self, sig: Sig, args: &[ValueRegs<Reg>]) -> CallArgList {
670        let (uses, insts) = self.vcode.abi().gen_call_args(
671            self.vcode.sigs(),
672            sig,
673            args,
674            /* is_tail_call */ true,
675            &self.flags,
676            &mut self.vregs,
677        );
678        for insn in insts {
679            self.emit(insn);
680        }
681        uses
682    }
683
684    /// Set up return values `outputs` for a call with signature `sig`.
685    pub fn gen_call_rets(&mut self, sig: Sig, outputs: &[ValueRegs<Reg>]) -> CallRetList {
686        self.vcode
687            .abi()
688            .gen_call_rets(self.vcode.sigs(), sig, outputs, None, &mut self.vregs)
689    }
690
691    /// Likewise, but for a `try_call`.
692    pub fn gen_try_call_rets(&mut self, sig: Sig) -> CallRetList {
693        let ir_inst = self.cur_inst.unwrap();
694        let mut outputs: SmallVec<[ValueRegs<Reg>; 2]> = smallvec![];
695        for return_def in self.try_call_rets.get(&ir_inst).unwrap() {
696            outputs.push(return_def.map(|r| r.to_reg()));
697        }
698        let payloads = Some(&self.try_call_payloads.get(&ir_inst).unwrap()[..]);
699
700        self.vcode
701            .abi()
702            .gen_call_rets(self.vcode.sigs(), sig, &outputs, payloads, &mut self.vregs)
703    }
704
705    /// Populate a `CallInfo` for a call with signature `sig`.
706    pub fn gen_call_info<T>(
707        &mut self,
708        sig: Sig,
709        dest: T,
710        uses: CallArgList,
711        defs: CallRetList,
712        try_call_info: Option<TryCallInfo>,
713    ) -> CallInfo<T> {
714        self.vcode
715            .abi()
716            .gen_call_info(self.vcode.sigs(), sig, dest, uses, defs, try_call_info)
717    }
718
719    /// Has this instruction been sunk to a use-site (i.e., away from its
720    /// original location)?
721    fn is_inst_sunk(&self, inst: Inst) -> bool {
722        self.inst_sunk.contains(&inst)
723    }
724
725    // Is any result of this instruction needed?
726    fn is_any_inst_result_needed(&self, inst: Inst) -> bool {
727        self.f
728            .dfg
729            .inst_results(inst)
730            .iter()
731            .any(|&result| self.value_lowered_uses[result] > 0)
732    }
733
734    fn lower_clif_block<B: LowerBackend<MInst = I>>(
735        &mut self,
736        backend: &B,
737        block: Block,
738        ctrl_plane: &mut ControlPlane,
739    ) -> CodegenResult<()> {
740        self.cur_scan_entry_color = Some(self.block_end_colors[block]);
741        // Lowering loop:
742        // - For each non-branch instruction, in reverse order:
743        //   - If side-effecting (load, store, branch/call/return,
744        //     possible trap), or if used outside of this block, or if
745        //     demanded by another inst, then lower.
746        //
747        // That's it! Lowering of side-effecting ops will force all *needed*
748        // (live) non-side-effecting ops to be lowered at the right places, via
749        // the `use_input_reg()` callback on the `Lower` (that's us). That's
750        // because `use_input_reg()` sets the eager/demand bit for any insts
751        // whose result registers are used.
752        //
753        // We set the VCodeBuilder to "backward" mode, so we emit
754        // blocks in reverse order wrt the BlockIndex sequence, and
755        // emit instructions in reverse order within blocks.  Because
756        // the machine backend calls `ctx.emit()` in forward order, we
757        // collect per-IR-inst lowered instructions in `ir_insts`,
758        // then reverse these and append to the VCode at the end of
759        // each IR instruction.
760        for inst in self.f.layout.block_insts(block).rev() {
761            let data = &self.f.dfg.insts[inst];
762            let has_side_effect = has_lowering_side_effect(self.f, inst);
763            // If  inst has been sunk to another location, skip it.
764            if self.is_inst_sunk(inst) {
765                continue;
766            }
767            // Are any outputs used at least once?
768            let value_needed = self.is_any_inst_result_needed(inst);
769            trace!(
770                "lower_clif_block: block {} inst {} ({:?}) is_branch {} side_effect {} value_needed {}",
771                block,
772                inst,
773                data,
774                data.opcode().is_branch(),
775                has_side_effect,
776                value_needed,
777            );
778
779            // Update scan state to color prior to this inst (as we are scanning
780            // backward).
781            self.cur_inst = Some(inst);
782            if has_side_effect {
783                let entry_color = *self
784                    .side_effect_inst_entry_colors
785                    .get(&inst)
786                    .expect("every side-effecting inst should have a color-map entry");
787                self.cur_scan_entry_color = Some(entry_color);
788            }
789
790            // Skip lowering branches; these are handled separately
791            // (see `lower_clif_branches()` below).
792            if self.f.dfg.insts[inst].opcode().is_branch() {
793                continue;
794            }
795
796            // Value defined by "inst" becomes live after it in normal
797            // order, and therefore **before** in reversed order.
798            self.emit_value_label_live_range_start_for_inst(inst);
799
800            // Normal instruction: codegen if the instruction is side-effecting
801            // or any of its outputs is used.
802            if has_side_effect || value_needed {
803                trace!("lowering: inst {}: {}", inst, self.f.dfg.display_inst(inst));
804                let temp_regs = match backend.lower(self, inst) {
805                    Some(regs) => regs,
806                    None => {
807                        let ty = if self.num_outputs(inst) > 0 {
808                            Some(self.output_ty(inst, 0))
809                        } else {
810                            None
811                        };
812                        return Err(CodegenError::Unsupported(format!(
813                            "should be implemented in ISLE: inst = `{}`, type = `{:?}`",
814                            self.f.dfg.display_inst(inst),
815                            ty
816                        )));
817                    }
818                };
819
820                // The ISLE generated code emits its own registers to define the
821                // instruction's lowered values in. However, other instructions
822                // that use this SSA value will be lowered assuming that the value
823                // is generated into a pre-assigned, different, register.
824                //
825                // To connect the two, we set up "aliases" in the VCodeBuilder
826                // that apply when it is building the Operand table for the
827                // regalloc to use. These aliases effectively rewrite any use of
828                // the pre-assigned register to the register that was returned by
829                // the ISLE lowering logic.
830                let results = self.f.dfg.inst_results(inst);
831                debug_assert_eq!(temp_regs.len(), results.len());
832                for (regs, &result) in temp_regs.iter().zip(results) {
833                    let dsts = self.value_regs[result];
834                    let mut regs = regs.regs().iter();
835                    for &dst in dsts.regs().iter() {
836                        let temp = regs.next().copied().unwrap_or(Reg::invalid_sentinel());
837                        trace!("set vreg alias: {result:?} = {dst:?}, lowering = {temp:?}");
838                        self.vregs.set_vreg_alias(dst, temp);
839                    }
840                }
841            }
842
843            let start = self.vcode.vcode.num_insts();
844            let loc = self.srcloc(inst);
845            self.finish_ir_inst(loc);
846
847            // If the instruction had a user stack map, forward it from the CLIF
848            // to the vcode.
849            if let Some(entries) = self.f.dfg.user_stack_map_entries(inst) {
850                let end = self.vcode.vcode.num_insts();
851                debug_assert!(end > start);
852                debug_assert_eq!(
853                    (start..end)
854                        .filter(|i| self.vcode.vcode[InsnIndex::new(*i)].is_safepoint())
855                        .count(),
856                    1
857                );
858                for i in start..end {
859                    let iix = InsnIndex::new(i);
860                    if self.vcode.vcode[iix].is_safepoint() {
861                        trace!(
862                            "Adding user stack map from clif\n\n\
863                                 {inst:?} `{}`\n\n\
864                             to vcode\n\n\
865                                 {iix:?} `{}`",
866                            self.f.dfg.display_inst(inst),
867                            &self.vcode.vcode[iix].pretty_print_inst(&mut Default::default()),
868                        );
869                        self.vcode
870                            .add_user_stack_map(BackwardsInsnIndex::new(iix.index()), entries);
871                        break;
872                    }
873                }
874            }
875
876            // If the CLIF instruction had debug tags, copy them to
877            // the VCode. Place on all VCode instructions lowered from
878            // this CLIF instruction.
879            let debug_tags = self.f.debug_tags.get(inst);
880            if !debug_tags.is_empty() && self.vcode.vcode.num_insts() > 0 {
881                let end = self.vcode.vcode.num_insts();
882                for i in start..end {
883                    let backwards_index = BackwardsInsnIndex::new(i);
884                    log::trace!(
885                        "debug tags on {inst}; associating {debug_tags:?} with {backwards_index:?}"
886                    );
887                    self.vcode.add_debug_tags(backwards_index, debug_tags);
888                }
889            }
890
891            // maybe insert random instruction
892            if ctrl_plane.get_decision() {
893                if ctrl_plane.get_decision() {
894                    let imm: u64 = ctrl_plane.get_arbitrary();
895                    let reg = self.alloc_tmp(crate::ir::types::I64).regs()[0];
896                    I::gen_imm_u64(imm, reg).map(|inst| self.emit(inst));
897                } else {
898                    let imm: f64 = ctrl_plane.get_arbitrary();
899                    let tmp = self.alloc_tmp(crate::ir::types::I64).regs()[0];
900                    let reg = self.alloc_tmp(crate::ir::types::F64).regs()[0];
901                    for inst in I::gen_imm_f64(imm, tmp, reg) {
902                        self.emit(inst);
903                    }
904                }
905            }
906        }
907
908        // Add the block params to this block.
909        self.add_block_params(block)?;
910
911        self.cur_scan_entry_color = None;
912        Ok(())
913    }
914
915    fn add_block_params(&mut self, block: Block) -> CodegenResult<()> {
916        for &param in self.f.dfg.block_params(block) {
917            for &reg in self.value_regs[param].regs() {
918                let vreg = reg.to_virtual_reg().unwrap();
919                self.vcode.add_block_param(vreg);
920            }
921        }
922        Ok(())
923    }
924
925    fn get_value_labels<'a>(&'a self, val: Value, depth: usize) -> Option<&'a [ValueLabelStart]> {
926        if let Some(ref values_labels) = self.f.dfg.values_labels {
927            debug_assert!(self.f.dfg.value_is_real(val));
928            trace!(
929                "get_value_labels: val {} -> {:?}",
930                val,
931                values_labels.get(&val)
932            );
933            match values_labels.get(&val) {
934                Some(&ValueLabelAssignments::Starts(ref list)) => Some(&list[..]),
935                Some(&ValueLabelAssignments::Alias { value, .. }) if depth < 10 => {
936                    self.get_value_labels(value, depth + 1)
937                }
938                _ => None,
939            }
940        } else {
941            None
942        }
943    }
944
945    fn emit_value_label_marks_for_value(&mut self, val: Value) {
946        let regs = self.value_regs[val];
947        if regs.len() > 1 {
948            return;
949        }
950        let reg = regs.only_reg().unwrap();
951
952        if let Some(label_starts) = self.get_value_labels(val, 0) {
953            let labels = label_starts
954                .iter()
955                .map(|&ValueLabelStart { label, .. }| label)
956                .collect::<FxHashSet<_>>();
957            for label in labels {
958                trace!(
959                    "value labeling: defines val {:?} -> reg {:?} -> label {:?}",
960                    val, reg, label,
961                );
962                self.vcode.add_value_label(reg, label);
963            }
964        }
965    }
966
967    fn emit_value_label_live_range_start_for_inst(&mut self, inst: Inst) {
968        if self.f.dfg.values_labels.is_none() {
969            return;
970        }
971
972        trace!(
973            "value labeling: srcloc {}: inst {}",
974            self.srcloc(inst),
975            inst
976        );
977        for &val in self.f.dfg.inst_results(inst) {
978            self.emit_value_label_marks_for_value(val);
979        }
980    }
981
982    fn emit_value_label_live_range_start_for_block_args(&mut self, block: Block) {
983        if self.f.dfg.values_labels.is_none() {
984            return;
985        }
986
987        trace!("value labeling: block {}", block);
988        for &arg in self.f.dfg.block_params(block) {
989            self.emit_value_label_marks_for_value(arg);
990        }
991        self.finish_ir_inst(Default::default());
992    }
993
994    fn finish_ir_inst(&mut self, loc: RelSourceLoc) {
995        // The VCodeBuilder builds in reverse order (and reverses at
996        // the end), but `ir_insts` is in forward order, so reverse
997        // it.
998        for inst in self.ir_insts.drain(..).rev() {
999            self.vcode.push(inst, loc);
1000        }
1001    }
1002
1003    fn finish_bb(&mut self) {
1004        self.vcode.end_bb();
1005    }
1006
1007    fn lower_clif_branch<B: LowerBackend<MInst = I>>(
1008        &mut self,
1009        backend: &B,
1010        // Lowered block index:
1011        bindex: BlockIndex,
1012        // Original CLIF block:
1013        block: Block,
1014        branch: Inst,
1015        targets: &[MachLabel],
1016    ) -> CodegenResult<()> {
1017        trace!(
1018            "lower_clif_branch: block {} branch {:?} targets {:?}",
1019            block, branch, targets,
1020        );
1021        // When considering code-motion opportunities, consider the current
1022        // program point to be this branch.
1023        self.cur_inst = Some(branch);
1024
1025        // Lower the branch in ISLE.
1026        backend
1027            .lower_branch(self, branch, targets)
1028            .unwrap_or_else(|| {
1029                panic!(
1030                    "should be implemented in ISLE: branch = `{}`",
1031                    self.f.dfg.display_inst(branch),
1032                )
1033            });
1034        let loc = self.srcloc(branch);
1035        self.finish_ir_inst(loc);
1036        // Add block param outputs for current block.
1037        self.lower_branch_blockparam_args(bindex);
1038        Ok(())
1039    }
1040
1041    fn lower_branch_blockparam_args(&mut self, block: BlockIndex) {
1042        let mut branch_arg_vregs: SmallVec<[Reg; 16]> = smallvec![];
1043
1044        // TODO: why not make `block_order` public?
1045        for succ_idx in 0..self.vcode.block_order().succ_indices(block).1.len() {
1046            branch_arg_vregs.clear();
1047            let (succ, args) = self.collect_block_call(block, succ_idx, &mut branch_arg_vregs);
1048            self.vcode.add_succ(succ, args);
1049        }
1050    }
1051
1052    fn collect_branch_and_targets(
1053        &self,
1054        bindex: BlockIndex,
1055        _bb: Block,
1056        targets: &mut SmallVec<[MachLabel; 2]>,
1057    ) -> Option<Inst> {
1058        targets.clear();
1059        let (opt_inst, succs) = self.vcode.block_order().succ_indices(bindex);
1060        targets.extend(succs.iter().map(|succ| MachLabel::from_block(*succ)));
1061        opt_inst
1062    }
1063
1064    /// Collect the outgoing block-call arguments for a given edge out
1065    /// of a lowered block.
1066    fn collect_block_call<'a>(
1067        &mut self,
1068        block: BlockIndex,
1069        succ_idx: usize,
1070        buffer: &'a mut SmallVec<[Reg; 16]>,
1071    ) -> (BlockIndex, &'a [Reg]) {
1072        let block_order = self.vcode.block_order();
1073        let (_, succs) = block_order.succ_indices(block);
1074        let succ = succs[succ_idx];
1075        let this_lb = block_order.lowered_order()[block.index()];
1076        let succ_lb = block_order.lowered_order()[succ.index()];
1077
1078        let (branch_inst, succ_idx) = match (this_lb, succ_lb) {
1079            (_, LoweredBlock::CriticalEdge { .. }) => {
1080                // The successor is a split-critical-edge block. In this
1081                // case, this block-call has no arguments, and the
1082                // arguments go on the critical edge block's unconditional
1083                // branch instead.
1084                return (succ, &[]);
1085            }
1086            (LoweredBlock::CriticalEdge { pred, succ_idx, .. }, _) => {
1087                // This is a split-critical-edge block. In this case, our
1088                // block-call has the arguments that in the CLIF appear in
1089                // the predecessor's branch to this edge.
1090                let branch_inst = self.f.layout.last_inst(pred).unwrap();
1091                (branch_inst, succ_idx as usize)
1092            }
1093
1094            (this, _) => {
1095                let block = this.orig_block().unwrap();
1096                // Ordinary block, with an ordinary block as
1097                // successor. Take the arguments from the branch.
1098                let branch_inst = self.f.layout.last_inst(block).unwrap();
1099                (branch_inst, succ_idx)
1100            }
1101        };
1102
1103        let block_call = self.f.dfg.insts[branch_inst]
1104            .branch_destination(&self.f.dfg.jump_tables, &self.f.dfg.exception_tables)[succ_idx];
1105        for arg in block_call.args(&self.f.dfg.value_lists) {
1106            match arg {
1107                BlockArg::Value(arg) => {
1108                    debug_assert!(self.f.dfg.value_is_real(arg));
1109                    let regs = self.put_value_in_regs(arg);
1110                    buffer.extend_from_slice(regs.regs());
1111                }
1112                BlockArg::TryCallRet(i) => {
1113                    let regs = self.try_call_rets.get(&branch_inst).unwrap()[i as usize]
1114                        .map(|r| r.to_reg());
1115                    buffer.extend_from_slice(regs.regs());
1116                }
1117                BlockArg::TryCallExn(i) => {
1118                    let reg =
1119                        self.try_call_payloads.get(&branch_inst).unwrap()[i as usize].to_reg();
1120                    buffer.push(reg);
1121                }
1122            }
1123        }
1124        (succ, &buffer[..])
1125    }
1126
1127    /// Lower the function.
1128    pub fn lower<B: LowerBackend<MInst = I>>(
1129        mut self,
1130        backend: &B,
1131        ctrl_plane: &mut ControlPlane,
1132    ) -> CodegenResult<VCode<I>> {
1133        trace!("about to lower function: {:?}", self.f);
1134
1135        self.vcode.init_retval_area(&mut self.vregs)?;
1136
1137        // Get the pinned reg here (we only parameterize this function on `B`,
1138        // not the whole `Lower` impl).
1139        self.pinned_reg = backend.maybe_pinned_reg();
1140
1141        self.vcode.set_entry(BlockIndex::new(0));
1142
1143        // Reused vectors for branch lowering.
1144        let mut targets: SmallVec<[MachLabel; 2]> = SmallVec::new();
1145
1146        // get a copy of the lowered order; we hold this separately because we
1147        // need a mut ref to the vcode to mutate it below.
1148        let lowered_order: SmallVec<[LoweredBlock; 64]> = self
1149            .vcode
1150            .block_order()
1151            .lowered_order()
1152            .iter()
1153            .cloned()
1154            .collect();
1155
1156        // Main lowering loop over lowered blocks.
1157        for (bindex, lb) in lowered_order.iter().enumerate().rev() {
1158            let bindex = BlockIndex::new(bindex);
1159
1160            // Lower the block body in reverse order (see comment in
1161            // `lower_clif_block()` for rationale).
1162
1163            // End branch.
1164            if let Some(bb) = lb.orig_block() {
1165                if let Some(branch) = self.collect_branch_and_targets(bindex, bb, &mut targets) {
1166                    self.lower_clif_branch(backend, bindex, bb, branch, &targets)?;
1167                    self.finish_ir_inst(self.srcloc(branch));
1168                }
1169            } else {
1170                // If no orig block, this must be a pure edge block;
1171                // get the successor and emit a jump. This block has
1172                // no block params; and this jump's block-call args
1173                // will be filled in by
1174                // `lower_branch_blockparam_args`.
1175                let succ = self.vcode.block_order().succ_indices(bindex).1[0];
1176                self.emit(I::gen_jump(MachLabel::from_block(succ)));
1177                self.finish_ir_inst(Default::default());
1178                self.lower_branch_blockparam_args(bindex);
1179            }
1180
1181            // Original block body.
1182            if let Some(bb) = lb.orig_block() {
1183                self.lower_clif_block(backend, bb, ctrl_plane)?;
1184                self.emit_value_label_live_range_start_for_block_args(bb);
1185            }
1186
1187            if bindex.index() == 0 {
1188                // Set up the function with arg vreg inits.
1189                self.gen_arg_setup();
1190                self.finish_ir_inst(Default::default());
1191            }
1192
1193            self.finish_bb();
1194
1195            // Check for any deferred vreg-temp allocation errors, and
1196            // bubble one up at this time if it exists.
1197            if let Some(e) = self.vregs.take_deferred_error() {
1198                return Err(e);
1199            }
1200        }
1201
1202        // Now that we've emitted all instructions into the
1203        // VCodeBuilder, let's build the VCode.
1204        trace!(
1205            "built vcode:\n{:?}Backwards {:?}",
1206            &self.vregs, &self.vcode.vcode
1207        );
1208        let vcode = self.vcode.build(self.vregs);
1209
1210        Ok(vcode)
1211    }
1212
1213    pub fn value_is_unused(&self, val: Value) -> bool {
1214        match self.value_ir_uses[val] {
1215            ValueUseState::Unused => true,
1216            _ => false,
1217        }
1218    }
1219
1220    pub fn block_successor_label(&self, block: Block, succ: usize) -> MachLabel {
1221        trace!("block_successor_label: block {block} succ {succ}");
1222        let lowered = self
1223            .vcode
1224            .block_order()
1225            .lowered_index_for_block(block)
1226            .expect("Unreachable block");
1227        trace!(" -> lowered block {lowered:?}");
1228        let (_, succs) = self.vcode.block_order().succ_indices(lowered);
1229        trace!(" -> succs {succs:?}");
1230        let succ_block = *succs.get(succ).expect("Successor index out of range");
1231        MachLabel::from_block(succ_block)
1232    }
1233}
1234
1235/// Pre-analysis: compute `value_ir_uses`. See comment on
1236/// `ValueUseState` for a description of what this analysis
1237/// computes.
1238fn compute_use_states(
1239    f: &Function,
1240    sret_param: Option<Value>,
1241) -> SecondaryMap<Value, ValueUseState> {
1242    // We perform the analysis without recursion, so we don't
1243    // overflow the stack on long chains of ops in the input.
1244    //
1245    // This is sort of a hybrid of a "shallow use-count" pass and
1246    // a DFS. We iterate over all instructions and mark their args
1247    // as used. However when we increment a use-count to
1248    // "Multiple" we push its args onto the stack and do a DFS,
1249    // immediately marking the whole dependency tree as
1250    // Multiple. Doing both (shallow use-counting over all insts,
1251    // and deep Multiple propagation) lets us trim both
1252    // traversals, stopping recursion when a node is already at
1253    // the appropriate state.
1254    //
1255    // In particular, note that the *coarsening* into {Unused,
1256    // Once, Multiple} is part of what makes this pass more
1257    // efficient than a full indirect-use-counting pass.
1258
1259    let mut value_ir_uses = SecondaryMap::with_default(ValueUseState::Unused);
1260
1261    if let Some(sret_param) = sret_param {
1262        // There's an implicit use of the struct-return parameter in each
1263        // copy of the function epilogue, which we count here.
1264        value_ir_uses[sret_param] = ValueUseState::Multiple;
1265    }
1266
1267    // Stack of iterators over Values as we do DFS to mark
1268    // Multiple-state subtrees. The iterator type is whatever is
1269    // returned by `uses` below.
1270    let mut stack: SmallVec<[_; 16]> = smallvec![];
1271
1272    // Find the args for the inst corresponding to the given value.
1273    //
1274    // Note that "root" instructions are skipped here. This means that multiple
1275    // uses of any result of a multi-result instruction are not considered
1276    // multiple uses of the operands of a multi-result instruction. This
1277    // requires tight coupling with `get_value_as_source_or_const` above which
1278    // is the consumer of the map that this function is producing.
1279    let uses = |value| {
1280        trace!(" -> pushing args for {} onto stack", value);
1281        if let ValueDef::Result(src_inst, _) = f.dfg.value_def(value) {
1282            if is_value_use_root(f, src_inst) {
1283                None
1284            } else {
1285                Some(f.dfg.inst_values(src_inst))
1286            }
1287        } else {
1288            None
1289        }
1290    };
1291
1292    // Do a DFS through `value_ir_uses` to mark a subtree as
1293    // Multiple.
1294    for inst in f
1295        .layout
1296        .blocks()
1297        .flat_map(|block| f.layout.block_insts(block))
1298    {
1299        // Iterate over all values used by all instructions, noting an
1300        // additional use on each operand.
1301        for arg in f.dfg.inst_values(inst) {
1302            debug_assert!(f.dfg.value_is_real(arg));
1303            let old = value_ir_uses[arg];
1304            value_ir_uses[arg].inc();
1305            let new = value_ir_uses[arg];
1306            trace!("arg {} used, old state {:?}, new {:?}", arg, old, new);
1307
1308            // On transition to Multiple, do DFS.
1309            if old == ValueUseState::Multiple || new != ValueUseState::Multiple {
1310                continue;
1311            }
1312            if let Some(iter) = uses(arg) {
1313                stack.push(iter);
1314            }
1315            while let Some(iter) = stack.last_mut() {
1316                if let Some(value) = iter.next() {
1317                    debug_assert!(f.dfg.value_is_real(value));
1318                    trace!(" -> DFS reaches {}", value);
1319                    if value_ir_uses[value] == ValueUseState::Multiple {
1320                        // Truncate DFS here: no need to go further,
1321                        // as whole subtree must already be Multiple.
1322                        // With debug asserts, check one level of
1323                        // that invariant at least.
1324                        debug_assert!(uses(value).into_iter().flatten().all(|arg| {
1325                            debug_assert!(f.dfg.value_is_real(arg));
1326                            value_ir_uses[arg] == ValueUseState::Multiple
1327                        }));
1328                        continue;
1329                    }
1330                    value_ir_uses[value] = ValueUseState::Multiple;
1331                    trace!(" -> became Multiple");
1332                    if let Some(iter) = uses(value) {
1333                        stack.push(iter);
1334                    }
1335                } else {
1336                    // Empty iterator, discard.
1337                    stack.pop();
1338                }
1339            }
1340        }
1341    }
1342
1343    value_ir_uses
1344}
1345
1346/// Definition of a "root" instruction for the calculation of `ValueUseState`.
1347///
1348/// This function calculates whether `inst` is considered a "root" for value-use
1349/// information. This concept is used to forcibly prevent looking-through the
1350/// instruction during `get_value_as_source_or_const` as it additionally
1351/// prevents propagating `Multiple`-used results of the `inst` here to the
1352/// operands of the instruction.
1353///
1354/// Currently this is defined as multi-result instructions. That means that
1355/// lowerings are never allowed to look through a multi-result instruction to
1356/// generate patterns. Note that this isn't possible in ISLE today anyway so
1357/// this isn't currently much of a loss.
1358///
1359/// The main purpose of this function is to prevent the operands of a
1360/// multi-result instruction from being forcibly considered `Multiple`-used
1361/// regardless of circumstances.
1362fn is_value_use_root(f: &Function, inst: Inst) -> bool {
1363    f.dfg.inst_results(inst).len() > 1
1364}
1365
1366/// Function-level queries.
1367impl<'func, I: VCodeInst> Lower<'func, I> {
1368    pub fn dfg(&self) -> &DataFlowGraph {
1369        &self.f.dfg
1370    }
1371
1372    /// Get the `Callee`.
1373    pub fn abi(&self) -> &Callee<I::ABIMachineSpec> {
1374        self.vcode.abi()
1375    }
1376
1377    /// Get the `Callee`.
1378    pub fn abi_mut(&mut self) -> &mut Callee<I::ABIMachineSpec> {
1379        self.vcode.abi_mut()
1380    }
1381}
1382
1383/// Instruction input/output queries.
1384impl<'func, I: VCodeInst> Lower<'func, I> {
1385    /// Get the instdata for a given IR instruction.
1386    pub fn data(&self, ir_inst: Inst) -> &InstructionData {
1387        &self.f.dfg.insts[ir_inst]
1388    }
1389
1390    /// Likewise, but starting with a GlobalValue identifier.
1391    pub fn symbol_value_data<'b>(
1392        &'b self,
1393        global_value: GlobalValue,
1394    ) -> Option<(&'b ExternalName, RelocDistance, i64)> {
1395        let gvdata = &self.f.global_values[global_value];
1396        match gvdata {
1397            &GlobalValueData::Symbol {
1398                ref name,
1399                ref offset,
1400                colocated,
1401                ..
1402            } => {
1403                let offset = offset.bits();
1404                let dist = if colocated {
1405                    RelocDistance::Near
1406                } else {
1407                    RelocDistance::Far
1408                };
1409                Some((name, dist, offset))
1410            }
1411            _ => None,
1412        }
1413    }
1414
1415    /// Returns the memory flags of a given memory access.
1416    pub fn memflags(&self, ir_inst: Inst) -> Option<MemFlags> {
1417        match &self.f.dfg.insts[ir_inst] {
1418            &InstructionData::AtomicCas { flags, .. } => Some(flags),
1419            &InstructionData::AtomicRmw { flags, .. } => Some(flags),
1420            &InstructionData::Load { flags, .. }
1421            | &InstructionData::LoadNoOffset { flags, .. }
1422            | &InstructionData::Store { flags, .. } => Some(flags),
1423            &InstructionData::StoreNoOffset { flags, .. } => Some(flags),
1424            _ => None,
1425        }
1426    }
1427
1428    /// Get the source location for a given instruction.
1429    pub fn srcloc(&self, ir_inst: Inst) -> RelSourceLoc {
1430        self.f.rel_srclocs()[ir_inst]
1431    }
1432
1433    /// Get the number of inputs to the given IR instruction. This is a count only of the Value
1434    /// arguments to the instruction: block arguments will not be included in this count.
1435    pub fn num_inputs(&self, ir_inst: Inst) -> usize {
1436        self.f.dfg.inst_args(ir_inst).len()
1437    }
1438
1439    /// Get the number of outputs to the given IR instruction.
1440    pub fn num_outputs(&self, ir_inst: Inst) -> usize {
1441        self.f.dfg.inst_results(ir_inst).len()
1442    }
1443
1444    /// Get the type for an instruction's input.
1445    pub fn input_ty(&self, ir_inst: Inst, idx: usize) -> Type {
1446        self.value_ty(self.input_as_value(ir_inst, idx))
1447    }
1448
1449    /// Get the type for a value.
1450    pub fn value_ty(&self, val: Value) -> Type {
1451        self.f.dfg.value_type(val)
1452    }
1453
1454    /// Get the type for an instruction's output.
1455    pub fn output_ty(&self, ir_inst: Inst, idx: usize) -> Type {
1456        self.f.dfg.value_type(self.f.dfg.inst_results(ir_inst)[idx])
1457    }
1458
1459    /// Get the value of a constant instruction (`iconst`, etc.) as a 64-bit
1460    /// value, if possible.
1461    pub fn get_constant(&self, ir_inst: Inst) -> Option<u64> {
1462        self.inst_constants.get(&ir_inst).map(|&c| {
1463            // The upper bits must be zero, enforced during legalization and by
1464            // the CLIF verifier.
1465            debug_assert_eq!(c, {
1466                let input_size = self.output_ty(ir_inst, 0).bits() as u64;
1467                let shift = 64 - input_size;
1468                (c << shift) >> shift
1469            });
1470            c
1471        })
1472    }
1473
1474    /// Get the input as one of two options other than a direct register:
1475    ///
1476    /// - An instruction, given that it is effect-free or able to sink its
1477    ///   effect to the current instruction being lowered, and given it has only
1478    ///   one output, and if effect-ful, given that this is the only use;
1479    /// - A constant, if the value is a constant.
1480    ///
1481    /// The instruction input may be available in either of these forms.  It may
1482    /// be available in neither form, if the conditions are not met; if so, use
1483    /// `put_input_in_regs()` instead to get it in a register.
1484    ///
1485    /// If the backend merges the effect of a side-effecting instruction, it
1486    /// must call `sink_inst()`. When this is called, it indicates that the
1487    /// effect has been sunk to the current scan location. The sunk
1488    /// instruction's result(s) must have *no* uses remaining, because it will
1489    /// not be codegen'd (it has been integrated into the current instruction).
1490    pub fn input_as_value(&self, ir_inst: Inst, idx: usize) -> Value {
1491        let val = self.f.dfg.inst_args(ir_inst)[idx];
1492        debug_assert!(self.f.dfg.value_is_real(val));
1493        val
1494    }
1495
1496    /// Resolves a particular input of an instruction to the `Value` that it is
1497    /// represented with.
1498    ///
1499    /// For more information see [`Lower::get_value_as_source_or_const`].
1500    pub fn get_input_as_source_or_const(&self, ir_inst: Inst, idx: usize) -> NonRegInput {
1501        let val = self.input_as_value(ir_inst, idx);
1502        self.get_value_as_source_or_const(val)
1503    }
1504
1505    /// Resolves a `Value` definition to the source instruction it came from
1506    /// plus whether it's a unique-use of that instruction.
1507    ///
1508    /// This function is the workhorse of pattern-matching in ISLE which enables
1509    /// combining multiple instructions together. This is used implicitly in
1510    /// patterns such as `(iadd x (iconst y))` where this function is used to
1511    /// extract the `(iconst y)` operand.
1512    ///
1513    /// At its core this function is a wrapper around
1514    /// [`DataFlowGraph::value_def`]. This function applies a filter on top of
1515    /// that, however, to determine when it is actually safe to "look through"
1516    /// the `val` definition here and view the underlying instruction. This
1517    /// protects against duplicating side effects, such as loads, for example.
1518    ///
1519    /// Internally this uses the data computed from `compute_use_states` along
1520    /// with other instruction properties to know what to return.
1521    pub fn get_value_as_source_or_const(&self, val: Value) -> NonRegInput {
1522        trace!(
1523            "get_input_for_val: val {} at cur_inst {:?} cur_scan_entry_color {:?}",
1524            val, self.cur_inst, self.cur_scan_entry_color,
1525        );
1526        let inst = match self.f.dfg.value_def(val) {
1527            // OK to merge source instruction if we have a source
1528            // instruction, and one of these two conditions hold:
1529            //
1530            // - It has no side-effects and this instruction is not a "value-use
1531            //   root" instruction. Instructions which are considered "roots"
1532            //   for value-use calculations do not have accurate information
1533            //   known about the `ValueUseState` of their operands. This is
1534            //   currently done for multi-result instructions to prevent a use
1535            //   of each result from forcing all operands of the multi-result
1536            //   instruction to also be `Multiple`. This in turn means that the
1537            //   `ValueUseState` for operands of a "root" instruction to be a
1538            //   lie if pattern matching were to look through the multi-result
1539            //   instruction. As a result the "look through this instruction"
1540            //   logic only succeeds if it's not a root instruction.
1541            //
1542            // - It has a side-effect, has one output value, that one
1543            //   output has only one use, directly or indirectly (so
1544            //   cannot be duplicated -- see comment on
1545            //   `ValueUseState`), and the instruction's color is *one
1546            //   less than* the current scan color.
1547            //
1548            //   This latter set of conditions is testing whether a
1549            //   side-effecting instruction can sink to the current scan
1550            //   location; this is possible if the in-color of this inst is
1551            //   equal to the out-color of the producing inst, so no other
1552            //   side-effecting ops occur between them (which will only be true
1553            //   if they are in the same BB, because color increments at each BB
1554            //   start).
1555            //
1556            //   If it is actually sunk, then in `merge_inst()`, we update the
1557            //   scan color so that as we scan over the range past which the
1558            //   instruction was sunk, we allow other instructions (that came
1559            //   prior to the sunk instruction) to sink.
1560            ValueDef::Result(src_inst, result_idx) => {
1561                let src_side_effect = has_lowering_side_effect(self.f, src_inst);
1562                trace!(" -> src inst {}", self.f.dfg.display_inst(src_inst));
1563                trace!(" -> has lowering side effect: {}", src_side_effect);
1564                if is_value_use_root(self.f, src_inst) {
1565                    // If this instruction is a "root instruction" then it's
1566                    // required that we can't look through it to see the
1567                    // definition. This means that the `ValueUseState` for the
1568                    // operands of this result assume that this instruction is
1569                    // generated exactly once which might get violated were we
1570                    // to allow looking through it.
1571                    trace!(" -> is a root instruction");
1572                    InputSourceInst::None
1573                } else if !src_side_effect {
1574                    // Otherwise if this instruction has no side effects and the
1575                    // value is used only once then we can look through it with
1576                    // a "unique" tag. A non-unique `Use` can be shown for other
1577                    // values ensuring consumers know how it's computed but that
1578                    // it's not available to omit.
1579                    if self.value_ir_uses[val] == ValueUseState::Once {
1580                        InputSourceInst::UniqueUse(src_inst, result_idx)
1581                    } else {
1582                        InputSourceInst::Use(src_inst, result_idx)
1583                    }
1584                } else {
1585                    // Side-effect: test whether this is the only use of the
1586                    // only result of the instruction, and whether colors allow
1587                    // the code-motion.
1588                    trace!(
1589                        " -> side-effecting op {} for val {}: use state {:?}",
1590                        src_inst, val, self.value_ir_uses[val]
1591                    );
1592                    if self.cur_scan_entry_color.is_some()
1593                        && self.value_ir_uses[val] == ValueUseState::Once
1594                        && self.num_outputs(src_inst) == 1
1595                        && self
1596                            .side_effect_inst_entry_colors
1597                            .get(&src_inst)
1598                            .unwrap()
1599                            .get()
1600                            + 1
1601                            == self.cur_scan_entry_color.unwrap().get()
1602                    {
1603                        InputSourceInst::UniqueUse(src_inst, 0)
1604                    } else {
1605                        InputSourceInst::None
1606                    }
1607                }
1608            }
1609            _ => InputSourceInst::None,
1610        };
1611        let constant = inst.as_inst().and_then(|(inst, _)| self.get_constant(inst));
1612
1613        NonRegInput { inst, constant }
1614    }
1615
1616    /// Increment the reference count for the Value, ensuring that it gets lowered.
1617    pub fn increment_lowered_uses(&mut self, val: Value) {
1618        self.value_lowered_uses[val] += 1
1619    }
1620
1621    /// Put the `idx`th input into register(s) and return the assigned register.
1622    pub fn put_input_in_regs(&mut self, ir_inst: Inst, idx: usize) -> ValueRegs<Reg> {
1623        let val = self.f.dfg.inst_args(ir_inst)[idx];
1624        self.put_value_in_regs(val)
1625    }
1626
1627    /// Put the given value into register(s) and return the assigned register.
1628    pub fn put_value_in_regs(&mut self, val: Value) -> ValueRegs<Reg> {
1629        debug_assert!(self.f.dfg.value_is_real(val));
1630        trace!("put_value_in_regs: val {}", val);
1631
1632        if let Some(inst) = self.f.dfg.value_def(val).inst() {
1633            assert!(!self.inst_sunk.contains(&inst));
1634        }
1635
1636        let regs = self.value_regs[val];
1637        trace!(" -> regs {:?}", regs);
1638        assert!(regs.is_valid());
1639
1640        self.value_lowered_uses[val] += 1;
1641
1642        regs
1643    }
1644
1645    /// Get the ValueRegs for the edge-defined values for special
1646    /// try-call-return block arguments.
1647    pub fn try_call_return_defs(&mut self, ir_inst: Inst) -> &[ValueRegs<Writable<Reg>>] {
1648        &self.try_call_rets.get(&ir_inst).unwrap()[..]
1649    }
1650
1651    /// Get the Regs for the edge-defined values for special
1652    /// try-call-return exception payload arguments.
1653    pub fn try_call_exception_defs(&mut self, ir_inst: Inst) -> &[Writable<Reg>] {
1654        &self.try_call_payloads.get(&ir_inst).unwrap()[..]
1655    }
1656}
1657
1658/// Codegen primitives: allocate temps, emit instructions, set result registers,
1659/// ask for an input to be gen'd into a register.
1660impl<'func, I: VCodeInst> Lower<'func, I> {
1661    /// Get a new temp.
1662    pub fn alloc_tmp(&mut self, ty: Type) -> ValueRegs<Writable<Reg>> {
1663        writable_value_regs(self.vregs.alloc_with_deferred_error(ty))
1664    }
1665
1666    /// Get the current root instruction that we are lowering.
1667    pub fn cur_inst(&self) -> Inst {
1668        self.cur_inst.unwrap()
1669    }
1670
1671    /// Emit a machine instruction.
1672    pub fn emit(&mut self, mach_inst: I) {
1673        trace!("emit: {:?}", mach_inst);
1674        self.ir_insts.push(mach_inst);
1675    }
1676
1677    /// Indicate that the side-effect of an instruction has been sunk to the
1678    /// current scan location. This should only be done with the instruction's
1679    /// original results are not used (i.e., `put_input_in_regs` is not invoked
1680    /// for the input produced by the sunk instruction), otherwise the
1681    /// side-effect will occur twice.
1682    pub fn sink_inst(&mut self, ir_inst: Inst) {
1683        assert!(has_lowering_side_effect(self.f, ir_inst));
1684        assert!(self.cur_scan_entry_color.is_some());
1685
1686        for result in self.dfg().inst_results(ir_inst) {
1687            assert!(self.value_lowered_uses[*result] == 0);
1688        }
1689
1690        let sunk_inst_entry_color = self
1691            .side_effect_inst_entry_colors
1692            .get(&ir_inst)
1693            .cloned()
1694            .unwrap();
1695        let sunk_inst_exit_color = InstColor::new(sunk_inst_entry_color.get() + 1);
1696        assert!(sunk_inst_exit_color == self.cur_scan_entry_color.unwrap());
1697        self.cur_scan_entry_color = Some(sunk_inst_entry_color);
1698        self.inst_sunk.insert(ir_inst);
1699    }
1700
1701    /// Retrieve immediate data given a handle.
1702    pub fn get_immediate_data(&self, imm: Immediate) -> &ConstantData {
1703        self.f.dfg.immediates.get(imm).unwrap()
1704    }
1705
1706    /// Retrieve constant data given a handle.
1707    pub fn get_constant_data(&self, constant_handle: Constant) -> &ConstantData {
1708        self.f.dfg.constants.get(constant_handle)
1709    }
1710
1711    /// Indicate that a constant should be emitted.
1712    pub fn use_constant(&mut self, constant: VCodeConstantData) -> VCodeConstant {
1713        self.vcode.constants().insert(constant)
1714    }
1715
1716    /// Cause the value in `reg` to be in a virtual reg, by copying it into a
1717    /// new virtual reg if `reg` is a real reg. `ty` describes the type of the
1718    /// value in `reg`.
1719    pub fn ensure_in_vreg(&mut self, reg: Reg, ty: Type) -> Reg {
1720        if reg.to_virtual_reg().is_some() {
1721            reg
1722        } else {
1723            let new_reg = self.alloc_tmp(ty).only_reg().unwrap();
1724            self.emit(I::gen_move(new_reg, reg, ty));
1725            new_reg.to_reg()
1726        }
1727    }
1728
1729    /// Add a range fact to a register, if no other fact is present.
1730    pub fn add_range_fact(&mut self, reg: Reg, bit_width: u16, min: u64, max: u64) {
1731        if self.flags.enable_pcc() {
1732            self.vregs.set_fact_if_missing(
1733                reg.to_virtual_reg().unwrap(),
1734                Fact::Range {
1735                    bit_width,
1736                    min,
1737                    max,
1738                },
1739            );
1740        }
1741    }
1742}
1743
1744#[cfg(test)]
1745mod tests {
1746    use super::ValueUseState;
1747    use crate::cursor::{Cursor, FuncCursor};
1748    use crate::ir::types;
1749    use crate::ir::{Function, InstBuilder};
1750
1751    #[test]
1752    fn multi_result_use_once() {
1753        let mut func = Function::new();
1754        let block0 = func.dfg.make_block();
1755        let mut pos = FuncCursor::new(&mut func);
1756        pos.insert_block(block0);
1757        let v1 = pos.ins().iconst(types::I64, 0);
1758        let v2 = pos.ins().iconst(types::I64, 1);
1759        let v3 = pos.ins().iconcat(v1, v2);
1760        let (v4, v5) = pos.ins().isplit(v3);
1761        pos.ins().return_(&[v4, v5]);
1762        let func = pos.func;
1763
1764        let uses = super::compute_use_states(&func, None);
1765        assert_eq!(uses[v1], ValueUseState::Once);
1766        assert_eq!(uses[v2], ValueUseState::Once);
1767        assert_eq!(uses[v3], ValueUseState::Once);
1768        assert_eq!(uses[v4], ValueUseState::Once);
1769        assert_eq!(uses[v5], ValueUseState::Once);
1770    }
1771
1772    #[test]
1773    fn results_used_twice_but_not_operands() {
1774        let mut func = Function::new();
1775        let block0 = func.dfg.make_block();
1776        let mut pos = FuncCursor::new(&mut func);
1777        pos.insert_block(block0);
1778        let v1 = pos.ins().iconst(types::I64, 0);
1779        let v2 = pos.ins().iconst(types::I64, 1);
1780        let v3 = pos.ins().iconcat(v1, v2);
1781        let (v4, v5) = pos.ins().isplit(v3);
1782        pos.ins().return_(&[v4, v4]);
1783        let func = pos.func;
1784
1785        let uses = super::compute_use_states(&func, None);
1786        assert_eq!(uses[v1], ValueUseState::Once);
1787        assert_eq!(uses[v2], ValueUseState::Once);
1788        assert_eq!(uses[v3], ValueUseState::Once);
1789        assert_eq!(uses[v4], ValueUseState::Multiple);
1790        assert_eq!(uses[v5], ValueUseState::Unused);
1791    }
1792}