/*

 * This file was initially derived from the files

 * `js/src/jit/BacktrackingAllocator.h` and

 * `js/src/jit/BacktrackingAllocator.cpp` in Mozilla Firefox, and was

 * originally licensed under the Mozilla Public License 2.0. We

 * subsequently relicensed it to Apache-2.0 WITH LLVM-exception (see

 * https://github.com/bytecodealliance/regalloc2/issues/7).

 *

 * Since the initial port, the design has been substantially evolved

 * and optimized.

 */

//! Live-range computation.

use super::{

    CodeRange, Env, LiveRangeFlag, LiveRangeIndex, LiveRangeKey, LiveRangeList, LiveRangeListEntry,

    LiveRangeSet, PRegData, PRegIndex, RegClass, Use, VRegData, VRegIndex,

};

use crate::indexset::IndexSet;

use crate::ion::data_structures::{

    BlockparamIn, BlockparamOut, FixedRegFixupLevel, MultiFixedRegFixup,

};

use crate::{

    Allocation, Block, Function, Inst, InstPosition, Operand, OperandConstraint, OperandKind,

    OperandPos, PReg, ProgPoint, RegAllocError, VReg, VecExt,

};

use core::convert::TryFrom;

use core::usize;

use smallvec::{smallvec, SmallVec};

/// A spill weight computed for a certain Use.

#[derive(Clone, Copy, Debug)]

pub struct SpillWeight(f32);

#[inline(always)]

pub fn spill_weight_from_constraint(

    constraint: OperandConstraint,

    loop_depth: usize,

    is_def: bool,

) -> SpillWeight {

    // A bonus of 1000 for one loop level, 4000 for two loop levels,

    // 16000 for three loop levels, etc. Avoids exponentiation.

    let loop_depth = core::cmp::min(10, loop_depth);

    let hot_bonus: f32 = (0..loop_depth).fold(1000.0, |a, _| a * 4.0);

    let def_bonus: f32 = if is_def { 2000.0 } else { 0.0 };

    let constraint_bonus: f32 = match constraint {

        OperandConstraint::Any => 1000.0,

        OperandConstraint::Reg | OperandConstraint::FixedReg(_) => 2000.0,

        _ => 0.0,

    };

    SpillWeight(hot_bonus + def_bonus + constraint_bonus)

}

impl SpillWeight {

    /// Convert a floating-point weight to a u16 that can be compactly

    /// stored in a `Use`. We simply take the top 16 bits of the f32; this

    /// is equivalent to the bfloat16 format

    /// (https://en.wikipedia.org/wiki/Bfloat16_floating-point_format).

    pub fn to_bits(self) -> u16 {

        (self.0.to_bits() >> 15) as u16

    }

    /// Convert a value that was returned from

    /// `SpillWeight::to_bits()` back into a `SpillWeight`. Note that

    /// some precision may be lost when round-tripping from a spill

    /// weight to packed bits and back.

    pub fn from_bits(bits: u16) -> SpillWeight {

        let x = f32::from_bits((bits as u32) << 15);

        SpillWeight(x)

    }

    /// Get a zero spill weight.

    pub fn zero() -> SpillWeight {

        SpillWeight(0.0)

    }

    /// Convert to a raw floating-point value.

    pub fn to_f32(self) -> f32 {

        self.0

    }

    /// Create a `SpillWeight` from a raw floating-point value.

    pub fn from_f32(x: f32) -> SpillWeight {

        SpillWeight(x)

    }

    pub fn to_int(self) -> u32 {

        self.0 as u32

    }

}

impl core::ops::Add<SpillWeight> for SpillWeight {

    type Output = SpillWeight;

    fn add(self, other: SpillWeight) -> Self {

        SpillWeight(self.0 + other.0)

    }

}

fn slot_idx(i: usize) -> Result<u16, RegAllocError> {

    u16::try_from(i).map_err(|_| RegAllocError::TooManyOperands)

}

impl<'a, F: Function> Env<'a, F> {

