celox_backend_common/
regalloc.rs

1//! Register-allocation data types and target-independent allocation helpers.
2
3use std::collections::BTreeSet;
4use std::collections::VecDeque;
5use std::fmt;
6use std::hash::Hash;
7
8use fxhash::{FxHashMap, FxHashSet};
9
10mod live_interval;
11mod parallel_copy;
12mod stack_color;
13
14pub use live_interval::{
15    LiveInterval, LiveIntervalError, LiveIntervals, LiveSegment, analyze_live_intervals,
16};
17pub use parallel_copy::{
18    CopyDestination, CopyOperation, CopyResolution, CopyResolutionError, CopyResolutionWork,
19    CopySource, ParallelCopy, resolve_parallel_copies,
20};
21pub use stack_color::{StackColorError, StackSlotColoring, color_stack_slots};
22
23/// A physical register that can be stored in a compact register set.
24pub trait MachineRegister: Copy + Eq + Hash + Ord + fmt::Debug {
25    /// Stable target-defined register number in the range `0..64`.
26    fn index(self) -> u8;
27}
28
29/// Compact set for targets with at most 64 physical registers per class.
30#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
31pub struct RegisterSet(u64);
32
33impl RegisterSet {
34    pub const fn new() -> Self {
35        Self(0)
36    }
37
38    pub fn insert<R: MachineRegister>(&mut self, register: R) {
39        self.0 |= register_bit(register);
40    }
41
42    pub fn remove<R: MachineRegister>(&mut self, register: R) {
43        self.0 &= !register_bit(register);
44    }
45
46    pub fn contains<R: MachineRegister>(&self, register: &R) -> bool {
47        self.0 & register_bit(*register) != 0
48    }
49
50    pub const fn is_empty(self) -> bool {
51        self.0 == 0
52    }
53}
54
55fn register_bit<R: MachineRegister>(register: R) -> u64 {
56    1_u64
57        .checked_shl(u32::from(register.index()))
58        .expect("physical register index must be below 64")
59}
60
61/// Constraint on one machine-instruction operand.
62#[derive(Debug, Clone, Copy, PartialEq, Eq)]
63pub enum RegConstraint<R> {
64    Any,
65    Fixed(R),
66}
67
68/// Physical location used while lowering SSA edge transfers.
69#[derive(Debug, Clone, Copy, PartialEq, Eq)]
70pub enum ValueLocation<R> {
71    Register(R),
72    Stack(i32),
73    Immediate(u64),
74}
75
76/// Target constraints attached to one instruction after legalization.
77#[derive(Debug, Clone, PartialEq, Eq)]
78pub struct InstructionConstraints<V, R> {
79    pub fixed_uses: Vec<(V, R)>,
80    pub fixed_defs: Vec<(V, R)>,
81    pub clobbers: Vec<R>,
82}
83
84impl<V, R> Default for InstructionConstraints<V, R> {
85    fn default() -> Self {
86        Self {
87            fixed_uses: Vec::new(),
88            fixed_defs: Vec::new(),
89            clobbers: Vec::new(),
90        }
91    }
92}
93
94/// Register-allocation facts for one target-owned machine instruction.
95///
96/// This deliberately contains no opcode. Backends lower their own MIR into
97/// these facts so allocation algorithms do not need a common machine IR or a
98/// target instruction enum.
99#[derive(Debug, Clone, PartialEq, Eq)]
100pub struct InstructionAllocationFacts<V, R> {
101    pub uses: Vec<V>,
102    pub defs: Vec<V>,
103    pub constraints: InstructionConstraints<V, R>,
104    /// Hint used by allocators which perform copy coalescing.
105    pub is_copy: bool,
106}
107
108impl<V, R> Default for InstructionAllocationFacts<V, R> {
109    fn default() -> Self {
110        Self {
111            uses: Vec::new(),
112            defs: Vec::new(),
113            constraints: InstructionConstraints::default(),
114            is_copy: false,
115        }
116    }
117}
118
119/// One source of a target-MIR phi node, identified by normalized predecessor
120/// block index rather than a backend-specific block identifier.
121#[derive(Debug, Clone, Copy, PartialEq, Eq)]
122pub struct PhiSource<V> {
123    pub predecessor: usize,
124    pub value: V,
125}
126
127/// Register-allocation facts for one target-MIR phi node.
128#[derive(Debug, Clone, PartialEq, Eq)]
129pub struct PhiAllocationFacts<V> {
130    pub destination: V,
131    pub sources: Vec<PhiSource<V>>,
132}
133
134/// Register-allocation facts for one normalized target-MIR basic block.
135#[derive(Debug, Clone, PartialEq, Eq)]
136pub struct BlockAllocationFacts<V, R> {
137    pub successors: Vec<usize>,
138    pub phis: Vec<PhiAllocationFacts<V>>,
139    pub instructions: Vec<InstructionAllocationFacts<V, R>>,
140}
141
142/// Target-independent input boundary for register-allocation analyses.
143///
144/// x86 and AArch64 retain separate MIR instruction types and optimization
145/// pipelines. Each backend projects its final virtual-register MIR into this
146/// representation immediately before allocation.
147#[derive(Debug, Clone, PartialEq, Eq)]
148pub struct FunctionAllocationFacts<V, R> {
149    pub entry: usize,
150    pub blocks: Vec<BlockAllocationFacts<V, R>>,
151}
152
153/// Structural error in backend-provided register-allocation facts.
154#[derive(Debug, Clone, PartialEq, Eq)]
155pub enum AllocationFactsError<V> {
156    MissingEntry {
157        entry: usize,
158        block_count: usize,
159    },
160    MissingSuccessor {
161        block: usize,
162        successor: usize,
163        block_count: usize,
164    },
165    MissingPhiPredecessor {
166        block: usize,
167        predecessor: usize,
168        value: V,
169    },
170    FixedUseIsNotUse {
171        block: usize,
172        instruction: usize,
173        value: V,
174    },
175    FixedDefIsNotDef {
176        block: usize,
177        instruction: usize,
178        value: V,
179    },
180}
181
182impl<V> fmt::Display for AllocationFactsError<V>
183where
184    V: fmt::Debug,
185{
186    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
187        match self {
188            Self::MissingEntry { entry, block_count } => write!(
189                formatter,
190                "allocation entry block {entry} is outside {block_count} blocks"
191            ),
192            Self::MissingSuccessor {
193                block,
194                successor,
195                block_count,
196            } => write!(
197                formatter,
198                "allocation block {block} has successor {successor} outside {block_count} blocks"
199            ),
200            Self::MissingPhiPredecessor {
201                block,
202                predecessor,
203                value,
204            } => write!(
205                formatter,
206                "allocation phi for {value:?} in block {block} names non-predecessor block {predecessor}"
207            ),
208            Self::FixedUseIsNotUse {
209                block,
210                instruction,
211                value,
212            } => write!(
213                formatter,
214                "fixed-use value {value:?} is not a use of allocation block {block} instruction {instruction}"
215            ),
216            Self::FixedDefIsNotDef {
217                block,
218                instruction,
219                value,
220            } => write!(
221                formatter,
222                "fixed-def value {value:?} is not a definition of allocation block {block} instruction {instruction}"
223            ),
224        }
225    }
226}
227
228impl<V> std::error::Error for AllocationFactsError<V> where V: fmt::Debug {}
229
230impl<V, R> FunctionAllocationFacts<V, R>
231where
232    V: Copy + Eq + fmt::Debug,
233{
234    /// Verify only target-independent shape invariants. Opcode legality and
235    /// register-class rules remain the responsibility of the owning backend.
236    pub fn verify(&self) -> Result<(), AllocationFactsError<V>> {
237        let block_count = self.blocks.len();
238        if self.entry >= block_count {
239            return Err(AllocationFactsError::MissingEntry {
240                entry: self.entry,
241                block_count,
242            });
243        }
244
245        let mut predecessors = vec![Vec::new(); block_count];
246        for (block_index, block) in self.blocks.iter().enumerate() {
247            for &successor in &block.successors {
248                let Some(successor_predecessors) = predecessors.get_mut(successor) else {
249                    return Err(AllocationFactsError::MissingSuccessor {
250                        block: block_index,
251                        successor,
252                        block_count,
253                    });
254                };
255                successor_predecessors.push(block_index);
256            }
257        }
258
259        for (block_index, block) in self.blocks.iter().enumerate() {
260            for phi in &block.phis {
261                for source in &phi.sources {
262                    if !predecessors[block_index].contains(&source.predecessor) {
263                        return Err(AllocationFactsError::MissingPhiPredecessor {
264                            block: block_index,
265                            predecessor: source.predecessor,
266                            value: source.value,
267                        });
268                    }
269                }
270            }
271            for (instruction_index, instruction) in block.instructions.iter().enumerate() {
272                for &(value, _) in &instruction.constraints.fixed_uses {
273                    if !instruction.uses.contains(&value) {
274                        return Err(AllocationFactsError::FixedUseIsNotUse {
275                            block: block_index,
276                            instruction: instruction_index,
277                            value,
278                        });
279                    }
280                }
281                for &(value, _) in &instruction.constraints.fixed_defs {
282                    if !instruction.defs.contains(&value) {
283                        return Err(AllocationFactsError::FixedDefIsNotDef {
284                            block: block_index,
285                            instruction: instruction_index,
286                            value,
287                        });
288                    }
289                }
290            }
291        }
292        Ok(())
293    }
294}
295
296/// Next-use distances at target-MIR block boundaries.
297///
298/// Distances are measured in target instructions. Loop-exit paths receive a
299/// deliberately large penalty so an allocator prefers uses within the loop.
300#[derive(Debug, Clone, PartialEq, Eq)]
301pub struct NextUseDistances<V> {
302    entries: Vec<(V, u32)>,
303}
304
305impl<V> Default for NextUseDistances<V> {
306    fn default() -> Self {
307        Self {
308            entries: Vec::new(),
309        }
310    }
311}
312
313impl<V: Ord> NextUseDistances<V> {
314    fn from_min_entries(mut entries: Vec<(V, u32)>) -> Self {
315        entries.sort_unstable_by(|left, right| left.0.cmp(&right.0));
316        let mut merged: Vec<(V, u32)> = Vec::with_capacity(entries.len());
317        for (value, distance) in entries {
318            if let Some((previous_value, previous_distance)) = merged.last_mut()
319                && *previous_value == value
320            {
321                *previous_distance = (*previous_distance).min(distance);
322            } else {
323                merged.push((value, distance));
324            }
325        }
326        Self { entries: merged }
327    }
328
329    pub fn get(&self, value: &V) -> Option<&u32> {
330        self.entries
331            .binary_search_by(|(candidate, _)| candidate.cmp(value))
332            .ok()
333            .map(|index| &self.entries[index].1)
334    }
335
336    pub fn contains_key(&self, value: &V) -> bool {
337        self.get(value).is_some()
338    }
339
340    pub fn len(&self) -> usize {
341        self.entries.len()
342    }
343
344    pub fn is_empty(&self) -> bool {
345        self.entries.is_empty()
346    }
347
348    pub fn iter(&self) -> NextUseDistanceIter<'_, V> {
349        NextUseDistanceIter(self.entries.iter())
350    }
351
352    pub fn keys(&self) -> NextUseDistanceKeys<'_, V> {
353        NextUseDistanceKeys(self.entries.iter())
354    }
355}
356
357impl<V: Ord> std::ops::Index<&V> for NextUseDistances<V> {
358    type Output = u32;
359
360    fn index(&self, value: &V) -> &Self::Output {
361        self.get(value).expect("next-use distance key must exist")
362    }
363}
364
365pub struct NextUseDistanceIter<'a, V>(std::slice::Iter<'a, (V, u32)>);
366
367impl<'a, V> Iterator for NextUseDistanceIter<'a, V> {
368    type Item = (&'a V, &'a u32);
369
370    fn next(&mut self) -> Option<Self::Item> {
371        self.0.next().map(|(value, distance)| (value, distance))
372    }
373}
374
375pub struct NextUseDistanceKeys<'a, V>(std::slice::Iter<'a, (V, u32)>);
376
377impl<'a, V> Iterator for NextUseDistanceKeys<'a, V> {
378    type Item = &'a V;
379
380    fn next(&mut self) -> Option<Self::Item> {
381        self.0.next().map(|(value, _)| value)
382    }
383}
384
385impl<'a, V: Ord> IntoIterator for &'a NextUseDistances<V> {
386    type Item = (&'a V, &'a u32);
387    type IntoIter = NextUseDistanceIter<'a, V>;
388
389    fn into_iter(self) -> Self::IntoIter {
390        self.iter()
391    }
392}
393
394#[derive(Debug, Clone)]
395pub struct NextUseAnalysis<V> {
396    pub entry_distances: Vec<NextUseDistances<V>>,
397    pub exit_distances: Vec<NextUseDistances<V>>,
398    pub predecessors: Vec<Vec<usize>>,
399    pub backedge_successors: Vec<Vec<usize>>,
400}
401
402/// Large edge length for a DFS backedge. This matches the established native
403/// allocator's heuristic and keeps a use behind a loop farther away than uses
404/// in the loop body.
405const LOOP_EXIT_LENGTH: u32 = 100_000;
406
407/// Compute liveness and global next-use distances solely from allocator facts.
408pub fn analyze_next_uses<V, R>(
409    facts: &FunctionAllocationFacts<V, R>,
410) -> Result<NextUseAnalysis<V>, AllocationFactsError<V>>
411where
412    V: Copy + Eq + Hash + Ord + fmt::Debug,
413{
414    facts.verify()?;
415    let block_count = facts.blocks.len();
416    let successors = facts
417        .blocks
418        .iter()
419        .map(|block| block.successors.clone())
420        .collect::<Vec<_>>();
421    let mut predecessors = vec![Vec::new(); block_count];
422    for (block, block_successors) in successors.iter().enumerate() {
423        for &successor in block_successors {
424            predecessors[successor].push(block);
425        }
426    }
427    let backedge_successors = compute_backedge_successors(&successors);
428    let backedge_edges = successors
429        .iter()
430        .enumerate()
431        .map(|(block, block_successors)| {
432            block_successors
433                .iter()
434                .map(|successor| backedge_successors[block].contains(successor))
435                .collect::<Vec<_>>()
436        })
437        .collect::<Vec<_>>();
438    let phi_edge_uses = compute_phi_edge_uses(facts, &successors);
439    let transfers = compute_block_transfers(facts);
440
441    let mut entry_distances = vec![NextUseDistances::default(); block_count];
442    let mut exit_distances = vec![NextUseDistances::default(); block_count];
443    let mut worklist = (0..block_count).rev().collect::<VecDeque<_>>();
444    let mut in_worklist = vec![true; block_count];
445    while let Some(block) = worklist.pop_front() {
446        in_worklist[block] = false;
447        let (new_entry, new_exit) = compute_block_distances(
448            block,
449            &successors,
450            &backedge_edges,
451            &phi_edge_uses,
452            &transfers,
453            &entry_distances,
454        );
455        if new_entry != entry_distances[block] || new_exit != exit_distances[block] {
456            entry_distances[block] = new_entry;
457            exit_distances[block] = new_exit;
458            for &predecessor in &predecessors[block] {
459                if !in_worklist[predecessor] {
460                    worklist.push_back(predecessor);
461                    in_worklist[predecessor] = true;
462                }
463            }
464        }
465    }
466
467    Ok(NextUseAnalysis {
468        entry_distances,
469        exit_distances,
470        predecessors,
471        backedge_successors,
472    })
473}
474
475struct BlockTransfer<V> {
476    block_len: u32,
477    defs: FxHashSet<V>,
478    local_uses: Vec<(V, u32)>,
479}
480
481fn compute_block_transfers<V, R>(facts: &FunctionAllocationFacts<V, R>) -> Vec<BlockTransfer<V>>
482where
483    V: Copy + Eq + Hash + Ord,
484{
485    facts
486        .blocks
487        .iter()
488        .map(|block| {
489            let mut defs = FxHashSet::default();
490            defs.reserve(block.phis.len() + block.instructions.len());
491            defs.extend(block.phis.iter().map(|phi| phi.destination));
492            let mut local_uses = Vec::new();
493            for (instruction_index, instruction) in block.instructions.iter().enumerate() {
494                for &definition in &instruction.defs {
495                    defs.insert(definition);
496                }
497                let position = instruction_index as u32;
498                for &used in &instruction.uses {
499                    if !defs.contains(&used) {
500                        local_uses.push((used, position));
501                    }
502                }
503            }
504            local_uses.sort_unstable_by_key(|(value, position)| (*value, *position));
505            local_uses.dedup_by_key(|(value, _)| *value);
506            BlockTransfer {
507                block_len: block.instructions.len() as u32,
508                defs,
509                local_uses,
510            }
511        })
512        .collect()
513}
514
515fn compute_phi_edge_uses<V, R>(
516    facts: &FunctionAllocationFacts<V, R>,
517    successors: &[Vec<usize>],
518) -> Vec<Vec<Vec<V>>>
519where
520    V: Copy,
521{
522    successors
523        .iter()
524        .enumerate()
525        .map(|(predecessor, block_successors)| {
526            block_successors
527                .iter()
528                .map(|&successor| {
529                    facts.blocks[successor]
530                        .phis
531                        .iter()
532                        .flat_map(|phi| {
533                            phi.sources
534                                .iter()
535                                .filter(move |source| source.predecessor == predecessor)
536                                .map(|source| source.value)
537                        })
538                        .collect()
539                })
540                .collect()
541        })
542        .collect()
543}
544
545fn compute_block_distances<V>(
546    block: usize,
547    successors: &[Vec<usize>],
548    backedge_edges: &[Vec<bool>],
549    phi_edge_uses: &[Vec<Vec<V>>],
550    transfers: &[BlockTransfer<V>],
551    entry_distances: &[NextUseDistances<V>],
552) -> (NextUseDistances<V>, NextUseDistances<V>)
553where
554    V: Copy + Hash + Ord,
555{
556    let transfer = &transfers[block];
557    let exit_capacity = successors[block]
558        .iter()
559        .map(|&successor| entry_distances[successor].len())
560        .sum::<usize>()
561        + phi_edge_uses[block].iter().map(Vec::len).sum::<usize>();
562    let mut new_exit_entries = Vec::with_capacity(exit_capacity);
563    for (edge, &successor) in successors[block].iter().enumerate() {
564        let edge_length = if backedge_edges[block][edge] {
565            LOOP_EXIT_LENGTH
566        } else {
567            0
568        };
569        for (&value, &distance) in &entry_distances[successor] {
570            let distance = distance.saturating_add(edge_length);
571            new_exit_entries.push((value, distance));
572        }
573        for &value in &phi_edge_uses[block][edge] {
574            new_exit_entries.push((value, edge_length));
575        }
576    }
577    let new_exit = NextUseDistances::from_min_entries(new_exit_entries);
578
579    let mut new_entry_entries = Vec::with_capacity(new_exit.len() + transfer.local_uses.len());
580    for (&value, &distance) in &new_exit {
581        if !transfer.defs.contains(&value) {
582            new_entry_entries.push((value, transfer.block_len.saturating_add(distance)));
583        }
584    }
585    new_entry_entries.extend(transfer.local_uses.iter().copied());
586    let new_entry = NextUseDistances::from_min_entries(new_entry_entries);
587    (new_entry, new_exit)
588}
589
590fn compute_backedge_successors(successors: &[Vec<usize>]) -> Vec<Vec<usize>> {
591    #[derive(Clone, Copy, PartialEq, Eq)]
592    enum Color {
593        White,
594        Gray,
595        Black,
596    }
597
598    let mut colors = vec![Color::White; successors.len()];
599    let mut backedges = vec![Vec::new(); successors.len()];
600    for root in 0..successors.len() {
601        if colors[root] != Color::White {
602            continue;
603        }
604        colors[root] = Color::Gray;
605        let mut stack = vec![(root, 0usize)];
606        while let Some((node, next_successor)) = stack.last_mut() {
607            if *next_successor == successors[*node].len() {
608                colors[*node] = Color::Black;
609                stack.pop();
610                continue;
611            }
612            let successor = successors[*node][*next_successor];
613            *next_successor += 1;
614            match colors[successor] {
615                Color::White => {
616                    colors[successor] = Color::Gray;
617                    stack.push((successor, 0));
618                }
619                Color::Gray => backedges[*node].push(successor),
620                Color::Black => {}
621            }
622        }
623    }
624    backedges
625}
626
627/// One inclusive live range in a linearized machine function.
628#[derive(Debug, Clone, Copy, PartialEq, Eq)]
629pub struct LiveRange<V> {
630    pub value: V,
631    pub start: u32,
632    pub end: u32,
633}
634
635/// Register assignment returned by [`allocate_linear_scan`].
636#[derive(Debug, Clone, PartialEq, Eq)]
637pub struct Allocation<V: Eq + Hash, R> {
638    assignments: FxHashMap<V, R>,
639}
640
641impl<V: Eq + Hash, R: Copy> Allocation<V, R> {
642    pub fn get(&self, value: V) -> Option<R> {
643        self.assignments.get(&value).copied()
644    }
645
646    pub fn iter(&self) -> impl Iterator<Item = (&V, &R)> {
647        self.assignments.iter()
648    }
649}
650
651/// Failure from target-independent linear-scan allocation.
652#[derive(Debug, Clone, PartialEq, Eq)]
653pub enum LinearScanError<V> {
654    EmptyRegisterFile,
655    DuplicateValue(V),
656    InvalidRange(LiveRange<V>),
657    RegisterPressure { value: V, point: u32 },
658}
659
660impl<V: fmt::Debug> fmt::Display for LinearScanError<V> {
661    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
662        match self {
663            Self::EmptyRegisterFile => formatter.write_str("target has no allocatable registers"),
664            Self::DuplicateValue(value) => write!(formatter, "duplicate live range for {value:?}"),
665            Self::InvalidRange(range) => write!(
666                formatter,
667                "invalid live range {:?}: {}..{}",
668                range.value, range.start, range.end
669            ),
670            Self::RegisterPressure { value, point } => write!(
671                formatter,
672                "no register available for {value:?} at program point {point}"
673            ),
674        }
675    }
676}
677
678impl<V: fmt::Debug> std::error::Error for LinearScanError<V> {}
679
680/// Allocate non-spilling live ranges using a deterministic linear scan.
681///
682/// This is the bootstrap allocator for new native targets. The mature SSA
683/// splitter remains available to x86 while its target hooks are separated;
684/// both allocators share the physical-register and constraint model here.
685pub fn allocate_linear_scan<V, R>(
686    ranges: &[LiveRange<V>],
687    allocatable: &[R],
688) -> Result<Allocation<V, R>, LinearScanError<V>>
689where
690    V: Copy + Eq + Hash + Ord + fmt::Debug,
691    R: MachineRegister,
692{
693    if allocatable.is_empty() {
694        return Err(LinearScanError::EmptyRegisterFile);
695    }
696
697    let mut ordered = ranges.to_vec();
698    ordered.sort_unstable_by_key(|range| (range.start, range.end, range.value));
699    let mut seen = BTreeSet::new();
700    for range in &ordered {
701        if range.start > range.end {
702            return Err(LinearScanError::InvalidRange(*range));
703        }
704        if !seen.insert(range.value) {
705            return Err(LinearScanError::DuplicateValue(range.value));
706        }
707    }
708
709    let mut active = Vec::<(u32, V, R)>::new();
710    let mut assignments = FxHashMap::with_capacity_and_hasher(ordered.len(), Default::default());
711    for range in ordered {
712        active.retain(|(end, _, _)| *end >= range.start);
713        let register = allocatable
714            .iter()
715            .copied()
716            .find(|candidate| active.iter().all(|(_, _, used)| used != candidate))
717            .ok_or(LinearScanError::RegisterPressure {
718                value: range.value,
719                point: range.start,
720            })?;
721        assignments.insert(range.value, register);
722        active.push((range.end, range.value, register));
723        active.sort_unstable_by_key(|(end, value, register)| (*end, *value, register.index()));
724    }
725
726    Ok(Allocation { assignments })
727}
728
729#[cfg(test)]
730mod tests {
731    use super::*;
732
733    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
734    struct Reg(u8);
735
736    impl MachineRegister for Reg {
737        fn index(self) -> u8 {
738            self.0
739        }
740    }
741
742    #[test]
743    fn register_set_supports_registers_above_x86s_range() {
744        let mut set = RegisterSet::new();
745        set.insert(Reg(30));
746        assert!(set.contains(&Reg(30)));
747        set.remove(Reg(30));
748        assert!(set.is_empty());
749    }
750
751    #[test]
752    fn linear_scan_reuses_register_after_last_use() {
753        let ranges = [
754            LiveRange {
755                value: 0,
756                start: 0,
757                end: 1,
758            },
759            LiveRange {
760                value: 1,
761                start: 2,
762                end: 3,
763            },
764        ];
765        let allocation = allocate_linear_scan(&ranges, &[Reg(9)]).unwrap();
766        assert_eq!(allocation.get(0), Some(Reg(9)));
767        assert_eq!(allocation.get(1), Some(Reg(9)));
768    }
769
770    #[test]
771    fn linear_scan_reports_pressure_without_hidden_spills() {
772        let ranges = [
773            LiveRange {
774                value: 0,
775                start: 0,
776                end: 2,
777            },
778            LiveRange {
779                value: 1,
780                start: 1,
781                end: 2,
782            },
783        ];
784        assert_eq!(
785            allocate_linear_scan(&ranges, &[Reg(9)]),
786            Err(LinearScanError::RegisterPressure { value: 1, point: 1 })
787        );
788    }
789
790    #[test]
791    fn allocation_facts_verify_without_knowing_target_opcodes() {
792        let facts = FunctionAllocationFacts {
793            entry: 0,
794            blocks: vec![
795                BlockAllocationFacts {
796                    successors: vec![1],
797                    phis: Vec::new(),
798                    instructions: vec![InstructionAllocationFacts {
799                        uses: vec![0],
800                        defs: vec![1],
801                        constraints: InstructionConstraints {
802                            fixed_uses: vec![(0, Reg(3))],
803                            fixed_defs: vec![(1, Reg(4))],
804                            clobbers: vec![Reg(5)],
805                        },
806                        is_copy: false,
807                    }],
808                },
809                BlockAllocationFacts {
810                    successors: Vec::new(),
811                    phis: vec![PhiAllocationFacts {
812                        destination: 2,
813                        sources: vec![PhiSource {
814                            predecessor: 0,
815                            value: 1,
816                        }],
817                    }],
818                    instructions: Vec::new(),
819                },
820            ],
821        };
822
823        assert_eq!(facts.verify(), Ok(()));
824        let analysis = analyze_next_uses(&facts).unwrap();
825        assert_eq!(analysis.exit_distances[0].get(&1), Some(&0));
826        assert_eq!(analysis.entry_distances[0].get(&0), Some(&0));
827    }
828
829    #[test]
830    fn allocation_facts_reject_constraints_detached_from_operands() {
831        let facts = FunctionAllocationFacts {
832            entry: 0,
833            blocks: vec![BlockAllocationFacts {
834                successors: Vec::new(),
835                phis: Vec::new(),
836                instructions: vec![InstructionAllocationFacts {
837                    uses: vec![0],
838                    defs: Vec::new(),
839                    constraints: InstructionConstraints {
840                        fixed_uses: vec![(1, Reg(3))],
841                        ..InstructionConstraints::default()
842                    },
843                    is_copy: false,
844                }],
845            }],
846        };
847
848        assert_eq!(
849            facts.verify(),
850            Err(AllocationFactsError::FixedUseIsNotUse {
851                block: 0,
852                instruction: 0,
853                value: 1,
854            })
855        );
856    }
857}
celox_backend_common/regalloc.rs

celox_backend_common/
regalloc.rs
