1 //! Register allocator context.
2 //!
3 //! The `Context` struct contains data structures that should be preserved across invocations of
4 //! the register allocator algorithm. This doesn't preserve any data between functions, but it
5 //! avoids allocating data structures independently for each function begin compiled.
6 
7 use crate::dominator_tree::DominatorTree;
8 use crate::flowgraph::ControlFlowGraph;
9 use crate::ir::Function;
10 use crate::isa::TargetIsa;
11 use crate::regalloc::branch_splitting;
12 use crate::regalloc::coalescing::Coalescing;
13 use crate::regalloc::coloring::Coloring;
14 use crate::regalloc::live_value_tracker::LiveValueTracker;
15 use crate::regalloc::liveness::Liveness;
16 use crate::regalloc::reload::Reload;
17 use crate::regalloc::safepoint::emit_stackmaps;
18 use crate::regalloc::spilling::Spilling;
19 use crate::regalloc::virtregs::VirtRegs;
20 use crate::result::CodegenResult;
21 use crate::timing;
22 use crate::topo_order::TopoOrder;
23 use crate::verifier::{
24     verify_context, verify_cssa, verify_liveness, verify_locations, VerifierErrors,
25 };
26 
27 /// Persistent memory allocations for register allocation.
28 pub struct Context {
29     liveness: Liveness,
30     virtregs: VirtRegs,
31     coalescing: Coalescing,
32     topo: TopoOrder,
33     tracker: LiveValueTracker,
34     spilling: Spilling,
35     reload: Reload,
36     coloring: Coloring,
37 }
38 
39 impl Context {
40     /// Create a new context for register allocation.
41     ///
42     /// This context should be reused for multiple functions in order to avoid repeated memory
43     /// allocations.
new() -> Self44     pub fn new() -> Self {
45         Self {
46             liveness: Liveness::new(),
47             virtregs: VirtRegs::new(),
48             coalescing: Coalescing::new(),
49             topo: TopoOrder::new(),
50             tracker: LiveValueTracker::new(),
51             spilling: Spilling::new(),
52             reload: Reload::new(),
53             coloring: Coloring::new(),
54         }
55     }
56 
57     /// Clear all data structures in this context.
clear(&mut self)58     pub fn clear(&mut self) {
59         self.liveness.clear();
60         self.virtregs.clear();
61         self.coalescing.clear();
62         self.topo.clear();
63         self.tracker.clear();
64         self.spilling.clear();
65         self.reload.clear();
66         self.coloring.clear();
67     }
68 
69     /// Current values liveness state.
liveness(&self) -> &Liveness70     pub fn liveness(&self) -> &Liveness {
71         &self.liveness
72     }
73 
74     /// Allocate registers in `func`.
75     ///
76     /// After register allocation, all values in `func` have been assigned to a register or stack
77     /// location that is consistent with instruction encoding constraints.
run( &mut self, isa: &dyn TargetIsa, func: &mut Function, cfg: &mut ControlFlowGraph, domtree: &mut DominatorTree, ) -> CodegenResult<()>78     pub fn run(
79         &mut self,
80         isa: &dyn TargetIsa,
81         func: &mut Function,
82         cfg: &mut ControlFlowGraph,
83         domtree: &mut DominatorTree,
84     ) -> CodegenResult<()> {
85         let _tt = timing::regalloc();
86         debug_assert!(domtree.is_valid());
87 
88         let mut errors = VerifierErrors::default();
89 
90         // `Liveness` and `Coloring` are self-clearing.
91         self.virtregs.clear();
92 
93         // Tracker state (dominator live sets) is actually reused between the spilling and coloring
94         // phases.
95         self.tracker.clear();
96 
97         // Pass: Split branches, add space where to add copy & regmove instructions.
98         branch_splitting::run(isa, func, cfg, domtree, &mut self.topo);
99 
100         // Pass: Liveness analysis.
101         self.liveness.compute(isa, func, cfg);
102 
103         if isa.flags().enable_verifier() {
104             let ok = verify_liveness(isa, func, cfg, &self.liveness, &mut errors).is_ok();
105 
106             if !ok {
107                 return Err(errors.into());
108             }
109         }
110 
111         // Pass: Coalesce and create Conventional SSA form.
112         self.coalescing.conventional_ssa(
113             isa,
114             func,
115             cfg,
116             domtree,
117             &mut self.liveness,
118             &mut self.virtregs,
119         );
120 
121         if isa.flags().enable_verifier() {
122             let ok = verify_context(func, cfg, domtree, isa, &mut errors).is_ok()
123                 && verify_liveness(isa, func, cfg, &self.liveness, &mut errors).is_ok()
124                 && verify_cssa(
125                     func,
126                     cfg,
127                     domtree,
128                     &self.liveness,
129                     &self.virtregs,
130                     &mut errors,
131                 )
132                 .is_ok();
133 
134             if !ok {
135                 return Err(errors.into());
136             }
137         }
138 
139         // Pass: Spilling.
140         self.spilling.run(
141             isa,
142             func,
143             domtree,
144             &mut self.liveness,
145             &self.virtregs,
146             &mut self.topo,
147             &mut self.tracker,
148         );
149 
150         if isa.flags().enable_verifier() {
151             let ok = verify_context(func, cfg, domtree, isa, &mut errors).is_ok()
152                 && verify_liveness(isa, func, cfg, &self.liveness, &mut errors).is_ok()
153                 && verify_cssa(
154                     func,
155                     cfg,
156                     domtree,
157                     &self.liveness,
158                     &self.virtregs,
159                     &mut errors,
160                 )
161                 .is_ok();
162 
163             if !ok {
164                 return Err(errors.into());
165             }
166         }
167 
168         // Pass: Reload.
169         self.reload.run(
170             isa,
171             func,
172             domtree,
173             &mut self.liveness,
174             &mut self.topo,
175             &mut self.tracker,
176         );
177 
178         if isa.flags().enable_verifier() {
179             let ok = verify_context(func, cfg, domtree, isa, &mut errors).is_ok()
180                 && verify_liveness(isa, func, cfg, &self.liveness, &mut errors).is_ok()
181                 && verify_cssa(
182                     func,
183                     cfg,
184                     domtree,
185                     &self.liveness,
186                     &self.virtregs,
187                     &mut errors,
188                 )
189                 .is_ok();
190 
191             if !ok {
192                 return Err(errors.into());
193             }
194         }
195 
196         // Pass: Coloring.
197         self.coloring.run(
198             isa,
199             func,
200             cfg,
201             domtree,
202             &mut self.liveness,
203             &mut self.tracker,
204         );
205 
206         // This function runs after register allocation has taken
207         // place, meaning values have locations assigned already.
208         if isa.flags().enable_safepoints() {
209             emit_stackmaps(func, domtree, &self.liveness, &mut self.tracker, isa);
210         } else {
211             // Make sure no references are used.
212             for val in func.dfg.values() {
213                 let ty = func.dfg.value_type(val);
214                 if ty.lane_type().is_ref() {
215                     panic!("reference types were found but safepoints were not enabled.");
216                 }
217             }
218         }
219 
220         if isa.flags().enable_verifier() {
221             let ok = verify_context(func, cfg, domtree, isa, &mut errors).is_ok()
222                 && verify_liveness(isa, func, cfg, &self.liveness, &mut errors).is_ok()
223                 && verify_locations(isa, func, cfg, Some(&self.liveness), &mut errors).is_ok()
224                 && verify_cssa(
225                     func,
226                     cfg,
227                     domtree,
228                     &self.liveness,
229                     &self.virtregs,
230                     &mut errors,
231                 )
232                 .is_ok();
233 
234             if !ok {
235                 return Err(errors.into());
236             }
237         }
238 
239         // Even if we arrive here, (non-fatal) errors might have been reported, so we
240         // must make sure absolutely nothing is wrong
241         if errors.is_empty() {
242             Ok(())
243         } else {
244             Err(errors.into())
245         }
246     }
247 }
248