    pub fn create_pregs_and_vregs(&mut self) {

        // Create PRegs from the env.

        self.pregs.resize(

            PReg::NUM_INDEX,

            PRegData {

                allocations: LiveRangeSet::new(),

                is_stack: false,

            },

        );

        for &preg in &self.env.fixed_stack_slots {

            self.pregs[preg.index()].is_stack = true;

        }

        for class in 0..self.preferred_victim_by_class.len() {

            self.preferred_victim_by_class[class] = self.env.non_preferred_regs_by_class[class]

                .max_preg()

                .or(self.env.preferred_regs_by_class[class].max_preg())

                .unwrap_or(PReg::invalid());

        }

        // Create VRegs from the vreg count.

        for idx in 0..self.func.num_vregs() {

            // We'll fill in the real details when we see the def.

            self.ctx.vregs.add(

                VReg::new(idx, RegClass::Int),

                VRegData {

                    ranges: LiveRangeList::new_in(self.ctx.bump()),

                    blockparam: Block::invalid(),

                    // We'll learn the RegClass as we scan the code.

                    class: None,

                },

            );

        }

        // Create allocations too.

        for inst in 0..self.func.num_insts() {

            let start = self.output.allocs.len() as u32;

            self.output.inst_alloc_offsets.push(start);

            for _ in 0..self.func.inst_operands(Inst::new(inst)).len() {

                self.output.allocs.push(Allocation::none());

            }

        }

    }

    /// Mark `range` as live for the given `vreg`.

    ///

    /// Returns the liverange that contains the given range.

    pub fn add_liverange_to_vreg(

        &mut self,

        vreg: VRegIndex,

        mut range: CodeRange,

    ) -> LiveRangeIndex {

        trace!("add_liverange_to_vreg: vreg {:?} range {:?}", vreg, range);

        // Invariant: as we are building liveness information, we

        // *always* process instructions bottom-to-top, and as a

        // consequence, new liveranges are always created before any

        // existing liveranges for a given vreg. We assert this here,

        // then use it to avoid an O(n) merge step (which would lead

        // to O(n^2) liveness construction cost overall).

        //

        // We store liveranges in reverse order in the `.ranges`

        // array, then reverse them at the end of

        // `compute_liveness()`.

        if !self.vregs[vreg].ranges.is_empty() {

            let last_range_index = self.vregs[vreg].ranges.last().unwrap().index;

            let last_range = self.ranges[last_range_index].range;

            if self.func.allow_multiple_vreg_defs() {

                if last_range.contains(&range) {

                    // Special case (may occur when multiple defs of pinned

                    // physical regs occur): if this new range overlaps the

                    // existing range, return it.

                    return last_range_index;

                }

                // If this range's end falls in the middle of the last

                // range, truncate it to be contiguous so we can merge

                // below.

                if range.to >= last_range.from && range.to <= last_range.to {

                    range.to = last_range.from;

                }

            }

            debug_assert!(

                range.to <= last_range.from,

                "range {:?}, last_range {:?}",

                range,

                last_range

            );

        }

        if self.vregs[vreg].ranges.is_empty()

            || range.to

                < self.ranges[self.vregs[vreg].ranges.last().unwrap().index]

                    .range

                    .from

        {

            // Is not contiguous with previously-added (immediately

            // following) range; create a new range.

            let lr = self.ctx.ranges.add(range, self.ctx.bump());

            self.ranges[lr].vreg = vreg;

            self.vregs[vreg]

                .ranges

                .push(LiveRangeListEntry { range, index: lr });

            lr

        } else {

            // Is contiguous with previously-added range; just extend

            // its range and return it.

            let lr = self.vregs[vreg].ranges.last().unwrap().index;

            debug_assert!(range.to == self.ranges[lr].range.from);

            self.ranges[lr].range.from = range.from;

            lr

        }

    }

