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::cfg::CFGInfo;
17use crate::ssa::validate_ssa;
18use crate::{Function, MachineEnv, Output, PReg, ProgPoint, RegAllocError, RegClass};
19use std::collections::HashMap;
20
21pub(crate) mod data_structures;
22pub use data_structures::Stats;
23use data_structures::*;
24pub(crate) mod reg_traversal;
25use reg_traversal::*;
26pub(crate) mod requirement;
27use requirement::*;
28pub(crate) mod redundant_moves;
29use redundant_moves::*;
30pub(crate) mod liveranges;
31use liveranges::*;
32pub(crate) mod merge;
33pub(crate) mod process;
34use process::*;
35use smallvec::smallvec;
36pub(crate) mod dump;
37pub(crate) mod moves;
38pub(crate) mod spill;
39pub(crate) mod stackmap;
40
41impl<'a, F: Function> Env<'a, F> {
42    pub(crate) fn new(
43        func: &'a F,
44        env: &'a MachineEnv,
45        cfginfo: CFGInfo,
46        annotations_enabled: bool,
47    ) -> Self {
48        let n = func.num_insts();
49        Self {
50            func,
51            env,
52            cfginfo,
53
54            liveins: Vec::with_capacity(func.num_blocks()),
55            liveouts: Vec::with_capacity(func.num_blocks()),
56            blockparam_outs: vec![],
57            blockparam_ins: vec![],
58            bundles: Vec::with_capacity(n),
59            ranges: Vec::with_capacity(4 * n),
60            spillsets: Vec::with_capacity(n),
61            vregs: Vec::with_capacity(n),
62            pregs: vec![],
63            allocation_queue: PrioQueue::new(),
64            safepoints: vec![],
65            safepoints_per_vreg: HashMap::new(),
66            spilled_bundles: vec![],
67            spillslots: vec![],
68            slots_by_size: vec![],
69            allocated_bundle_count: 0,
70
71            extra_spillslots_by_class: [smallvec![], smallvec![]],
72            preferred_victim_by_class: [PReg::invalid(), PReg::invalid()],
73
74            prog_move_srcs: Vec::with_capacity(n / 2),
75            prog_move_dsts: Vec::with_capacity(n / 2),
76            prog_move_merges: Vec::with_capacity(n / 2),
77
78            multi_fixed_reg_fixups: vec![],
79            inserted_moves: vec![],
80            edits: Vec::with_capacity(n),
81            allocs: Vec::with_capacity(4 * n),
82            inst_alloc_offsets: vec![],
83            num_spillslots: 0,
84            safepoint_slots: vec![],
85            debug_locations: vec![],
86
87            stats: Stats::default(),
88
89            debug_annotations: std::collections::HashMap::new(),
90            annotations_enabled,
91
92            conflict_set: Default::default(),
93        }
94    }
95
96    pub(crate) fn init(&mut self) -> Result<(), RegAllocError> {
97        self.create_pregs_and_vregs();
98        self.compute_liveness()?;
99        self.build_liveranges();
100        self.fixup_multi_fixed_vregs();
101        self.merge_vreg_bundles();
102        self.queue_bundles();
103        if trace_enabled!() {
104            self.dump_state();
105        }
106        Ok(())
107    }
108
109    pub(crate) fn run(&mut self) -> Result<(), RegAllocError> {
110        self.process_bundles()?;
111        self.try_allocating_regs_for_spilled_bundles();
112        self.allocate_spillslots();
113        self.apply_allocations_and_insert_moves();
114        self.resolve_inserted_moves();
115        self.compute_stackmaps();
116        Ok(())
117    }
118}
119
120pub fn run<F: Function>(
121    func: &F,
122    mach_env: &MachineEnv,
123    enable_annotations: bool,
124    enable_ssa_checker: bool,
125) -> Result<Output, RegAllocError> {
126    let cfginfo = CFGInfo::new(func)?;
127
128    if enable_ssa_checker {
129        validate_ssa(func, &cfginfo)?;
130    }
131
132    let mut env = Env::new(func, mach_env, cfginfo, enable_annotations);
133    env.init()?;
134
135    env.run()?;
136
137    if enable_annotations {
138        env.dump_results();
139    }
140
141    Ok(Output {
142        edits: env
143            .edits
144            .into_iter()
145            .map(|(pos_prio, edit)| (pos_prio.pos, edit))
146            .collect(),
147        allocs: env.allocs,
148        inst_alloc_offsets: env.inst_alloc_offsets,
149        num_spillslots: env.num_spillslots as usize,
150        debug_locations: env.debug_locations,
151        safepoint_slots: env.safepoint_slots,
152        stats: env.stats,
153    })
154}
regalloc2/ion/mod.rs

regalloc2/ion/
mod.rs
