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