    pub fn insert_use_into_liverange(&mut self, into: LiveRangeIndex, mut u: Use) {

        let operand = u.operand;

        let constraint = operand.constraint();

        let block = self.cfginfo.insn_block[u.pos.inst().index()];

        let loop_depth = self.cfginfo.approx_loop_depth[block.index()] as usize;

        let weight = spill_weight_from_constraint(

            constraint,

            loop_depth,

            operand.kind() != OperandKind::Use,

        );

        u.weight = weight.to_bits();

        trace!(

            "insert use {:?} into lr {:?} with weight {:?}",

            u,

            into,

            weight,

        );

        // N.B.: we do *not* update `requirement` on the range,

        // because those will be computed during the multi-fixed-reg

        // fixup pass later (after all uses are inserted).

        self.ranges[into].uses.push(u);

        // Update stats.

        let range_weight = self.ranges[into].uses_spill_weight() + weight;

        self.ranges[into].set_uses_spill_weight(range_weight);

        trace!(

            "  -> now range has weight {:?}",

            self.ranges[into].uses_spill_weight(),

        );

    }

    pub fn find_vreg_liverange_for_pos(

        &self,

        vreg: VRegIndex,

        pos: ProgPoint,

    ) -> Option<LiveRangeIndex> {

        for entry in &self.vregs[vreg].ranges {

            if entry.range.contains_point(pos) {

                return Some(entry.index);

            }

        }

        None

    }

    pub fn add_liverange_to_preg(&mut self, range: CodeRange, reg: PReg) {

        trace!("adding liverange to preg: {:?} to {}", range, reg);

        let preg_idx = PRegIndex::new(reg.index());

        let res = self.pregs[preg_idx.index()]

            .allocations

            .btree

            .insert(LiveRangeKey::from_range(&range), LiveRangeIndex::invalid());

        debug_assert!(res.is_none());

    }

    pub fn is_live_in(&mut self, block: Block, vreg: VRegIndex) -> bool {

        self.liveins[block.index()].get(vreg.index())

    }

    pub fn compute_liveness(&mut self) -> Result<(), RegAllocError> {

        // Create initial LiveIn and LiveOut bitsets.

        for _ in 0..self.func.num_blocks() {

            self.liveins.push(IndexSet::new());

            self.liveouts.push(IndexSet::new());

        }

        // Run a worklist algorithm to precisely compute liveins and

        // liveouts.

        let mut workqueue = core::mem::take(&mut self.ctx.scratch_workqueue);

        let mut workqueue_set = core::mem::take(&mut self.ctx.scratch_workqueue_set);

        workqueue_set.clear();

        // Initialize workqueue with postorder traversal.

        for &block in &self.cfginfo.postorder[..] {

            workqueue.push_back(block);

            workqueue_set.insert(block);

        }

        while let Some(block) = workqueue.pop_front() {

            workqueue_set.remove(&block);

            let insns = self.func.block_insns(block);

            trace!("computing liveins for block{}", block.index());

            self.output.stats.livein_iterations += 1;

            let mut live = self.liveouts[block.index()].clone();

            trace!(" -> initial liveout set: {:?}", live);

            // Include outgoing blockparams in the initial live set.

            if self.func.is_branch(insns.last()) {

                for i in 0..self.func.block_succs(block).len() {

                    for &param in self.func.branch_blockparams(block, insns.last(), i) {

                        live.set(param.vreg(), true);

                        self.observe_vreg_class(param);

                    }

                }

            }

            for inst in insns.iter().rev() {

                for pos in &[OperandPos::Late, OperandPos::Early] {

                    for op in self.func.inst_operands(inst) {

                        if op.as_fixed_nonallocatable().is_some() {

                            continue;

                        }

                        if op.pos() == *pos {

                            let was_live = live.get(op.vreg().vreg());

                            trace!("op {:?} was_live = {}", op, was_live);

                            match op.kind() {

                                OperandKind::Use => {

                                    live.set(op.vreg().vreg(), true);

                                }

                                OperandKind::Def => {

                                    live.set(op.vreg().vreg(), false);

                                }

                            }

                            self.observe_vreg_class(op.vreg());

                        }

                    }

                }

            }

            for &blockparam in self.func.block_params(block) {

                live.set(blockparam.vreg(), false);

                self.observe_vreg_class(blockparam);

            }

            for &pred in self.func.block_preds(block) {

                if self.ctx.liveouts[pred.index()].union_with(&live) {

                    if !workqueue_set.contains(&pred) {

                        workqueue_set.insert(pred);

                        workqueue.push_back(pred);

                    }

                }

            }

            trace!("computed liveins at block{}: {:?}", block.index(), live);

            self.liveins[block.index()] = live;

        }

        // Check that there are no liveins to the entry block.

        if !self.liveins[self.func.entry_block().index()].is_empty() {

            trace!(

                "non-empty liveins to entry block: {:?}",

                self.liveins[self.func.entry_block().index()]

            );

            return Err(RegAllocError::EntryLivein);

        }

        self.ctx.scratch_workqueue = workqueue;

        self.ctx.scratch_workqueue_set = workqueue_set;

        Ok(())

    }

