regalloc2/ion/
mod.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//! Backtracking register allocator. See doc/DESIGN.md for details of
14//! its design.
15
16use crate::ssa::validate_ssa;
17use crate::{Function, MachineEnv, PReg, RegAllocError, RegClass, VecExt};
18pub(crate) mod data_structures;
19pub use data_structures::Ctx;
20pub use data_structures::Stats;
21use data_structures::*;
22pub(crate) mod reg_traversal;
23use reg_traversal::*;
24pub(crate) mod requirement;
25use requirement::*;
26pub(crate) mod redundant_moves;
27use redundant_moves::*;
28pub(crate) mod liveranges;
29use liveranges::*;
30pub(crate) mod merge;
31pub(crate) mod process;
32use process::*;
33use smallvec::smallvec;
34pub(crate) mod dump;
35pub(crate) mod moves;
36pub(crate) mod spill;
37
38impl<'a, F: Function> Env<'a, F> {
39    pub(crate) fn new(func: &'a F, env: &'a MachineEnv, ctx: &'a mut Ctx) -> Self {
40        let ninstrs = func.num_insts();
41        let nblocks = func.num_blocks();
42
43        ctx.liveins.preallocate(nblocks);
44        ctx.liveouts.preallocate(nblocks);
45        ctx.blockparam_ins.clear();
46        ctx.blockparam_outs.clear();
47        ctx.ranges.preallocate(4 * ninstrs);
48        ctx.bundles.preallocate(ninstrs);
49        ctx.spillsets.preallocate(ninstrs);
50        ctx.vregs.preallocate(ninstrs);
51        for preg in ctx.pregs.iter_mut() {
52            preg.is_stack = false;
53            preg.allocations.btree.clear();
54        }
55        ctx.allocation_queue.heap.clear();
56        ctx.spilled_bundles.clear();
57        ctx.scratch_spillset_pool
58            .extend(ctx.spillslots.drain(..).map(|mut s| {
59                s.ranges.btree.clear();
60                s.ranges
61            }));
62        ctx.slots_by_class = core::array::from_fn(|_| SpillSlotList::default());
63        ctx.extra_spillslots_by_class = core::array::from_fn(|_| smallvec![]);
64        ctx.preferred_victim_by_class = [PReg::invalid(); 3];
65        ctx.multi_fixed_reg_fixups.clear();
66        ctx.allocated_bundle_count = 0;
67        ctx.debug_annotations.clear();
68        ctx.scratch_bump
69            .get_mut()
70            .expect("we dropped all refs to this")
71            .reset();
72
73        ctx.output.allocs.preallocate(4 * ninstrs);
74        ctx.output.inst_alloc_offsets.clear();
75        ctx.output.num_spillslots = 0;
76        ctx.output.debug_locations.clear();
77        ctx.output.edits.clear();
78        ctx.output.stats = Stats::default();
79
80        Self { func, env, ctx }
81    }
82
83    pub(crate) fn init(&mut self) -> Result<(), RegAllocError> {
84        self.create_pregs_and_vregs();
85        self.compute_liveness()?;
86        self.build_liveranges()?;
87        self.fixup_multi_fixed_vregs();
88        self.merge_vreg_bundles();
89        self.queue_bundles();
90        if trace_enabled!() {
91            self.dump_state();
92        }
93        Ok(())
94    }
95
96    pub(crate) fn run(&mut self) -> Result<Edits, RegAllocError> {
97        self.process_bundles()?;
98        self.try_allocating_regs_for_spilled_bundles();
99        self.allocate_spillslots();
100        if trace_enabled!() {
101            self.dump_state();
102        }
103        let moves = self.apply_allocations_and_insert_moves();
104        Ok(self.resolve_inserted_moves(moves))
105    }
106}
107
108pub fn run<F: Function>(
109    func: &F,
110    mach_env: &MachineEnv,
111    ctx: &mut Ctx,
112    enable_annotations: bool,
113    enable_ssa_checker: bool,
114) -> Result<(), RegAllocError> {
115    ctx.cfginfo.init(func, &mut ctx.cfginfo_ctx)?;
116
117    if enable_ssa_checker {
118        validate_ssa(func, &ctx.cfginfo)?;
119    }
120
121    ctx.annotations_enabled = enable_annotations;
122    let mut env = Env::new(func, mach_env, ctx);
123    env.init()?;
124
125    let mut edits = env.run()?;
126
127    if enable_annotations {
128        env.dump_results();
129    }
130
131    ctx.output.edits.extend(edits.drain_edits());
132
133    Ok(())
134}
regalloc2/ion/mod.rs

regalloc2/ion/
mod.rs
