regalloc2/ion/
requirement.rs

1/*
2 * This file was initially derived from the files
3 * `js/src/jit/BacktrackingAllocator.h` and
4 * `js/src/jit/BacktrackingAllocator.cpp` in Mozilla Firefox, and was
5 * originally licensed under the Mozilla Public License 2.0. We
6 * subsequently relicensed it to Apache-2.0 WITH LLVM-exception (see
7 * https://github.com/bytecodealliance/regalloc2/issues/7).
8 *
9 * Since the initial port, the design has been substantially evolved
10 * and optimized.
11 */
12
13//! Requirements computation.
14
15use super::{Env, LiveBundleIndex};
16use crate::{Function, Inst, Operand, OperandConstraint, PReg, ProgPoint};
17
18pub struct RequirementConflict;
19
20#[derive(Clone, Copy, Debug)]
21pub enum RequirementConflictAt {
22    /// A transition from a stack-constrained to a reg-constrained
23    /// segment. The suggested split point is late, to keep the
24    /// intervening region with the stackslot (which is cheaper).
25    StackToReg(ProgPoint),
26    /// A transition from a reg-constraint to a stack-constrained
27    /// segment. Mirror of above: the suggested split point is early
28    /// (just after the last register use).
29    RegToStack(ProgPoint),
30    /// Any other transition. The suggested split point is late (just
31    /// before the conflicting use), but the split will also trim the
32    /// ends and create a split bundle, so the intervening region will
33    /// not appear with either side. This is probably for the best
34    /// when e.g. the two sides of the split are both constrained to
35    /// different physical registers: the part in the middle should be
36    /// constrained to neither.
37    Other(ProgPoint),
38}
39
40impl RequirementConflictAt {
41    #[inline(always)]
42    pub fn should_trim_edges_around_split(self) -> bool {
43        match self {
44            RequirementConflictAt::RegToStack(..) | RequirementConflictAt::StackToReg(..) => false,
45            RequirementConflictAt::Other(..) => true,
46        }
47    }
48
49    #[inline(always)]
50    pub fn suggested_split_point(self) -> ProgPoint {
51        match self {
52            RequirementConflictAt::RegToStack(pt)
53            | RequirementConflictAt::StackToReg(pt)
54            | RequirementConflictAt::Other(pt) => pt,
55        }
56    }
57}
58
59#[derive(Clone, Copy, Debug, PartialEq, Eq)]
60pub enum Requirement {
61    FixedReg(PReg),
62    FixedStack(PReg),
63    Register,
64    Stack,
65    Any,
66}
67impl Requirement {
68    #[inline(always)]
69    pub fn merge(self, other: Requirement) -> Result<Requirement, RequirementConflict> {
70        match (self, other) {
71            (other, Requirement::Any) | (Requirement::Any, other) => Ok(other),
72            (Requirement::Register, Requirement::Register) => Ok(self),
73            (Requirement::Stack, Requirement::Stack) => Ok(self),
74            (Requirement::Register, Requirement::FixedReg(preg))
75            | (Requirement::FixedReg(preg), Requirement::Register) => {
76                Ok(Requirement::FixedReg(preg))
77            }
78            (Requirement::Stack, Requirement::FixedStack(preg))
79            | (Requirement::FixedStack(preg), Requirement::Stack) => {
80                Ok(Requirement::FixedStack(preg))
81            }
82            (Requirement::FixedReg(a), Requirement::FixedReg(b)) if a == b => Ok(self),
83            (Requirement::FixedStack(a), Requirement::FixedStack(b)) if a == b => Ok(self),
84            _ => Err(RequirementConflict),
85        }
86    }
87
88    #[inline(always)]
89    pub fn is_stack(self) -> bool {
90        match self {
91            Requirement::Stack | Requirement::FixedStack(..) => true,
92            Requirement::Register | Requirement::FixedReg(..) => false,
93            Requirement::Any => false,
94        }
95    }
96
97    #[inline(always)]
98    pub fn is_reg(self) -> bool {
99        match self {
100            Requirement::Register | Requirement::FixedReg(..) => true,
101            Requirement::Stack | Requirement::FixedStack(..) => false,
102            Requirement::Any => false,
103        }
104    }
105}
106
107impl<'a, F: Function> Env<'a, F> {
108    #[inline(always)]
109    pub fn requirement_from_operand(&self, op: Operand) -> Requirement {
110        match op.constraint() {
111            OperandConstraint::FixedReg(preg) => {
112                if self.pregs[preg.index()].is_stack {
113                    Requirement::FixedStack(preg)
114                } else {
115                    Requirement::FixedReg(preg)
116                }
117            }
118            OperandConstraint::Reg | OperandConstraint::Reuse(_) => Requirement::Register,
119            OperandConstraint::Stack => Requirement::Stack,
120            OperandConstraint::Any => Requirement::Any,
121        }
122    }
123
124    pub fn compute_requirement(
125        &self,
126        bundle: LiveBundleIndex,
127    ) -> Result<Requirement, RequirementConflictAt> {
128        let mut req = Requirement::Any;
129        let mut last_pos = ProgPoint::before(Inst::new(0));
130        trace!("compute_requirement: {:?}", bundle);
131        let ranges = &self.bundles[bundle].ranges;
132        for entry in ranges {
133            trace!(" -> LR {:?}: {:?}", entry.index, entry.range);
134            for u in &self.ranges[entry.index].uses {
135                trace!("  -> use {:?}", u);
136                let r = self.requirement_from_operand(u.operand);
137                req = req.merge(r).map_err(|_| {
138                    trace!("     -> conflict");
139                    if req.is_stack() && r.is_reg() {
140                        // Suggested split point just before the reg (i.e., late split).
141                        RequirementConflictAt::StackToReg(u.pos)
142                    } else if req.is_reg() && r.is_stack() {
143                        // Suggested split point just after the stack
144                        // (i.e., early split). Note that splitting
145                        // with a use *right* at the beginning is
146                        // interpreted by `split_and_requeue_bundle`
147                        // as splitting off the first use.
148                        RequirementConflictAt::RegToStack(last_pos)
149                    } else {
150                        RequirementConflictAt::Other(u.pos)
151                    }
152                })?;
153                last_pos = u.pos;
154                trace!("     -> req {:?}", req);
155            }
156        }
157        trace!(" -> final: {:?}", req);
158        Ok(req)
159    }
160
161    pub fn merge_bundle_requirements(
162        &self,
163        a: LiveBundleIndex,
164        b: LiveBundleIndex,
165    ) -> Result<Requirement, RequirementConflict> {
166        let req_a = self
167            .compute_requirement(a)
168            .map_err(|_| RequirementConflict)?;
169        let req_b = self
170            .compute_requirement(b)
171            .map_err(|_| RequirementConflict)?;
172        req_a.merge(req_b)
173    }
174}
regalloc2/ion/requirement.rs

regalloc2/ion/
requirement.rs