    pub fn build_liveranges(&mut self) -> Result<(), RegAllocError> {

        // Create Uses and Defs referring to VRegs, and place the Uses

        // in LiveRanges.

        //

        // We already computed precise liveouts and liveins for every

        // block above, so we don't need to run an iterative algorithm

        // here; instead, every block's computation is purely local,

        // from end to start.

        // Track current LiveRange for each vreg.

        //

        // Invariant: a stale range may be present here; ranges are

        // only valid if `live.get(vreg)` is true.

        let mut vreg_ranges = core::mem::take(&mut self.ctx.scratch_vreg_ranges);

        vreg_ranges.repopulate(self.func.num_vregs(), LiveRangeIndex::invalid());

        let mut operand_rewrites = core::mem::take(&mut self.ctx.scratch_operand_rewrites);

        for i in (0..self.func.num_blocks()).rev() {

            let block = Block::new(i);

            let insns = self.func.block_insns(block);

            self.output.stats.livein_blocks += 1;

            // Init our local live-in set.

            let mut live = self.liveouts[block.index()].clone();

            // If the last instruction is a branch (rather than

            // return), create blockparam_out entries.

            if self.func.is_branch(insns.last()) {

                for (i, &succ) in self.func.block_succs(block).iter().enumerate() {

                    let blockparams_in = self.func.block_params(succ);

                    let blockparams_out = self.func.branch_blockparams(block, insns.last(), i);

                    for (&blockparam_in, &blockparam_out) in

                        blockparams_in.iter().zip(blockparams_out)

                    {

                        let blockparam_out = VRegIndex::new(blockparam_out.vreg());

                        let blockparam_in = VRegIndex::new(blockparam_in.vreg());

                        self.blockparam_outs.push(BlockparamOut {

                            to_vreg: blockparam_in,

                            to_block: succ,

                            from_block: block,

                            from_vreg: blockparam_out,

                        });

                        // Include outgoing blockparams in the initial live set.

                        live.set(blockparam_out.index(), true);

                    }

                }

            }

            // Initially, registers are assumed live for the whole block.

            for vreg in live.iter() {

                let range = CodeRange {

                    from: self.cfginfo.block_entry[block.index()],

                    to: self.cfginfo.block_exit[block.index()].next(),

                };

                trace!(

                    "vreg {:?} live at end of block --> create range {:?}",

                    VRegIndex::new(vreg),

                    range

                );

                let lr = self.add_liverange_to_vreg(VRegIndex::new(vreg), range);

                vreg_ranges[vreg] = lr;

            }

            // Create vreg data for blockparams.

            for &param in self.func.block_params(block) {

                self.vregs[param].blockparam = block;

            }

            // For each instruction, in reverse order, process

            // operands and clobbers.

            for inst in insns.iter().rev() {

                // Mark clobbers with CodeRanges on PRegs.

                for clobber in self.func.inst_clobbers(inst) {

                    // Clobber range is at After point only: an

                    // instruction can still take an input in a reg

                    // that it later clobbers. (In other words, the

                    // clobber is like a normal def that never gets

                    // used.)

                    let range = CodeRange {

                        from: ProgPoint::after(inst),

                        to: ProgPoint::before(inst.next()),

                    };

                    self.add_liverange_to_preg(range, clobber);

                }

                // Does the instruction have any input-reusing

                // outputs? This is important below to establish

                // proper interference wrt other inputs. We note the

                // *vreg* that is reused, not the index.

                let mut reused_input = None;

                for op in self.func.inst_operands(inst) {

                    if let OperandConstraint::Reuse(i) = op.constraint() {

                        debug_assert!(self.func.inst_operands(inst)[i]

                            .as_fixed_nonallocatable()

                            .is_none());

                        reused_input = Some(self.func.inst_operands(inst)[i].vreg());

                        break;

                    }

                }

                // Preprocess defs and uses. Specifically, if there

                // are any fixed-reg-constrained defs at Late position

                // and fixed-reg-constrained uses at Early position

                // with the same preg, we need to (i) add a fixup move

                // for the use, (ii) rewrite the use to have an Any

                // constraint, and (ii) move the def to Early position

                // to reserve the register for the whole instruction.

                //

                // We don't touch any fixed-early-def or fixed-late-use

                // constraints: the only situation where the same physical

                // register can be used multiple times in the same

                // instruction is with an early-use and a late-def. Anything

                // else is a user error.

                operand_rewrites.clear();

                let mut late_def_fixed: SmallVec<[PReg; 8]> = smallvec![];

                for &operand in self.func.inst_operands(inst) {

                    if let OperandConstraint::FixedReg(preg) = operand.constraint() {

                        match (operand.pos(), operand.kind()) {

                            (OperandPos::Late, OperandKind::Def) => {

                                late_def_fixed.push(preg);

                            }

                            _ => {}

                        }

                    }

                }

                for (i, &operand) in self.func.inst_operands(inst).iter().enumerate() {

                    if operand.as_fixed_nonallocatable().is_some() {

                        continue;

                    }

                    if let OperandConstraint::FixedReg(preg) = operand.constraint() {

                        match (operand.pos(), operand.kind()) {

                            (OperandPos::Early, OperandKind::Use)

                                if live.get(operand.vreg().vreg()) =>

                            {

                                // If we have a use constraint at the

                                // Early point for a fixed preg, and

                                // this preg is also constrained with

                                // a *separate* def at Late or is

                                // clobbered, and *if* the vreg is

                                // live downward, we have to use the

                                // multi-fixed-reg mechanism for a

                                // fixup and rewrite here without the

                                // constraint. See #53.

                                //

                                // We adjust the def liverange and Use

                                // to an "early" position to reserve

                                // the register, it still must not be

                                // used by some other vreg at the

                                // use-site.

                                //

                                // Note that we handle multiple

                                // conflicting constraints for the

                                // same vreg in a separate pass (see

                                // `fixup_multi_fixed_vregs` below).

                                if late_def_fixed.contains(&preg)

                                    || self.func.inst_clobbers(inst).contains(preg)

                                {

                                    trace!(

                                        concat!(

                                            "-> operand {:?} is fixed to preg {:?}, ",

                                            "is downward live, and there is also a ",

                                            "def or clobber at this preg"

                                        ),

                                        operand,

                                        preg

                                    );

                                    let pos = ProgPoint::before(inst);

                                    self.multi_fixed_reg_fixups.push(MultiFixedRegFixup {

                                        pos,

                                        from_slot: slot_idx(i)?,

                                        to_slot: slot_idx(i)?,

                                        to_preg: PRegIndex::new(preg.index()),

                                        vreg: VRegIndex::new(operand.vreg().vreg()),

                                        level: FixedRegFixupLevel::Initial,

                                    });

                                    // We need to insert a reservation

                                    // at the before-point to reserve

                                    // the reg for the use too.

                                    let range = CodeRange::singleton(pos);

                                    self.add_liverange_to_preg(range, preg);

                                    // Remove the fixed-preg

                                    // constraint from the Use.

                                    operand_rewrites.insert(

                                        i,

                                        Operand::new(

                                            operand.vreg(),

                                            OperandConstraint::Any,

                                            operand.kind(),

                                            operand.pos(),

                                        ),

                                    );

                                }

                            }

                            _ => {}

                        }

                    }

                }

                // Process defs and uses.

                for &cur_pos in &[InstPosition::After, InstPosition::Before] {

                    for i in 0..self.func.inst_operands(inst).len() {

                        // don't borrow `self`

                        let operand = operand_rewrites

                            .get(&i)

                            .cloned()

                            .unwrap_or(self.func.inst_operands(inst)[i]);

                        let pos = match (operand.kind(), operand.pos()) {

                            (OperandKind::Def, OperandPos::Early) => ProgPoint::before(inst),

                            (OperandKind::Def, OperandPos::Late) => ProgPoint::after(inst),

                            (OperandKind::Use, OperandPos::Late) => ProgPoint::after(inst),

                            // If there are any reused inputs in this

                            // instruction, and this is *not* the

                            // reused vreg, force `pos` to

                            // `After`. This ensures that we correctly

                            // account for the interference between

                            // the other inputs and the

                            // input-that-is-reused/output.

                            (OperandKind::Use, OperandPos::Early)

                                if reused_input.is_some()

                                    && reused_input.unwrap() != operand.vreg() =>

                            {

                                ProgPoint::after(inst)

                            }

                            (OperandKind::Use, OperandPos::Early) => ProgPoint::before(inst),

                        };

                        if pos.pos() != cur_pos {

                            continue;

                        }

                        trace!(

                            "processing inst{} operand at {:?}: {:?}",

                            inst.index(),

                            pos,

                            operand

                        );

                        // If this is a "fixed non-allocatable

                        // register" operand, set the alloc

                        // immediately and then ignore the operand

                        // hereafter.

                        if let Some(preg) = operand.as_fixed_nonallocatable() {

                            self.set_alloc(inst, i, Allocation::reg(preg));

                            continue;

                        }

                        match operand.kind() {

                            OperandKind::Def => {

                                trace!("Def of {} at {:?}", operand.vreg(), pos);

                                // Get or create the LiveRange.

                                let mut lr = vreg_ranges[operand.vreg().vreg()];

                                trace!(" -> has existing LR {:?}", lr);

                                // If there was no liverange (dead def), create a trivial one.

                                if !live.get(operand.vreg().vreg()) {

                                    let from = pos;

                                    // We want to we want to span

                                    // until Before of the next

                                    // inst. This ensures that early

                                    // defs used for temps on an

                                    // instruction are reserved across

                                    // the whole instruction.

                                    let to = ProgPoint::before(pos.inst().next());

                                    lr = self.add_liverange_to_vreg(

                                        VRegIndex::new(operand.vreg().vreg()),

                                        CodeRange { from, to },

                                    );

                                    trace!(" -> invalid; created {:?}", lr);

                                    vreg_ranges[operand.vreg().vreg()] = lr;

                                    live.set(operand.vreg().vreg(), true);

                                }

                                // Create the use in the LiveRange.

                                self.insert_use_into_liverange(

                                    lr,

                                    Use::new(operand, pos, slot_idx(i)?),

                                );

                                // If def (not mod), this reg is now dead,

                                // scanning backward; make it so.

                                if operand.kind() == OperandKind::Def {

                                    // Trim the range for this vreg to start

                                    // at `pos` if it previously ended at the

                                    // start of this block (i.e. was not

                                    // merged into some larger LiveRange due

                                    // to out-of-order blocks).

                                    if self.ranges[lr].range.from

                                        == self.cfginfo.block_entry[block.index()]

                                    {

                                        trace!(" -> started at block start; trimming to {:?}", pos);

                                        self.ranges[lr].range.from = pos;

                                    }

                                    self.ranges[lr].set_flag(LiveRangeFlag::StartsAtDef);

                                    // Remove from live-set.

                                    live.set(operand.vreg().vreg(), false);

                                    vreg_ranges[operand.vreg().vreg()] = LiveRangeIndex::invalid();

                                }

                            }

                            OperandKind::Use => {

                                // Create/extend the LiveRange if it

                                // doesn't already exist, and add the use

                                // to the range.

                                let mut lr = vreg_ranges[operand.vreg().vreg()];

                                if !live.get(operand.vreg().vreg()) {

                                    let range = CodeRange {

                                        from: self.cfginfo.block_entry[block.index()],

                                        to: pos.next(),

                                    };

                                    lr = self.add_liverange_to_vreg(

                                        VRegIndex::new(operand.vreg().vreg()),

                                        range,

                                    );

                                    vreg_ranges[operand.vreg().vreg()] = lr;

                                }

                                debug_assert!(lr.is_valid());

                                trace!("Use of {:?} at {:?} -> {:?}", operand, pos, lr,);

                                self.insert_use_into_liverange(

                                    lr,

                                    Use::new(operand, pos, slot_idx(i)?),

                                );

                                // Add to live-set.

                                live.set(operand.vreg().vreg(), true);

                            }

                        }

                    }

                }

            }

            // Block parameters define vregs at the very beginning of

            // the block. Remove their live vregs from the live set

            // here.

            for vreg in self.func.block_params(block) {

                if live.get(vreg.vreg()) {

                    live.set(vreg.vreg(), false);

                } else {

                    // Create trivial liverange if blockparam is dead.

                    let start = self.cfginfo.block_entry[block.index()];

                    self.add_liverange_to_vreg(

                        VRegIndex::new(vreg.vreg()),

                        CodeRange {

                            from: start,

                            to: start.next(),

                        },

                    );

                }

                // add `blockparam_ins` entries.

                let vreg_idx = VRegIndex::new(vreg.vreg());

                for &pred in self.func.block_preds(block) {

                    self.blockparam_ins.push(BlockparamIn {

                        to_vreg: vreg_idx,

                        to_block: block,

                        from_block: pred,

                    });

                }

            }

        }

        // Make ranges in each vreg and uses in each range appear in

        // sorted order. We built them in reverse order above, so this

        // is a simple reversal, *not* a full sort.

        //

        // The ordering invariant is always maintained for uses and

        // always for ranges in bundles (which are initialized later),

        // but not always for ranges in vregs; those are sorted only

        // when needed, here and then again at the end of allocation

        // when resolving moves.

        for vreg in &mut self.ctx.vregs {

            vreg.ranges.reverse();

            let mut last = None;

            for entry in &mut vreg.ranges {

                // Ranges may have been truncated above at defs. We

                // need to update with the final range here.

                entry.range = self.ctx.ranges[entry.index].range;

                // Assert in-order and non-overlapping.

                debug_assert!(last.is_none() || last.unwrap() <= entry.range.from);

                last = Some(entry.range.to);

            }

        }

        for range in &mut self.ranges {

            range.uses.reverse();

            debug_assert!(range.uses.windows(2).all(|win| win[0].pos <= win[1].pos));

        }

        self.blockparam_ins.sort_unstable_by_key(|x| x.key());

        self.blockparam_outs.sort_unstable_by_key(|x| x.key());

        self.output.stats.initial_liverange_count = self.ranges.len();

        self.output.stats.blockparam_ins_count = self.blockparam_ins.len();

        self.output.stats.blockparam_outs_count = self.blockparam_outs.len();

        self.ctx.scratch_vreg_ranges = vreg_ranges;

        self.ctx.scratch_operand_rewrites = operand_rewrites;

        Ok(())

    }

