regalloc2/ion/

requirement.rs

/*
 * 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.
 */

//! Requirements computation.

use super::{Env, LiveBundleIndex};
use crate::{Function, Inst, Operand, OperandConstraint, PReg, ProgPoint};

pub struct RequirementConflict;

#[derive(Clone, Copy, Debug)]
pub enum RequirementConflictAt {
    /// A transition from a stack-constrained to a reg-constrained
    /// segment. The suggested split point is late, to keep the
    /// intervening region with the stackslot (which is cheaper).
    StackToReg(ProgPoint),
    /// A transition from a reg-constraint to a stack-constrained
    /// segment. Mirror of above: the suggested split point is early
    /// (just after the last register use).
    RegToStack(ProgPoint),
    /// Any other transition. The suggested split point is late (just
    /// before the conflicting use), but the split will also trim the
    /// ends and create a split bundle, so the intervening region will
    /// not appear with either side. This is probably for the best
    /// when e.g. the two sides of the split are both constrained to
    /// different physical registers: the part in the middle should be
    /// constrained to neither.
    Other(ProgPoint),
}

impl RequirementConflictAt {
    #[inline(always)]
    pub fn should_trim_edges_around_split(self) -> bool {
        match self {
            RequirementConflictAt::RegToStack(..) | RequirementConflictAt::StackToReg(..) => false,
            RequirementConflictAt::Other(..) => true,
        }
    }

    #[inline(always)]
    pub fn suggested_split_point(self) -> ProgPoint {
        match self {
            RequirementConflictAt::RegToStack(pt)
            | RequirementConflictAt::StackToReg(pt)
            | RequirementConflictAt::Other(pt) => pt,
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Requirement {
    Any,
    Register,
    FixedReg(PReg),
    Limit(usize),
    Stack,
    FixedStack(PReg),
}
impl Requirement {
    #[inline(always)]
    pub fn merge(self, other: Requirement) -> Result<Requirement, RequirementConflict> {
        use Requirement::*;

        match (self, other) {
            // `Any` matches anything.
            (other, Any) | (Any, other) => Ok(other),
            // Same kinds match.
            (Register, Register) => Ok(self),
            (Stack, Stack) => Ok(self),
            (Limit(a), Limit(b)) => Ok(Limit(a.min(b))),
            (FixedReg(a), FixedReg(b)) if a == b => Ok(self),
            (FixedStack(a), FixedStack(b)) if a == b => Ok(self),
            // Limit a 'Register|FixedReg`.
            (Limit(a), Register) | (Register, Limit(a)) => Ok(Limit(a)),
            (Limit(a), FixedReg(b)) | (FixedReg(b), Limit(a)) if usize::from(a) > b.hw_enc() => {
                Ok(FixedReg(b))
            }
            // Constrain `Register|Stack` to `Fixed{Reg|Stack}`.
            (Register, FixedReg(preg)) | (FixedReg(preg), Register) => Ok(FixedReg(preg)),
            (Stack, FixedStack(preg)) | (FixedStack(preg), Stack) => Ok(FixedStack(preg)),
            // Fail otherwise.
            _ => Err(RequirementConflict),
        }
    }

    #[inline(always)]
    pub fn is_stack(self) -> bool {
        match self {
            Requirement::Stack | Requirement::FixedStack(..) => true,
            Requirement::Register | Requirement::FixedReg(..) | Requirement::Limit(..) => false,
            Requirement::Any => false,
        }
    }

    #[inline(always)]
    pub fn is_reg(self) -> bool {
        match self {
            Requirement::Register | Requirement::FixedReg(..) | Requirement::Limit(..) => true,
            Requirement::Stack | Requirement::FixedStack(..) => false,
            Requirement::Any => false,
        }
    }
}

impl<'a, F: Function> Env<'a, F> {
    #[inline(always)]
    pub fn requirement_from_operand(&self, op: Operand) -> Requirement {
        match op.constraint() {
            OperandConstraint::FixedReg(preg) => {
                if self.pregs[preg.index()].is_stack {
                    Requirement::FixedStack(preg)
                } else {
                    Requirement::FixedReg(preg)
                }
            }
            OperandConstraint::Reg | OperandConstraint::Reuse(_) => Requirement::Register,
            OperandConstraint::Limit(max) => Requirement::Limit(max),
            OperandConstraint::Stack => Requirement::Stack,
            OperandConstraint::Any => Requirement::Any,
        }
    }

    pub fn compute_requirement(
        &self,
        bundle: LiveBundleIndex,
    ) -> Result<Requirement, RequirementConflictAt> {
        let mut req = Requirement::Any;
        let mut last_pos = ProgPoint::before(Inst::new(0));
        trace!("compute_requirement: {:?}", bundle);
        let ranges = &self.bundles[bundle].ranges;
        for entry in ranges {
            trace!(" -> LR {:?}: {:?}", entry.index, entry.range);
            for u in &self.ranges[entry.index].uses {
                trace!("  -> use {:?}", u);
                let r = self.requirement_from_operand(u.operand);
                req = req.merge(r).map_err(|_| {
                    trace!("     -> conflict");
                    if req.is_stack() && r.is_reg() {
                        // Suggested split point just before the reg (i.e., late split).
                        RequirementConflictAt::StackToReg(u.pos)
                    } else if req.is_reg() && r.is_stack() {
                        // Suggested split point just after the stack
                        // (i.e., early split). Note that splitting
                        // with a use *right* at the beginning is
                        // interpreted by `split_and_requeue_bundle`
                        // as splitting off the first use.
                        RequirementConflictAt::RegToStack(last_pos)
                    } else {
                        RequirementConflictAt::Other(u.pos)
                    }
                })?;
                last_pos = u.pos;
                trace!("     -> req {:?}", req);
            }
        }
        trace!(" -> final: {:?}", req);
        Ok(req)
    }

    pub fn merge_bundle_requirements(
        &self,
        a: LiveBundleIndex,
        b: LiveBundleIndex,
    ) -> Result<Requirement, RequirementConflict> {
        let req_a = self
            .compute_requirement(a)
            .map_err(|_| RequirementConflict)?;
        let req_b = self
            .compute_requirement(b)
            .map_err(|_| RequirementConflict)?;
        req_a.merge(req_b)
    }
}