backend_lang/
regs.rs

1//! Registers: physical registers of a target, virtual registers of a
2//! function, the classes that type them, and sets of physical registers.
3//!
4//! All four are dense numbers. A [`PReg`] indexes the target's register file
5//! ([`Target::regs`](crate::target::Target::regs)), a [`RegClass`] indexes its
6//! class table, and a [`VReg`] indexes a function's virtual-register table,
7//! which records each virtual register's class. [`Reg`] is either kind,
8//! packed into one `u32`, so an operand that names a register is the same
9//! size before and after register allocation.
10
11use core::fmt;
12
13/// The most physical registers a target may describe.
14///
15/// [`RegSet`] is a fixed 128-bit set, so every target's register file fits
16/// in one, with room for x86-64's 16 general-purpose and 16 vector registers
17/// and AArch64's 31 + 32.
18pub const MAX_PREGS: usize = 128;
19
20/// A physical register: an index into the target's register file.
21///
22/// What the number means (its name, hardware encoding, and class) is the
23/// target's business; see [`Target::reg`](crate::target::Target::reg). The
24/// x86-64 target names its registers as constants, such as
25/// [`x86_64::RAX`](crate::x86_64::RAX).
26///
27/// # Examples
28///
29/// ```
30/// use backend_lang::x86_64::{self, RAX, RDI};
31///
32/// assert_eq!(x86_64::TARGET.reg(RAX).name(), "rax");
33/// assert!(RAX.index() < RDI.index());
34/// ```
35#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
36pub struct PReg(u8);
37
38impl PReg {
39    /// The physical register with index `index`, or `None` past
40    /// [`MAX_PREGS`].
41    ///
42    /// # Examples
43    ///
44    /// ```
45    /// use backend_lang::PReg;
46    ///
47    /// assert_eq!(PReg::new(3).map(PReg::index), Some(3));
48    /// assert_eq!(PReg::new(128), None);
49    /// ```
50    #[inline]
51    #[must_use]
52    pub const fn new(index: usize) -> Option<PReg> {
53        if index < MAX_PREGS {
54            Some(PReg(index as u8))
55        } else {
56            None
57        }
58    }
59
60    /// Builds a register from an index the caller knows is in range (target
61    /// tables are checked by tests to stay below [`MAX_PREGS`]).
62    pub(crate) const fn from_index(index: u8) -> PReg {
63        PReg(index & (MAX_PREGS as u8 - 1))
64    }
65
66    /// The register's index in the target's register file.
67    ///
68    /// # Examples
69    ///
70    /// ```
71    /// use backend_lang::x86_64::RCX;
72    ///
73    /// assert_eq!(RCX.index(), 1);
74    /// ```
75    #[inline]
76    #[must_use]
77    pub const fn index(self) -> usize {
78        self.0 as usize
79    }
80}
81
82impl fmt::Debug for PReg {
83    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
84        write!(f, "p{}", self.0)
85    }
86}
87
88/// A virtual register: an index into a function's virtual-register table.
89///
90/// Virtual registers are created by
91/// [`Function::vreg`](crate::mir::Function::vreg), each with a
92/// [`RegClass`], and printed as `%N`.
93///
94/// # Examples
95///
96/// ```
97/// use backend_lang::mir::Function;
98/// use backend_lang::x86_64::{GPR, SYSV};
99///
100/// let mut f = Function::new("f", &SYSV);
101/// let v = f.vreg(GPR).unwrap();
102/// assert_eq!(v.as_virt().map(|v| v.index()), Some(0));
103/// assert_eq!(f.vreg_class(v.as_virt().unwrap()), Some(GPR));
104/// ```
105#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
106pub struct VReg(u32);
107
108impl VReg {
109    /// The most virtual registers one function may have: indexes use 31
110    /// bits, because [`Reg`] keeps the top bit to tell the two kinds apart.
111    pub const MAX: usize = (1 << 31) - 1;
112
113    pub(crate) const fn from_index(index: u32) -> VReg {
114        VReg(index & VIRT_MASK)
115    }
116
117    /// The register's index in its function's virtual-register table.
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// use backend_lang::mir::Function;
123    /// use backend_lang::x86_64::{GPR, SYSV};
124    ///
125    /// let mut f = Function::new("f", &SYSV);
126    /// let _ = f.vreg(GPR).unwrap();
127    /// let second = f.vreg(GPR).unwrap().as_virt().unwrap();
128    /// assert_eq!(second.index(), 1);
129    /// ```
130    #[inline]
131    #[must_use]
132    pub const fn index(self) -> usize {
133        self.0 as usize
134    }
135}
136
137impl fmt::Debug for VReg {
138    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139        write!(f, "%{}", self.0)
140    }
141}
142
143const VIRT_BIT: u32 = 1 << 31;
144const VIRT_MASK: u32 = VIRT_BIT - 1;
145
146/// A register operand: physical or virtual.
147///
148/// Before register allocation, instructions name virtual registers (and the
149/// physical registers an ABI or an instruction fixes); after it, only
150/// physical ones. Emission requires the latter.
151///
152/// # Examples
153///
154/// ```
155/// use backend_lang::Reg;
156/// use backend_lang::x86_64::RAX;
157///
158/// let r = Reg::from(RAX);
159/// assert_eq!(r.as_phys(), Some(RAX));
160/// assert!(r.as_virt().is_none());
161/// ```
162#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
163pub struct Reg(u32);
164
165impl Reg {
166    /// The register as a physical register, if it is one.
167    ///
168    /// # Examples
169    ///
170    /// ```
171    /// use backend_lang::Reg;
172    /// use backend_lang::x86_64::RSI;
173    ///
174    /// assert_eq!(Reg::from(RSI).as_phys(), Some(RSI));
175    /// ```
176    #[inline]
177    #[must_use]
178    pub const fn as_phys(self) -> Option<PReg> {
179        if self.0 & VIRT_BIT == 0 {
180            Some(PReg::from_index(self.0 as u8))
181        } else {
182            None
183        }
184    }
185
186    /// The register as a virtual register, if it is one.
187    ///
188    /// # Examples
189    ///
190    /// ```
191    /// use backend_lang::mir::Function;
192    /// use backend_lang::x86_64::{GPR, SYSV};
193    ///
194    /// let mut f = Function::new("f", &SYSV);
195    /// let r = f.vreg(GPR).unwrap();
196    /// assert!(r.as_virt().is_some());
197    /// assert!(r.as_phys().is_none());
198    /// ```
199    #[inline]
200    #[must_use]
201    pub const fn as_virt(self) -> Option<VReg> {
202        if self.0 & VIRT_BIT != 0 {
203            Some(VReg(self.0 & VIRT_MASK))
204        } else {
205            None
206        }
207    }
208
209    /// Whether this is a virtual register.
210    ///
211    /// # Examples
212    ///
213    /// ```
214    /// use backend_lang::Reg;
215    /// use backend_lang::x86_64::RAX;
216    ///
217    /// assert!(!Reg::from(RAX).is_virtual());
218    /// ```
219    #[inline]
220    #[must_use]
221    pub const fn is_virtual(self) -> bool {
222        self.0 & VIRT_BIT != 0
223    }
224}
225
226impl From<PReg> for Reg {
227    #[inline]
228    fn from(p: PReg) -> Reg {
229        Reg(u32::from(p.0))
230    }
231}
232
233impl From<VReg> for Reg {
234    #[inline]
235    fn from(v: VReg) -> Reg {
236        Reg(v.0 | VIRT_BIT)
237    }
238}
239
240impl fmt::Debug for Reg {
241    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
242        match (self.as_phys(), self.as_virt()) {
243            (Some(p), _) => fmt::Debug::fmt(&p, f),
244            (_, Some(v)) => fmt::Debug::fmt(&v, f),
245            _ => Ok(()),
246        }
247    }
248}
249
250/// A register class: the set of physical registers a value may live in, and
251/// the type of a virtual register. An index into the target's class table.
252///
253/// # Examples
254///
255/// ```
256/// use backend_lang::x86_64::{self, GPR, RAX, XMM0};
257///
258/// let gpr = x86_64::TARGET.class(GPR);
259/// assert_eq!(gpr.name(), "gpr");
260/// assert!(gpr.regs().contains(RAX));
261/// assert!(!gpr.regs().contains(XMM0));
262/// ```
263#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
264pub struct RegClass(u8);
265
266impl RegClass {
267    /// The class with index `index` (whether the target has it is checked
268    /// where it is used).
269    ///
270    /// # Examples
271    ///
272    /// ```
273    /// use backend_lang::RegClass;
274    /// use backend_lang::x86_64::GPR;
275    ///
276    /// assert_eq!(RegClass::new(0), GPR);
277    /// ```
278    #[inline]
279    #[must_use]
280    pub const fn new(index: u8) -> RegClass {
281        RegClass(index)
282    }
283
284    /// The class's index in the target's class table.
285    ///
286    /// # Examples
287    ///
288    /// ```
289    /// use backend_lang::x86_64::VEC;
290    ///
291    /// assert_eq!(VEC.index(), 1);
292    /// ```
293    #[inline]
294    #[must_use]
295    pub const fn index(self) -> usize {
296        self.0 as usize
297    }
298}
299
300impl fmt::Debug for RegClass {
301    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
302        write!(f, "class{}", self.0)
303    }
304}
305
306/// A set of physical registers: 128 bits, one per [`PReg`] index.
307///
308/// Used for class membership, allocatable sets, callee- and caller-saved
309/// sets, and per-instruction clobbers. Every operation is a few word
310/// operations; iteration yields registers in index order.
311///
312/// # Examples
313///
314/// ```
315/// use backend_lang::RegSet;
316/// use backend_lang::x86_64::{RAX, RCX, RDX};
317///
318/// let set = RegSet::EMPTY.with(RAX).with(RDX);
319/// assert!(set.contains(RDX));
320/// assert!(!set.contains(RCX));
321/// assert_eq!(set.iter().collect::<Vec<_>>(), [RAX, RDX]);
322/// assert_eq!(set.len(), 2);
323/// ```
324#[derive(Clone, Copy, PartialEq, Eq, Hash, Default)]
325pub struct RegSet([u64; 2]);
326
327impl RegSet {
328    /// The empty set.
329    pub const EMPTY: RegSet = RegSet([0, 0]);
330
331    /// The set holding exactly the registers in `regs`.
332    ///
333    /// # Examples
334    ///
335    /// ```
336    /// use backend_lang::RegSet;
337    /// use backend_lang::x86_64::{R11, RCX};
338    ///
339    /// let set = RegSet::of(&[RCX, R11]);
340    /// assert!(set.contains(R11));
341    /// ```
342    #[must_use]
343    pub const fn of(regs: &[PReg]) -> RegSet {
344        let mut set = RegSet::EMPTY;
345        let mut i = 0;
346        while i < regs.len() {
347            set = set.with(regs[i]);
348            i += 1;
349        }
350        set
351    }
352
353    /// The set with `reg` added.
354    ///
355    /// # Examples
356    ///
357    /// ```
358    /// use backend_lang::RegSet;
359    /// use backend_lang::x86_64::RBX;
360    ///
361    /// assert!(RegSet::EMPTY.with(RBX).contains(RBX));
362    /// ```
363    #[inline]
364    #[must_use]
365    pub const fn with(self, reg: PReg) -> RegSet {
366        let i = reg.index();
367        let mut words = self.0;
368        words[i >> 6] |= 1 << (i & 63);
369        RegSet(words)
370    }
371
372    /// The set with `reg` removed.
373    ///
374    /// # Examples
375    ///
376    /// ```
377    /// use backend_lang::RegSet;
378    /// use backend_lang::x86_64::RBX;
379    ///
380    /// assert!(RegSet::of(&[RBX]).without(RBX).is_empty());
381    /// ```
382    #[inline]
383    #[must_use]
384    pub const fn without(self, reg: PReg) -> RegSet {
385        let i = reg.index();
386        let mut words = self.0;
387        words[i >> 6] &= !(1 << (i & 63));
388        RegSet(words)
389    }
390
391    /// Whether `reg` is in the set.
392    ///
393    /// # Examples
394    ///
395    /// ```
396    /// use backend_lang::RegSet;
397    /// use backend_lang::x86_64::{RAX, RBX};
398    ///
399    /// assert!(RegSet::of(&[RAX]).contains(RAX));
400    /// assert!(!RegSet::of(&[RAX]).contains(RBX));
401    /// ```
402    #[inline]
403    #[must_use]
404    pub const fn contains(self, reg: PReg) -> bool {
405        let i = reg.index();
406        self.0[i >> 6] & (1 << (i & 63)) != 0
407    }
408
409    /// The registers in either set.
410    ///
411    /// # Examples
412    ///
413    /// ```
414    /// use backend_lang::RegSet;
415    /// use backend_lang::x86_64::{RAX, RBX};
416    ///
417    /// assert_eq!(RegSet::of(&[RAX]).union(RegSet::of(&[RBX])).len(), 2);
418    /// ```
419    #[inline]
420    #[must_use]
421    pub const fn union(self, other: RegSet) -> RegSet {
422        RegSet([self.0[0] | other.0[0], self.0[1] | other.0[1]])
423    }
424
425    /// The registers in both sets.
426    ///
427    /// # Examples
428    ///
429    /// ```
430    /// use backend_lang::RegSet;
431    /// use backend_lang::x86_64::{RAX, RBX};
432    ///
433    /// let a = RegSet::of(&[RAX, RBX]);
434    /// assert_eq!(a.intersect(RegSet::of(&[RBX])), RegSet::of(&[RBX]));
435    /// ```
436    #[inline]
437    #[must_use]
438    pub const fn intersect(self, other: RegSet) -> RegSet {
439        RegSet([self.0[0] & other.0[0], self.0[1] & other.0[1]])
440    }
441
442    /// The registers in `self` but not in `other`.
443    ///
444    /// # Examples
445    ///
446    /// ```
447    /// use backend_lang::RegSet;
448    /// use backend_lang::x86_64::{RAX, RBX};
449    ///
450    /// let a = RegSet::of(&[RAX, RBX]);
451    /// assert_eq!(a.difference(RegSet::of(&[RAX])), RegSet::of(&[RBX]));
452    /// ```
453    #[inline]
454    #[must_use]
455    pub const fn difference(self, other: RegSet) -> RegSet {
456        RegSet([self.0[0] & !other.0[0], self.0[1] & !other.0[1]])
457    }
458
459    /// Whether the set is empty.
460    ///
461    /// # Examples
462    ///
463    /// ```
464    /// use backend_lang::RegSet;
465    ///
466    /// assert!(RegSet::EMPTY.is_empty());
467    /// ```
468    #[inline]
469    #[must_use]
470    pub const fn is_empty(self) -> bool {
471        self.0[0] == 0 && self.0[1] == 0
472    }
473
474    /// The number of registers in the set.
475    ///
476    /// # Examples
477    ///
478    /// ```
479    /// use backend_lang::x86_64::{self, GPR};
480    ///
481    /// assert_eq!(x86_64::TARGET.class(GPR).regs().len(), 16);
482    /// ```
483    #[inline]
484    #[must_use]
485    pub const fn len(self) -> usize {
486        (self.0[0].count_ones() + self.0[1].count_ones()) as usize
487    }
488
489    /// The lowest-numbered register in the set.
490    ///
491    /// # Examples
492    ///
493    /// ```
494    /// use backend_lang::RegSet;
495    /// use backend_lang::x86_64::{RCX, R9};
496    ///
497    /// assert_eq!(RegSet::of(&[R9, RCX]).first(), Some(RCX));
498    /// assert_eq!(RegSet::EMPTY.first(), None);
499    /// ```
500    #[inline]
501    #[must_use]
502    pub const fn first(self) -> Option<PReg> {
503        if self.0[0] != 0 {
504            Some(PReg::from_index(self.0[0].trailing_zeros() as u8))
505        } else if self.0[1] != 0 {
506            Some(PReg::from_index(64 + self.0[1].trailing_zeros() as u8))
507        } else {
508            None
509        }
510    }
511
512    /// The registers in the set, in index order.
513    ///
514    /// # Examples
515    ///
516    /// ```
517    /// use backend_lang::RegSet;
518    /// use backend_lang::x86_64::{RAX, R15};
519    ///
520    /// let v: Vec<_> = RegSet::of(&[R15, RAX]).iter().collect();
521    /// assert_eq!(v, [RAX, R15]);
522    /// ```
523    #[must_use]
524    pub fn iter(self) -> RegSetIter {
525        RegSetIter(self)
526    }
527}
528
529impl fmt::Debug for RegSet {
530    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
531        f.debug_set().entries(self.iter()).finish()
532    }
533}
534
535impl FromIterator<PReg> for RegSet {
536    fn from_iter<I: IntoIterator<Item = PReg>>(iter: I) -> RegSet {
537        iter.into_iter().fold(RegSet::EMPTY, RegSet::with)
538    }
539}
540
541/// The registers of a [`RegSet`], in index order. Made by [`RegSet::iter`].
542///
543/// # Examples
544///
545/// ```
546/// use backend_lang::RegSet;
547/// use backend_lang::x86_64::RDX;
548///
549/// let mut it = RegSet::of(&[RDX]).iter();
550/// assert_eq!(it.next(), Some(RDX));
551/// assert_eq!(it.next(), None);
552/// ```
553#[derive(Clone, Debug)]
554pub struct RegSetIter(RegSet);
555
556impl Iterator for RegSetIter {
557    type Item = PReg;
558
559    #[inline]
560    fn next(&mut self) -> Option<PReg> {
561        let first = self.0.first()?;
562        self.0 = self.0.without(first);
563        Some(first)
564    }
565
566    fn size_hint(&self) -> (usize, Option<usize>) {
567        let n = self.0.len();
568        (n, Some(n))
569    }
570}
571
572impl ExactSizeIterator for RegSetIter {}
573
574#[cfg(test)]
575mod tests {
576    use alloc::vec::Vec;
577
578    use super::*;
579
580    #[test]
581    fn test_reg_packing_round_trips_both_kinds() {
582        for i in [0u8, 1, 15, 127] {
583            let p = PReg::from_index(i);
584            assert_eq!(Reg::from(p).as_phys(), Some(p));
585            assert_eq!(Reg::from(p).as_virt(), None);
586        }
587        for i in [0u32, 1, 1 << 20, VIRT_MASK] {
588            let v = VReg::from_index(i);
589            assert_eq!(Reg::from(v).as_virt(), Some(v));
590            assert_eq!(Reg::from(v).as_phys(), None);
591            assert!(Reg::from(v).is_virtual());
592        }
593    }
594
595    #[test]
596    fn test_regset_high_word_and_iteration_order() {
597        let regs: Vec<PReg> = [0u8, 63, 64, 100, 127]
598            .iter()
599            .map(|&i| PReg::from_index(i))
600            .collect();
601        let set: RegSet = regs.iter().copied().collect();
602        assert_eq!(set.len(), 5);
603        assert_eq!(set.iter().collect::<Vec<_>>(), regs);
604        assert_eq!(set.iter().len(), 5);
605        assert_eq!(set.without(regs[0]).first(), Some(regs[1]));
606        let high = RegSet::of(&[PReg::from_index(100)]);
607        assert_eq!(high.first(), Some(PReg::from_index(100)));
608        assert!(set.difference(set).is_empty());
609        assert_eq!(set.intersect(high), high);
610    }
611
612    #[test]
613    fn test_preg_new_bounds() {
614        assert!(PReg::new(127).is_some());
615        assert!(PReg::new(128).is_none());
616        assert!(PReg::new(usize::MAX).is_none());
617    }
618}
backend_lang/regs.rs

backend_lang/
regs.rs