    pub fn fixup_multi_fixed_vregs(&mut self) {

        // Do a fixed-reg cleanup pass: if there are any LiveRanges with

        // multiple uses at the same ProgPoint and there is

        // more than one FixedReg constraint at that ProgPoint, we

        // need to record all but one of them in a special fixup list

        // and handle them later; otherwise, bundle-splitting to

        // create minimal bundles becomes much more complex (we would

        // have to split the multiple uses at the same progpoint into

        // different bundles, which breaks invariants related to

        // disjoint ranges and bundles).

        let mut extra_clobbers: SmallVec<[(PReg, ProgPoint); 8]> = smallvec![];

        for vreg in 0..self.vregs.len() {

            let vreg = VRegIndex::new(vreg);

            for range_idx in 0..self.vregs[vreg].ranges.len() {

                let entry = self.vregs[vreg].ranges[range_idx];

                let range = entry.index;

                trace!("multi-fixed-reg cleanup: vreg {:?} range {:?}", vreg, range,);

                // Find groups of uses that occur in at the same program point.

                for uses in self.ctx.ranges[range]

                    .uses

                    .chunk_by_mut(|a, b| a.pos == b.pos)

                {

                    if uses.len() < 2 {

                        continue;

                    }

                    // Search for conflicting constraints in the uses.

                    let mut requires_reg = false;

                    let mut num_fixed_reg = 0;

                    let mut num_fixed_stack = 0;

                    let mut first_reg_slot = None;

                    let mut first_stack_slot = None;

                    let mut min_limit = usize::MAX;

                    let mut max_fixed_reg = usize::MIN;

                    for u in uses.iter() {

                        match u.operand.constraint() {

                            OperandConstraint::Any => {

                                first_reg_slot.get_or_insert(u.slot);

                                first_stack_slot.get_or_insert(u.slot);

                            }

                            OperandConstraint::Reg | OperandConstraint::Reuse(_) => {

                                first_reg_slot.get_or_insert(u.slot);

                                requires_reg = true;

                            }

                            OperandConstraint::Limit(max) => {

                                first_reg_slot.get_or_insert(u.slot);

                                min_limit = min_limit.min(max);

                                requires_reg = true;

                            }

                            OperandConstraint::FixedReg(preg) => {

                                max_fixed_reg = max_fixed_reg.max(preg.hw_enc());

                                if self.ctx.pregs[preg.index()].is_stack {

                                    num_fixed_stack += 1;

                                    first_stack_slot.get_or_insert(u.slot);

                                } else {

                                    requires_reg = true;

                                    num_fixed_reg += 1;

                                    first_reg_slot.get_or_insert(u.slot);

                                }

                            }

                            // Maybe this could be supported in this future...

                            OperandConstraint::Stack => panic!(

                                "multiple uses of vreg with a Stack constraint are not supported"

                            ),

                        }

                    }

                    // Fast path if there are no conflicts.

                    if num_fixed_reg + num_fixed_stack <= 1

                        && !(requires_reg && num_fixed_stack != 0)

                        && max_fixed_reg < min_limit

                    {

                        continue;

                    }

                    // We pick one constraint (in order: FixedReg, Reg, FixedStack)

                    // and then rewrite any incompatible constraints to Any.

                    // This allows register allocation to succeed and we will

                    // later insert moves to satisfy the rewritten constraints.

                    let source_slot = if requires_reg {

                        first_reg_slot.unwrap()

                    } else {

                        first_stack_slot.unwrap()

                    };

                    let mut first_preg = None;

                    for u in uses.iter_mut() {

                        if let OperandConstraint::FixedReg(preg) = u.operand.constraint() {

                            let vreg_idx = VRegIndex::new(u.operand.vreg().vreg());

                            let preg_idx = PRegIndex::new(preg.index());

                            trace!(

                                "at pos {:?}, vreg {:?} has fixed constraint to preg {:?}",

                                u.pos,

                                vreg_idx,

                                preg_idx

                            );

                            // FixedStack is incompatible if there are any

                            // Reg/FixedReg constraints. FixedReg is

                            // incompatible if there already is a different

                            // FixedReg constraint. If either condition is true,

                            // we edit the constraint below; otherwise, we can

                            // skip this edit.

                            if !(requires_reg && self.ctx.pregs[preg.index()].is_stack)

                                && *first_preg.get_or_insert(preg) == preg

                                && preg.hw_enc() < min_limit

                            {

                                continue;

                            }

                            trace!(" -> duplicate; switching to constraint Any");

                            self.ctx.multi_fixed_reg_fixups.push(MultiFixedRegFixup {

                                pos: u.pos,

                                from_slot: source_slot,

                                to_slot: u.slot,

                                to_preg: preg_idx,

                                vreg: vreg_idx,

                                level: FixedRegFixupLevel::Secondary,

                            });

                            u.operand = Operand::new(

                                u.operand.vreg(),

                                OperandConstraint::Any,