1 //! Register allocator coloring pass. 2 //! 3 //! The coloring pass assigns a physical register to every SSA value with a register affinity, 4 //! under the assumption that the register pressure has been lowered sufficiently by spilling and 5 //! splitting. 6 //! 7 //! # Preconditions 8 //! 9 //! The coloring pass doesn't work on arbitrary code. Certain preconditions must be satisfied: 10 //! 11 //! 1. All instructions must be legalized and assigned an encoding. The encoding recipe guides the 12 //! register assignments and provides exact constraints. 13 //! 14 //! 2. Instructions with tied operands must be in a coloring-friendly state. Specifically, the 15 //! values used by the tied operands must be killed by the instruction. This can be achieved by 16 //! inserting a `copy` to a new value immediately before the two-address instruction. 17 //! 18 //! 3. If a value is bound to more than one operand on the same instruction, the operand 19 //! constraints must be compatible. This can also be achieved by inserting copies so the 20 //! incompatible operands get different values. 21 //! 22 //! 4. The register pressure must be lowered sufficiently by inserting spill code. Register 23 //! operands are allowed to read spilled values, but each such instance must be counted as using 24 //! a register. 25 //! 26 //! 5. The code must be in Conventional SSA form. Among other things, this means that values passed 27 //! as arguments when branching to an EBB must belong to the same virtual register as the 28 //! corresponding EBB argument value. 29 //! 30 //! # Iteration order 31 //! 32 //! The SSA property guarantees that whenever the live range of two values overlap, one of the 33 //! values will be live at the definition point of the other value. If we visit the instructions in 34 //! a topological order relative to the dominance relation, we can assign colors to the values 35 //! defined by the instruction and only consider the colors of other values that are live at the 36 //! instruction. 37 //! 38 //! The first time we see a branch to an EBB, the EBB's argument values are colored to match the 39 //! registers currently holding branch argument values passed to the predecessor branch. By 40 //! visiting EBBs in a CFG topological order, we guarantee that at least one predecessor branch has 41 //! been visited before the destination EBB. Therefore, the EBB's arguments are already colored. 42 //! 43 //! The exception is the entry block whose arguments are colored from the ABI requirements. 44 45 use crate::cursor::{Cursor, EncCursor}; 46 use crate::dominator_tree::DominatorTree; 47 use crate::flowgraph::ControlFlowGraph; 48 use crate::ir::{ArgumentLoc, InstBuilder, ValueDef}; 49 use crate::ir::{Ebb, Function, Inst, InstructionData, Layout, Opcode, SigRef, Value, ValueLoc}; 50 use crate::isa::{regs_overlap, RegClass, RegInfo, RegUnit}; 51 use crate::isa::{ConstraintKind, EncInfo, OperandConstraint, RecipeConstraints, TargetIsa}; 52 use crate::packed_option::PackedOption; 53 use crate::regalloc::affinity::Affinity; 54 use crate::regalloc::diversion::RegDiversions; 55 use crate::regalloc::live_value_tracker::{LiveValue, LiveValueTracker}; 56 use crate::regalloc::liveness::Liveness; 57 use crate::regalloc::liverange::{LiveRange, LiveRangeContext}; 58 use crate::regalloc::register_set::RegisterSet; 59 use crate::regalloc::solver::{Solver, SolverError}; 60 use crate::timing; 61 use core::mem; 62 use log::debug; 63 64 /// Data structures for the coloring pass. 65 /// 66 /// These are scratch space data structures that can be reused between invocations. 67 pub struct Coloring { 68 divert: RegDiversions, 69 solver: Solver, 70 } 71 72 /// Kinds of ABI parameters. 73 enum AbiParams { 74 Parameters(SigRef), 75 Returns, 76 } 77 78 /// Bundle of references that the coloring algorithm needs. 79 /// 80 /// Some of the needed mutable references are passed around as explicit function arguments so we 81 /// can avoid many fights with the borrow checker over mutable borrows of `self`. This includes the 82 /// `Function` and `LiveValueTracker` references. 83 /// 84 /// Immutable context information and mutable references that don't need to be borrowed across 85 /// method calls should go in this struct. 86 struct Context<'a> { 87 // Current instruction as well as reference to function and ISA. 88 cur: EncCursor<'a>, 89 90 // Cached ISA information. 91 // We save it here to avoid frequent virtual function calls on the `TargetIsa` trait object. 92 reginfo: RegInfo, 93 encinfo: EncInfo, 94 95 // References to contextual data structures we need. 96 cfg: &'a ControlFlowGraph, 97 domtree: &'a DominatorTree, 98 liveness: &'a mut Liveness, 99 100 // References to working set data structures. 101 // If we need to borrow out of a data structure across a method call, it must be passed as a 102 // function argument instead, see the `LiveValueTracker` arguments. 103 divert: &'a mut RegDiversions, 104 solver: &'a mut Solver, 105 106 // Pristine set of registers that the allocator can use. 107 // This set remains immutable, we make clones. 108 usable_regs: RegisterSet, 109 110 uses_pinned_reg: bool, 111 } 112 113 impl Coloring { 114 /// Allocate scratch space data structures for the coloring pass. new() -> Self115 pub fn new() -> Self { 116 Self { 117 divert: RegDiversions::new(), 118 solver: Solver::new(), 119 } 120 } 121 122 /// Clear all data structures in this coloring pass. clear(&mut self)123 pub fn clear(&mut self) { 124 self.divert.clear(); 125 self.solver.clear(); 126 } 127 128 /// Run the coloring algorithm over `func`. run( &mut self, isa: &dyn TargetIsa, func: &mut Function, cfg: &ControlFlowGraph, domtree: &DominatorTree, liveness: &mut Liveness, tracker: &mut LiveValueTracker, )129 pub fn run( 130 &mut self, 131 isa: &dyn TargetIsa, 132 func: &mut Function, 133 cfg: &ControlFlowGraph, 134 domtree: &DominatorTree, 135 liveness: &mut Liveness, 136 tracker: &mut LiveValueTracker, 137 ) { 138 let _tt = timing::ra_coloring(); 139 debug!("Coloring for:\n{}", func.display(isa)); 140 let mut ctx = Context { 141 usable_regs: isa.allocatable_registers(func), 142 uses_pinned_reg: isa.flags().enable_pinned_reg(), 143 cur: EncCursor::new(func, isa), 144 reginfo: isa.register_info(), 145 encinfo: isa.encoding_info(), 146 cfg, 147 domtree, 148 liveness, 149 divert: &mut self.divert, 150 solver: &mut self.solver, 151 }; 152 ctx.run(tracker) 153 } 154 } 155 156 impl<'a> Context<'a> { 157 /// Is the pinned register usage enabled, and is this register the pinned register? 158 #[inline] is_pinned_reg(&self, rc: RegClass, reg: RegUnit) -> bool159 fn is_pinned_reg(&self, rc: RegClass, reg: RegUnit) -> bool { 160 rc.is_pinned_reg(self.uses_pinned_reg, reg) 161 } 162 163 /// Run the coloring algorithm. run(&mut self, tracker: &mut LiveValueTracker)164 fn run(&mut self, tracker: &mut LiveValueTracker) { 165 self.cur 166 .func 167 .locations 168 .resize(self.cur.func.dfg.num_values()); 169 170 // Visit blocks in reverse post-order. We need to ensure that at least one predecessor has 171 // been visited before each EBB. That guarantees that the EBB arguments have been colored. 172 for &ebb in self.domtree.cfg_postorder().iter().rev() { 173 self.visit_ebb(ebb, tracker); 174 } 175 } 176 177 /// Visit `ebb`, assuming that the immediate dominator has already been visited. visit_ebb(&mut self, ebb: Ebb, tracker: &mut LiveValueTracker)178 fn visit_ebb(&mut self, ebb: Ebb, tracker: &mut LiveValueTracker) { 179 debug!("Coloring {}:", ebb); 180 let mut regs = self.visit_ebb_header(ebb, tracker); 181 tracker.drop_dead_params(); 182 183 // Now go through the instructions in `ebb` and color the values they define. 184 self.cur.goto_top(ebb); 185 while let Some(inst) = self.cur.next_inst() { 186 self.cur.use_srcloc(inst); 187 let opcode = self.cur.func.dfg[inst].opcode(); 188 if !opcode.is_ghost() { 189 // This is an instruction which either has an encoding or carries ABI-related 190 // register allocation constraints. 191 let enc = self.cur.func.encodings[inst]; 192 let constraints = self.encinfo.operand_constraints(enc); 193 if self.visit_inst(inst, constraints, tracker, &mut regs) { 194 self.replace_global_defines(inst, tracker); 195 // Restore cursor location after `replace_global_defines` moves it. 196 // We want to revisit the copy instructions it inserted. 197 self.cur.goto_inst(inst); 198 } 199 } else { 200 // This is a ghost instruction with no encoding and no extra constraints. 201 let (_throughs, kills) = tracker.process_ghost(inst); 202 self.process_ghost_kills(kills, &mut regs); 203 } 204 tracker.drop_dead(inst); 205 206 // We are not able to insert any regmove for diversion or un-diversion after the first 207 // branch. Instead, we record the diversion to be restored at the entry of the next EBB, 208 // which should have a single predecessor. 209 if opcode.is_branch() && cfg!(feature = "basic-blocks") { 210 // The next instruction is necessarily an unconditional branch. 211 if let Some(branch) = self.cur.next_inst() { 212 debug!( 213 "Skip coloring {}\n from {}\n with diversions {}", 214 self.cur.display_inst(branch), 215 regs.input.display(&self.reginfo), 216 self.divert.display(&self.reginfo) 217 ); 218 use crate::ir::instructions::BranchInfo::*; 219 let target = match self.cur.func.dfg.analyze_branch(branch) { 220 NotABranch | Table(_, _) => panic!( 221 "unexpected instruction {} after a conditional branch", 222 self.cur.display_inst(branch) 223 ), 224 SingleDest(ebb, _) => ebb, 225 }; 226 227 // We have a single branch with a single target, and an EBB with a single 228 // predecessor. Thus we can forward the diversion set to the next EBB. 229 if self.cfg.pred_iter(target).count() == 1 { 230 // Transfer the diversion to the next EBB. 231 self.divert 232 .save_for_ebb(&mut self.cur.func.entry_diversions, target); 233 debug!( 234 "Set entry-diversion for {} to\n {}", 235 target, 236 self.divert.display(&self.reginfo) 237 ); 238 } else { 239 debug_assert!( 240 self.divert.is_empty(), 241 "Divert set is non-empty after the terminator." 242 ); 243 } 244 assert_eq!( 245 self.cur.next_inst(), 246 None, 247 "Unexpected instruction after a branch group." 248 ); 249 } else { 250 assert!(opcode.is_terminator()); 251 } 252 } 253 } 254 } 255 256 /// Visit the `ebb` header. 257 /// 258 /// Initialize the set of live registers and color the arguments to `ebb`. visit_ebb_header(&mut self, ebb: Ebb, tracker: &mut LiveValueTracker) -> AvailableRegs259 fn visit_ebb_header(&mut self, ebb: Ebb, tracker: &mut LiveValueTracker) -> AvailableRegs { 260 // Reposition the live value tracker and deal with the EBB arguments. 261 tracker.ebb_top( 262 ebb, 263 &self.cur.func.dfg, 264 self.liveness, 265 &self.cur.func.layout, 266 self.domtree, 267 ); 268 269 // Copy the content of the registered diversions to be reused at the 270 // entry of this basic block. 271 self.divert.at_ebb(&self.cur.func.entry_diversions, ebb); 272 debug!( 273 "Start {} with entry-diversion set to\n {}", 274 ebb, 275 self.divert.display(&self.reginfo) 276 ); 277 278 if self.cur.func.layout.entry_block() == Some(ebb) { 279 // Parameters on the entry block have ABI constraints. 280 self.color_entry_params(tracker.live()) 281 } else { 282 // The live-ins and parameters of a non-entry EBB have already been assigned a register. 283 // Reconstruct the allocatable set. 284 self.livein_regs(tracker.live()) 285 } 286 } 287 288 /// Initialize a set of allocatable registers from the values that are live-in to a block. 289 /// These values must already be colored when the dominating blocks were processed. 290 /// 291 /// Also process the EBB arguments which were colored when the first predecessor branch was 292 /// encountered. livein_regs(&self, live: &[LiveValue]) -> AvailableRegs293 fn livein_regs(&self, live: &[LiveValue]) -> AvailableRegs { 294 // Start from the registers that are actually usable. We don't want to include any reserved 295 // registers in the set. 296 let mut regs = AvailableRegs::new(&self.usable_regs); 297 298 for lv in live.iter().filter(|lv| !lv.is_dead) { 299 debug!( 300 "Live-in: {}:{} in {}", 301 lv.value, 302 lv.affinity.display(&self.reginfo), 303 self.divert 304 .get(lv.value, &self.cur.func.locations) 305 .display(&self.reginfo) 306 ); 307 if let Affinity::Reg(rci) = lv.affinity { 308 let rc = self.reginfo.rc(rci); 309 let loc = self.cur.func.locations[lv.value]; 310 let reg = match loc { 311 ValueLoc::Reg(reg) => reg, 312 ValueLoc::Unassigned => panic!("Live-in {} wasn't assigned", lv.value), 313 ValueLoc::Stack(ss) => { 314 panic!("Live-in {} is in {}, should be register", lv.value, ss) 315 } 316 }; 317 if lv.is_local { 318 regs.take(rc, reg, lv.is_local); 319 } else { 320 let loc = self.divert.get(lv.value, &self.cur.func.locations); 321 let reg_divert = match loc { 322 ValueLoc::Reg(reg) => reg, 323 ValueLoc::Unassigned => { 324 panic!("Diversion: Live-in {} wasn't assigned", lv.value) 325 } 326 ValueLoc::Stack(ss) => panic!( 327 "Diversion: Live-in {} is in {}, should be register", 328 lv.value, ss 329 ), 330 }; 331 regs.take_divert(rc, reg, reg_divert); 332 } 333 } 334 } 335 336 regs 337 } 338 339 /// Color the parameters on the entry block. 340 /// 341 /// These are function parameters that should already have assigned register units in the 342 /// function signature. 343 /// 344 /// Return the set of remaining allocatable registers after filtering out the dead arguments. color_entry_params(&mut self, args: &[LiveValue]) -> AvailableRegs345 fn color_entry_params(&mut self, args: &[LiveValue]) -> AvailableRegs { 346 let sig = &self.cur.func.signature; 347 debug_assert_eq!(sig.params.len(), args.len()); 348 349 let mut regs = AvailableRegs::new(&self.usable_regs); 350 351 for (lv, abi) in args.iter().zip(&sig.params) { 352 match lv.affinity { 353 Affinity::Reg(rci) => { 354 let rc = self.reginfo.rc(rci); 355 if let ArgumentLoc::Reg(reg) = abi.location { 356 if !lv.is_dead { 357 regs.take(rc, reg, lv.is_local); 358 } 359 self.cur.func.locations[lv.value] = ValueLoc::Reg(reg); 360 } else { 361 // This should have been fixed by the reload pass. 362 panic!( 363 "Entry arg {} has {} affinity, but ABI {}", 364 lv.value, 365 lv.affinity.display(&self.reginfo), 366 abi.display(&self.reginfo) 367 ); 368 } 369 } 370 // The spiller will have assigned an incoming stack slot already. 371 Affinity::Stack => debug_assert!(abi.location.is_stack()), 372 // This is a ghost value, unused in the function. Don't assign it to a location 373 // either. 374 Affinity::Unassigned => {} 375 } 376 } 377 378 regs 379 } 380 381 /// Program the input-side ABI constraints for `inst` into the constraint solver. 382 /// 383 /// ABI constraints are the fixed register assignments useds for calls and returns. program_input_abi(&mut self, inst: Inst, abi_params: AbiParams)384 fn program_input_abi(&mut self, inst: Inst, abi_params: AbiParams) { 385 let abi_types = match abi_params { 386 AbiParams::Parameters(sig) => &self.cur.func.dfg.signatures[sig].params, 387 AbiParams::Returns => &self.cur.func.signature.returns, 388 }; 389 390 for (abi, &value) in abi_types 391 .iter() 392 .zip(self.cur.func.dfg.inst_variable_args(inst)) 393 { 394 if let ArgumentLoc::Reg(reg) = abi.location { 395 if let Affinity::Reg(rci) = self 396 .liveness 397 .get(value) 398 .expect("ABI register must have live range") 399 .affinity 400 { 401 let rc = self.reginfo.rc(rci); 402 let cur_reg = self.divert.reg(value, &self.cur.func.locations); 403 self.solver.reassign_in(value, rc, cur_reg, reg); 404 } else { 405 panic!("ABI argument {} should be in a register", value); 406 } 407 } 408 } 409 } 410 411 /// Color the values defined by `inst` and insert any necessary shuffle code to satisfy 412 /// instruction constraints. 413 /// 414 /// Update `regs` to reflect the allocated registers after `inst`, including removing any dead 415 /// or killed values from the set. 416 /// 417 /// Returns true when the global values defined by `inst` must be replaced by local values. visit_inst( &mut self, inst: Inst, constraints: Option<&RecipeConstraints>, tracker: &mut LiveValueTracker, regs: &mut AvailableRegs, ) -> bool418 fn visit_inst( 419 &mut self, 420 inst: Inst, 421 constraints: Option<&RecipeConstraints>, 422 tracker: &mut LiveValueTracker, 423 regs: &mut AvailableRegs, 424 ) -> bool { 425 debug!( 426 "Coloring {}\n from {}", 427 self.cur.display_inst(inst), 428 regs.input.display(&self.reginfo), 429 ); 430 431 // EBB whose arguments should be colored to match the current branch instruction's 432 // arguments. 433 let mut color_dest_args = None; 434 435 // Program the solver with register constraints for the input side. 436 self.solver.reset(®s.input); 437 438 if let Some(constraints) = constraints { 439 self.program_input_constraints(inst, constraints.ins); 440 } 441 442 let call_sig = self.cur.func.dfg.call_signature(inst); 443 if let Some(sig) = call_sig { 444 self.program_input_abi(inst, AbiParams::Parameters(sig)); 445 } else if self.cur.func.dfg[inst].opcode().is_return() { 446 self.program_input_abi(inst, AbiParams::Returns); 447 } else if self.cur.func.dfg[inst].opcode().is_branch() { 448 // This is a branch, so we need to make sure that globally live values are in their 449 // global registers. For EBBs that take arguments, we also need to place the argument 450 // values in the expected registers. 451 if let Some(dest) = self.cur.func.dfg[inst].branch_destination() { 452 if self.program_ebb_arguments(inst, dest) { 453 color_dest_args = Some(dest); 454 } 455 } else { 456 // This is a multi-way branch like `br_table`. We only support arguments on 457 // single-destination branches. 458 debug_assert_eq!( 459 self.cur.func.dfg.inst_variable_args(inst).len(), 460 0, 461 "Can't handle EBB arguments: {}", 462 self.cur.display_inst(inst) 463 ); 464 self.undivert_regs(|lr, _| !lr.is_local()); 465 } 466 } 467 468 if self.solver.has_fixed_input_conflicts() { 469 self.divert_fixed_input_conflicts(tracker.live()); 470 } 471 472 self.solver.inputs_done(); 473 474 // Update the live value tracker with this instruction. 475 let (throughs, kills, defs) = tracker.process_inst(inst, &self.cur.func.dfg, self.liveness); 476 477 // Get rid of the killed values. 478 for lv in kills { 479 if let Affinity::Reg(rci) = lv.affinity { 480 let rc = self.reginfo.rc(rci); 481 let reg = self.divert.reg(lv.value, &self.cur.func.locations); 482 483 if self.is_pinned_reg(rc, reg) { 484 // Don't kill the pinned reg, either in the local or global register sets. 485 debug_assert!(lv.is_local, "pinned register SSA value can't be global"); 486 continue; 487 } 488 489 debug!( 490 " kill {} in {} ({} {})", 491 lv.value, 492 self.reginfo.display_regunit(reg), 493 if lv.is_local { "local" } else { "global" }, 494 rc 495 ); 496 self.solver.add_kill(lv.value, rc, reg); 497 498 // Update the global register set which has no diversions. 499 if !lv.is_local { 500 regs.global 501 .free(rc, self.cur.func.locations[lv.value].unwrap_reg()); 502 } 503 } 504 } 505 506 // This aligns with the " from" line at the top of the function. 507 debug!(" glob {}", regs.global.display(&self.reginfo)); 508 509 // This flag is set when the solver failed to find a solution for the global defines that 510 // doesn't interfere with `regs.global`. We need to rewrite all of `inst`s global defines 511 // as local defines followed by copies. 512 let mut replace_global_defines = false; 513 514 // Program the fixed output constraints before the general defines. This allows us to 515 // detect conflicts between fixed outputs and tied operands where the input value hasn't 516 // been converted to a solver variable. 517 if let Some(constraints) = constraints { 518 if constraints.fixed_outs { 519 self.program_fixed_outputs( 520 constraints.outs, 521 defs, 522 throughs, 523 &mut replace_global_defines, 524 ®s.global, 525 ); 526 } 527 } 528 529 if let Some(sig) = call_sig { 530 self.program_output_abi( 531 sig, 532 defs, 533 throughs, 534 &mut replace_global_defines, 535 ®s.global, 536 ); 537 } 538 539 if let Some(constraints) = constraints { 540 self.program_output_constraints( 541 inst, 542 constraints.outs, 543 defs, 544 &mut replace_global_defines, 545 ®s.global, 546 ); 547 } 548 549 // Finally, we've fully programmed the constraint solver. 550 // We expect a quick solution in most cases. 551 let is_reload = match &self.cur.func.dfg[inst] { 552 InstructionData::Unary { 553 opcode: Opcode::Fill, 554 arg: _, 555 } => true, 556 _ => false, 557 }; 558 559 let output_regs = self 560 .solver 561 .quick_solve(®s.global, is_reload) 562 .unwrap_or_else(|_| { 563 debug!("quick_solve failed for {}", self.solver); 564 self.iterate_solution( 565 throughs, 566 ®s.global, 567 &mut replace_global_defines, 568 is_reload, 569 ) 570 }); 571 572 // The solution and/or fixed input constraints may require us to shuffle the set of live 573 // registers around. 574 self.shuffle_inputs(&mut regs.input); 575 576 // If this is the first time we branch to `dest`, color its arguments to match the current 577 // register state. 578 if let Some(dest) = color_dest_args { 579 self.color_ebb_params(inst, dest); 580 } 581 582 // Apply the solution to the defs. 583 for v in self.solver.vars().iter().filter(|&v| v.is_define()) { 584 self.cur.func.locations[v.value] = ValueLoc::Reg(v.solution); 585 } 586 587 // Tied defs are not part of the solution above. 588 // Copy register assignments from tied inputs to tied outputs. 589 if let Some(constraints) = constraints { 590 if constraints.tied_ops { 591 for (op, lv) in constraints.outs.iter().zip(defs) { 592 if let ConstraintKind::Tied(num) = op.kind { 593 let arg = self.cur.func.dfg.inst_args(inst)[num as usize]; 594 let reg = self.divert.reg(arg, &self.cur.func.locations); 595 self.cur.func.locations[lv.value] = ValueLoc::Reg(reg); 596 } 597 } 598 } 599 } 600 601 // Update `regs` for the next instruction. 602 regs.input = output_regs; 603 for lv in defs { 604 let loc = self.cur.func.locations[lv.value]; 605 debug!( 606 " color {} -> {}{}", 607 lv.value, 608 loc.display(&self.reginfo), 609 if lv.is_local { 610 "" 611 } else if replace_global_defines { 612 " (global to be replaced)" 613 } else { 614 " (global)" 615 } 616 ); 617 618 if let Affinity::Reg(rci) = lv.affinity { 619 let rc = self.reginfo.rc(rci); 620 let reg = loc.unwrap_reg(); 621 622 debug_assert!( 623 !self.is_pinned_reg(rc, reg) 624 || self.cur.func.dfg[inst].opcode() == Opcode::GetPinnedReg, 625 "pinned register may not be part of outputs for '{}'.", 626 self.cur.func.dfg[inst].opcode() 627 ); 628 629 if self.is_pinned_reg(rc, reg) { 630 continue; 631 } 632 633 // Remove the dead defs. 634 if lv.endpoint == inst { 635 regs.input.free(rc, reg); 636 debug_assert!(lv.is_local); 637 } 638 639 // Track globals in their undiverted locations. 640 if !lv.is_local && !replace_global_defines { 641 regs.global.take(rc, reg); 642 } 643 } 644 } 645 646 self.forget_diverted(kills); 647 648 replace_global_defines 649 } 650 651 /// Program the input-side constraints for `inst` into the constraint solver. program_input_constraints(&mut self, inst: Inst, constraints: &[OperandConstraint])652 fn program_input_constraints(&mut self, inst: Inst, constraints: &[OperandConstraint]) { 653 for (op, &value) in constraints 654 .iter() 655 .zip(self.cur.func.dfg.inst_args(inst)) 656 .filter(|&(op, _)| op.kind != ConstraintKind::Stack) 657 { 658 // Reload pass is supposed to ensure that all arguments to register operands are 659 // already in a register. 660 let cur_reg = self.divert.reg(value, &self.cur.func.locations); 661 match op.kind { 662 ConstraintKind::FixedReg(regunit) => { 663 // Add the fixed constraint even if `cur_reg == regunit`. 664 // It is possible that we will want to convert the value to a variable later, 665 // and this identity assignment prevents that from happening. 666 self.solver 667 .reassign_in(value, op.regclass, cur_reg, regunit); 668 } 669 ConstraintKind::FixedTied(regunit) => { 670 // The pinned register may not be part of a fixed tied requirement. If this 671 // becomes the case, then it must be changed to a different register. 672 debug_assert!( 673 !self.is_pinned_reg(op.regclass, regunit), 674 "see comment above" 675 ); 676 // See comment right above. 677 self.solver 678 .reassign_in(value, op.regclass, cur_reg, regunit); 679 } 680 ConstraintKind::Tied(_) => { 681 if self.is_pinned_reg(op.regclass, cur_reg) { 682 // Divert the pinned register; it shouldn't be reused for a tied input. 683 if self.solver.can_add_var(op.regclass, cur_reg) { 684 self.solver.add_var(value, op.regclass, cur_reg); 685 } 686 } else if !op.regclass.contains(cur_reg) { 687 self.solver.add_var(value, op.regclass, cur_reg); 688 } 689 } 690 ConstraintKind::Reg => { 691 if !op.regclass.contains(cur_reg) { 692 self.solver.add_var(value, op.regclass, cur_reg); 693 } 694 } 695 ConstraintKind::Stack => unreachable!(), 696 } 697 } 698 } 699 700 /// Program the complete set of input constraints into the solver. 701 /// 702 /// The `program_input_constraints()` function above will not tell the solver about any values 703 /// that are already assigned to appropriate registers. This is normally fine, but if we want 704 /// to add additional variables to help the solver, we need to make sure that they are 705 /// constrained properly. 706 /// 707 /// This function completes the work of `program_input_constraints()` by calling `add_var` for 708 /// all values used by the instruction. program_complete_input_constraints(&mut self)709 fn program_complete_input_constraints(&mut self) { 710 let inst = self.cur.current_inst().expect("Not on an instruction"); 711 let constraints = self 712 .encinfo 713 .operand_constraints(self.cur.func.encodings[inst]) 714 .expect("Current instruction not encoded") 715 .ins; 716 717 for (op, &value) in constraints.iter().zip(self.cur.func.dfg.inst_args(inst)) { 718 match op.kind { 719 ConstraintKind::Reg | ConstraintKind::Tied(_) => { 720 let cur_reg = self.divert.reg(value, &self.cur.func.locations); 721 722 // This is the opposite condition of `program_input_constraints()`. The pinned 723 // register mustn't be added back as a variable. 724 if op.regclass.contains(cur_reg) && !self.is_pinned_reg(op.regclass, cur_reg) { 725 // This code runs after calling `solver.inputs_done()` so we must identify 726 // the new variable as killed or live-through. Always special-case the 727 // pinned register as a through variable. 728 let ctx = self.liveness.context(&self.cur.func.layout); 729 if self.liveness[value].killed_at(inst, ctx.order.pp_ebb(inst), ctx) { 730 self.solver.add_killed_var(value, op.regclass, cur_reg); 731 } else { 732 self.solver.add_through_var(value, op.regclass, cur_reg); 733 } 734 } 735 } 736 ConstraintKind::FixedReg(_) 737 | ConstraintKind::FixedTied(_) 738 | ConstraintKind::Stack => {} 739 } 740 } 741 } 742 743 /// Prepare for a branch to `dest`. 744 /// 745 /// 1. Any values that are live-in to `dest` must be un-diverted so they live in their globally 746 /// assigned register. 747 /// 2. If the `dest` EBB takes arguments, reassign the branch argument values to the matching 748 /// registers. 749 /// 750 /// Returns true if this is the first time a branch to `dest` is seen, so the `dest` argument 751 /// values should be colored after `shuffle_inputs`. program_ebb_arguments(&mut self, inst: Inst, dest: Ebb) -> bool752 fn program_ebb_arguments(&mut self, inst: Inst, dest: Ebb) -> bool { 753 // Find diverted registers that are live-in to `dest` and reassign them to their global 754 // home. 755 // 756 // Values with a global live range that are not live in to `dest` could appear as branch 757 // arguments, so they can't always be un-diverted. 758 self.undivert_regs(|lr, ctx| lr.is_livein(dest, ctx)); 759 760 // Now handle the EBB arguments. 761 let br_args = self.cur.func.dfg.inst_variable_args(inst); 762 let dest_args = self.cur.func.dfg.ebb_params(dest); 763 debug_assert_eq!(br_args.len(), dest_args.len()); 764 for (&dest_arg, &br_arg) in dest_args.iter().zip(br_args) { 765 // The first time we encounter a branch to `dest`, we get to pick the location. The 766 // following times we see a branch to `dest`, we must follow suit. 767 match self.cur.func.locations[dest_arg] { 768 ValueLoc::Unassigned => { 769 // This is the first branch to `dest`, so we should color `dest_arg` instead of 770 // `br_arg`. However, we don't know where `br_arg` will end up until 771 // after `shuffle_inputs`. See `color_ebb_params` below. 772 // 773 // It is possible for `dest_arg` to have no affinity, and then it should simply 774 // be ignored. 775 if self.liveness[dest_arg].affinity.is_reg() { 776 return true; 777 } 778 } 779 ValueLoc::Reg(dest_reg) => { 780 // We've branched to `dest` before. Make sure we use the correct argument 781 // registers by reassigning `br_arg`. 782 if let Affinity::Reg(rci) = self.liveness[br_arg].affinity { 783 let rc = self.reginfo.rc(rci); 784 let br_reg = self.divert.reg(br_arg, &self.cur.func.locations); 785 self.solver.reassign_in(br_arg, rc, br_reg, dest_reg); 786 } else { 787 panic!("Branch argument {} is not in a register", br_arg); 788 } 789 } 790 ValueLoc::Stack(ss) => { 791 // The spiller should already have given us identical stack slots. 792 debug_assert_eq!(ValueLoc::Stack(ss), self.cur.func.locations[br_arg]); 793 } 794 } 795 } 796 797 // No `dest` arguments need coloring. 798 false 799 } 800 801 /// Knowing that we've never seen a branch to `dest` before, color its parameters to match our 802 /// register state. 803 /// 804 /// This function is only called when `program_ebb_arguments()` returned `true`. color_ebb_params(&mut self, inst: Inst, dest: Ebb)805 fn color_ebb_params(&mut self, inst: Inst, dest: Ebb) { 806 let br_args = self.cur.func.dfg.inst_variable_args(inst); 807 let dest_args = self.cur.func.dfg.ebb_params(dest); 808 debug_assert_eq!(br_args.len(), dest_args.len()); 809 for (&dest_arg, &br_arg) in dest_args.iter().zip(br_args) { 810 match self.cur.func.locations[dest_arg] { 811 ValueLoc::Unassigned => { 812 if self.liveness[dest_arg].affinity.is_reg() { 813 let br_reg = self.divert.reg(br_arg, &self.cur.func.locations); 814 self.cur.func.locations[dest_arg] = ValueLoc::Reg(br_reg); 815 } 816 } 817 ValueLoc::Reg(_) => panic!("{} arg {} already colored", dest, dest_arg), 818 // Spilled value consistency is verified by `program_ebb_arguments()` above. 819 ValueLoc::Stack(_) => {} 820 } 821 } 822 } 823 824 /// Find all diverted registers where `pred` returns `true` and undo their diversion so they 825 /// are reallocated to their global register assignments. undivert_regs<Pred>(&mut self, mut pred: Pred) where Pred: FnMut(&LiveRange, LiveRangeContext<Layout>) -> bool,826 fn undivert_regs<Pred>(&mut self, mut pred: Pred) 827 where 828 Pred: FnMut(&LiveRange, LiveRangeContext<Layout>) -> bool, 829 { 830 for (&value, rdiv) in self.divert.iter() { 831 let lr = self 832 .liveness 833 .get(value) 834 .expect("Missing live range for diverted register"); 835 if pred(lr, self.liveness.context(&self.cur.func.layout)) { 836 if let Affinity::Reg(rci) = lr.affinity { 837 let rc = self.reginfo.rc(rci); 838 // Stack diversions should not be possible here. They only live transiently 839 // during `shuffle_inputs()`. 840 self.solver.reassign_in( 841 value, 842 rc, 843 rdiv.to.unwrap_reg(), 844 rdiv.from.unwrap_reg(), 845 ); 846 } else { 847 panic!( 848 "Diverted register {} with {} affinity", 849 value, 850 lr.affinity.display(&self.reginfo) 851 ); 852 } 853 } 854 } 855 } 856 857 /// Find existing live values that conflict with the fixed input register constraints programmed 858 /// into the constraint solver. Convert them to solver variables so they can be diverted. divert_fixed_input_conflicts(&mut self, live: &[LiveValue])859 fn divert_fixed_input_conflicts(&mut self, live: &[LiveValue]) { 860 for lv in live { 861 if let Affinity::Reg(rci) = lv.affinity { 862 let toprc = self.reginfo.toprc(rci); 863 let reg = self.divert.reg(lv.value, &self.cur.func.locations); 864 if self.solver.is_fixed_input_conflict(toprc, reg) { 865 self.solver.add_var(lv.value, toprc, reg); 866 } 867 } 868 } 869 } 870 871 /// Program any fixed-register output constraints into the solver. This may also detect 872 /// conflicts between live-through registers and fixed output registers. These live-through 873 /// values need to be turned into solver variables so they can be reassigned. program_fixed_outputs( &mut self, constraints: &[OperandConstraint], defs: &[LiveValue], throughs: &[LiveValue], replace_global_defines: &mut bool, global_regs: &RegisterSet, )874 fn program_fixed_outputs( 875 &mut self, 876 constraints: &[OperandConstraint], 877 defs: &[LiveValue], 878 throughs: &[LiveValue], 879 replace_global_defines: &mut bool, 880 global_regs: &RegisterSet, 881 ) { 882 for (op, lv) in constraints.iter().zip(defs) { 883 match op.kind { 884 ConstraintKind::FixedReg(reg) | ConstraintKind::FixedTied(reg) => { 885 self.add_fixed_output(lv.value, op.regclass, reg, throughs); 886 if !lv.is_local && !global_regs.is_avail(op.regclass, reg) { 887 debug!( 888 "Fixed output {} in {}:{} is not available in global regs", 889 lv.value, 890 op.regclass, 891 self.reginfo.display_regunit(reg) 892 ); 893 *replace_global_defines = true; 894 } 895 } 896 ConstraintKind::Reg | ConstraintKind::Tied(_) | ConstraintKind::Stack => {} 897 } 898 } 899 } 900 901 /// Program the output-side ABI constraints for `inst` into the constraint solver. 902 /// 903 /// That means return values for a call instruction. program_output_abi( &mut self, sig: SigRef, defs: &[LiveValue], throughs: &[LiveValue], replace_global_defines: &mut bool, global_regs: &RegisterSet, )904 fn program_output_abi( 905 &mut self, 906 sig: SigRef, 907 defs: &[LiveValue], 908 throughs: &[LiveValue], 909 replace_global_defines: &mut bool, 910 global_regs: &RegisterSet, 911 ) { 912 // It's technically possible for a call instruction to have fixed results before the 913 // variable list of results, but we have no known instances of that. 914 // Just assume all results are variable return values. 915 debug_assert_eq!(defs.len(), self.cur.func.dfg.signatures[sig].returns.len()); 916 for (i, lv) in defs.iter().enumerate() { 917 let abi = self.cur.func.dfg.signatures[sig].returns[i]; 918 if let ArgumentLoc::Reg(reg) = abi.location { 919 if let Affinity::Reg(rci) = lv.affinity { 920 let rc = self.reginfo.rc(rci); 921 self.add_fixed_output(lv.value, rc, reg, throughs); 922 if !lv.is_local && !global_regs.is_avail(rc, reg) { 923 debug!( 924 "ABI output {} in {}:{} is not available in global regs", 925 lv.value, 926 rc, 927 self.reginfo.display_regunit(reg) 928 ); 929 *replace_global_defines = true; 930 } 931 } else { 932 panic!("ABI argument {} should be in a register", lv.value); 933 } 934 } 935 } 936 } 937 938 /// Add a single fixed output value to the solver. add_fixed_output( &mut self, value: Value, rc: RegClass, reg: RegUnit, throughs: &[LiveValue], )939 fn add_fixed_output( 940 &mut self, 941 value: Value, 942 rc: RegClass, 943 reg: RegUnit, 944 throughs: &[LiveValue], 945 ) { 946 // Pinned register is already unavailable in the solver, since it is copied in the 947 // available registers on entry. 948 if !self.is_pinned_reg(rc, reg) && !self.solver.add_fixed_output(rc, reg) { 949 // The fixed output conflicts with some of the live-through registers. 950 for lv in throughs { 951 if let Affinity::Reg(rci) = lv.affinity { 952 let toprc2 = self.reginfo.toprc(rci); 953 let reg2 = self.divert.reg(lv.value, &self.cur.func.locations); 954 if regs_overlap(rc, reg, toprc2, reg2) { 955 // This live-through value is interfering with the fixed output assignment. 956 // Convert it to a solver variable. 957 self.solver.add_through_var(lv.value, toprc2, reg2); 958 } 959 } 960 } 961 962 let ok = self.solver.add_fixed_output(rc, reg); 963 debug_assert!(ok, "Couldn't clear fixed output interference for {}", value); 964 } 965 self.cur.func.locations[value] = ValueLoc::Reg(reg); 966 } 967 968 /// Program the output-side constraints for `inst` into the constraint solver. 969 /// 970 /// It is assumed that all fixed outputs have already been handled. program_output_constraints( &mut self, inst: Inst, constraints: &[OperandConstraint], defs: &[LiveValue], replace_global_defines: &mut bool, global_regs: &RegisterSet, )971 fn program_output_constraints( 972 &mut self, 973 inst: Inst, 974 constraints: &[OperandConstraint], 975 defs: &[LiveValue], 976 replace_global_defines: &mut bool, 977 global_regs: &RegisterSet, 978 ) { 979 for (op, lv) in constraints.iter().zip(defs) { 980 match op.kind { 981 ConstraintKind::FixedReg(_) 982 | ConstraintKind::FixedTied(_) 983 | ConstraintKind::Stack => continue, 984 ConstraintKind::Reg => { 985 self.solver.add_def(lv.value, op.regclass, !lv.is_local); 986 } 987 ConstraintKind::Tied(num) => { 988 // Find the input operand we're tied to. 989 // The solver doesn't care about the output value. 990 let arg = self.cur.func.dfg.inst_args(inst)[num as usize]; 991 let reg = self.divert.reg(arg, &self.cur.func.locations); 992 993 if let Some(reg) = 994 self.solver 995 .add_tied_input(arg, op.regclass, reg, !lv.is_local) 996 { 997 // The value we're tied to has been assigned to a fixed register. 998 // We need to make sure that fixed output register is compatible with the 999 // global register set. 1000 if !lv.is_local && !global_regs.is_avail(op.regclass, reg) { 1001 debug!( 1002 "Tied output {} in {}:{} is not available in global regs", 1003 lv.value, 1004 op.regclass, 1005 self.reginfo.display_regunit(reg) 1006 ); 1007 *replace_global_defines = true; 1008 } 1009 } 1010 } 1011 } 1012 } 1013 } 1014 1015 /// Try harder to find a solution to the constraint problem since `quick_solve()` failed. 1016 /// 1017 /// We may need to move more registers around before a solution is possible. Use an iterative 1018 /// algorithm that adds one more variable until a solution can be found. iterate_solution( &mut self, throughs: &[LiveValue], global_regs: &RegisterSet, replace_global_defines: &mut bool, is_reload: bool, ) -> RegisterSet1019 fn iterate_solution( 1020 &mut self, 1021 throughs: &[LiveValue], 1022 global_regs: &RegisterSet, 1023 replace_global_defines: &mut bool, 1024 is_reload: bool, 1025 ) -> RegisterSet { 1026 // Make sure `try_add_var()` below doesn't create a variable with too loose constraints. 1027 self.program_complete_input_constraints(); 1028 1029 loop { 1030 match self.solver.real_solve(global_regs, is_reload) { 1031 Ok(regs) => return regs, 1032 Err(SolverError::Divert(rc)) => { 1033 // Do we have any live-through `rc` registers that are not already variables? 1034 let added = self.try_add_var(rc, throughs); 1035 debug_assert!(added, "Ran out of registers in {}", rc); 1036 } 1037 Err(SolverError::Global(_value)) => { 1038 debug!( 1039 "Not enough global registers for {}, trying as local", 1040 _value 1041 ); 1042 // We'll clear the `is_global` flag on all solver variables and instead make a 1043 // note to replace all global defines with local defines followed by a copy. 1044 *replace_global_defines = true; 1045 self.solver.clear_all_global_flags(); 1046 } 1047 }; 1048 } 1049 } 1050 1051 /// Try to add an `rc` variable to the solver from the `throughs` set. try_add_var(&mut self, rc: RegClass, throughs: &[LiveValue]) -> bool1052 fn try_add_var(&mut self, rc: RegClass, throughs: &[LiveValue]) -> bool { 1053 debug!("Trying to add a {} reg from {} values", rc, throughs.len()); 1054 1055 for lv in throughs { 1056 if let Affinity::Reg(rci) = lv.affinity { 1057 // The new variable gets to roam the whole top-level register class because it is 1058 // not actually constrained by the instruction. We just want it out of the way. 1059 let toprc2 = self.reginfo.toprc(rci); 1060 let reg2 = self.divert.reg(lv.value, &self.cur.func.locations); 1061 if rc.contains(reg2) 1062 && self.solver.can_add_var(toprc2, reg2) 1063 && !self.is_live_on_outgoing_edge(lv.value) 1064 { 1065 self.solver.add_through_var(lv.value, toprc2, reg2); 1066 return true; 1067 } 1068 } 1069 } 1070 1071 false 1072 } 1073 1074 /// Determine if `value` is live on a CFG edge from the current instruction. 1075 /// 1076 /// This means that the current instruction is a branch and `value` is live in to one of the 1077 /// branch destinations. Branch arguments and EBB parameters are not considered live on the 1078 /// edge. is_live_on_outgoing_edge(&self, value: Value) -> bool1079 fn is_live_on_outgoing_edge(&self, value: Value) -> bool { 1080 use crate::ir::instructions::BranchInfo::*; 1081 1082 let inst = self.cur.current_inst().expect("Not on an instruction"); 1083 let ctx = self.liveness.context(&self.cur.func.layout); 1084 match self.cur.func.dfg.analyze_branch(inst) { 1085 NotABranch => false, 1086 SingleDest(ebb, _) => { 1087 let lr = &self.liveness[value]; 1088 lr.is_livein(ebb, ctx) 1089 } 1090 Table(jt, ebb) => { 1091 let lr = &self.liveness[value]; 1092 !lr.is_local() 1093 && (ebb.map_or(false, |ebb| lr.is_livein(ebb, ctx)) 1094 || self.cur.func.jump_tables[jt] 1095 .iter() 1096 .any(|ebb| lr.is_livein(*ebb, ctx))) 1097 } 1098 } 1099 } 1100 1101 /// Emit `regmove` instructions as needed to move the live registers into place before the 1102 /// instruction. Also update `self.divert` accordingly. 1103 /// 1104 /// The `self.cur` cursor is expected to point at the instruction. The register moves are 1105 /// inserted before. 1106 /// 1107 /// The solver needs to be reminded of the available registers before any moves are inserted. shuffle_inputs(&mut self, regs: &mut RegisterSet)1108 fn shuffle_inputs(&mut self, regs: &mut RegisterSet) { 1109 use crate::regalloc::solver::Move::*; 1110 1111 let spills = self.solver.schedule_moves(regs); 1112 1113 // The move operations returned by `schedule_moves` refer to emergency spill slots by 1114 // consecutive indexes starting from 0. Map these to real stack slots. 1115 // It is very unlikely (impossible?) that we would need more than one spill per top-level 1116 // register class, so avoid allocation by using a fixed array here. 1117 let mut slot = [PackedOption::default(); 8]; 1118 debug_assert!(spills <= slot.len(), "Too many spills ({})", spills); 1119 1120 for m in self.solver.moves() { 1121 match *m { 1122 Reg { 1123 value, 1124 from, 1125 to, 1126 rc, 1127 } => { 1128 debug_assert!( 1129 !self.is_pinned_reg(rc, to), 1130 "pinned register used in a regmove" 1131 ); 1132 self.divert.regmove(value, from, to); 1133 self.cur.ins().regmove(value, from, to); 1134 } 1135 Spill { 1136 value, 1137 from, 1138 to_slot, 1139 .. 1140 } => { 1141 debug_assert_eq!(slot[to_slot].expand(), None, "Overwriting slot in use"); 1142 let ss = self 1143 .cur 1144 .func 1145 .stack_slots 1146 .get_emergency_slot(self.cur.func.dfg.value_type(value), &slot[0..spills]); 1147 slot[to_slot] = ss.into(); 1148 self.divert.regspill(value, from, ss); 1149 self.cur.ins().regspill(value, from, ss); 1150 } 1151 Fill { 1152 value, 1153 from_slot, 1154 to, 1155 rc, 1156 } => { 1157 debug_assert!( 1158 !self.is_pinned_reg(rc, to), 1159 "pinned register used in a regfill" 1160 ); 1161 // These slots are single use, so mark `ss` as available again. 1162 let ss = slot[from_slot].take().expect("Using unallocated slot"); 1163 self.divert.regfill(value, ss, to); 1164 self.cur.ins().regfill(value, ss, to); 1165 } 1166 } 1167 } 1168 } 1169 1170 /// Forget about any register diversions in `kills`. forget_diverted(&mut self, kills: &[LiveValue])1171 fn forget_diverted(&mut self, kills: &[LiveValue]) { 1172 if self.divert.is_empty() { 1173 return; 1174 } 1175 1176 for lv in kills { 1177 if lv.affinity.is_reg() { 1178 self.divert.remove(lv.value); 1179 } 1180 } 1181 } 1182 1183 /// Replace all global values defined by `inst` with local values that are then copied into the 1184 /// global value: 1185 /// 1186 /// v1 = foo 1187 /// 1188 /// becomes: 1189 /// 1190 /// v20 = foo 1191 /// v1 = copy v20 1192 /// 1193 /// This is sometimes necessary when there are no global registers available that can satisfy 1194 /// the constraints on the instruction operands. 1195 /// replace_global_defines(&mut self, inst: Inst, tracker: &mut LiveValueTracker)1196 fn replace_global_defines(&mut self, inst: Inst, tracker: &mut LiveValueTracker) { 1197 debug!("Replacing global defs on {}", self.cur.display_inst(inst)); 1198 1199 // We'll insert copies *after `inst`. Our caller will move the cursor back. 1200 self.cur.next_inst(); 1201 1202 // The tracker keeps the defs from `inst` at the end. Any dead defs have already been 1203 // removed, so it's not obvious how many defs to process 1204 for lv in tracker.live_mut().iter_mut().rev() { 1205 // Keep going until we reach a value that is not defined by `inst`. 1206 if match self.cur.func.dfg.value_def(lv.value) { 1207 ValueDef::Result(i, _) => i != inst, 1208 _ => true, 1209 } { 1210 break; 1211 } 1212 if lv.is_local || !lv.affinity.is_reg() { 1213 continue; 1214 } 1215 1216 // Now `lv.value` is globally live and defined by `inst`. Replace it with a local live 1217 // range that is copied after `inst`. 1218 let ty = self.cur.func.dfg.value_type(lv.value); 1219 let local = self.cur.func.dfg.replace_result(lv.value, ty); 1220 self.cur.ins().with_result(lv.value).copy(local); 1221 let copy = self.cur.built_inst(); 1222 1223 // Create a live range for `local: inst -> copy`. 1224 self.liveness.create_dead(local, inst, lv.affinity); 1225 self.liveness.extend_locally( 1226 local, 1227 self.cur.func.layout.pp_ebb(inst), 1228 copy, 1229 &self.cur.func.layout, 1230 ); 1231 1232 // Move the definition of the global `lv.value`. 1233 self.liveness.move_def_locally(lv.value, copy); 1234 1235 // Transfer the register coloring to `local`. 1236 let loc = mem::replace(&mut self.cur.func.locations[lv.value], ValueLoc::default()); 1237 self.cur.func.locations[local] = loc; 1238 1239 // Update `lv` to reflect the new `local` live range. 1240 lv.value = local; 1241 lv.endpoint = copy; 1242 lv.is_local = true; 1243 1244 debug!( 1245 " + {} with {} in {}", 1246 self.cur.display_inst(copy), 1247 local, 1248 loc.display(&self.reginfo) 1249 ); 1250 } 1251 debug!("Done: {}", self.cur.display_inst(inst)); 1252 } 1253 1254 /// Process kills on a ghost instruction. 1255 /// - Forget diversions. 1256 /// - Free killed registers. process_ghost_kills(&mut self, kills: &[LiveValue], regs: &mut AvailableRegs)1257 fn process_ghost_kills(&mut self, kills: &[LiveValue], regs: &mut AvailableRegs) { 1258 for lv in kills { 1259 if let Affinity::Reg(rci) = lv.affinity { 1260 let rc = self.reginfo.rc(rci); 1261 let loc = match self.divert.remove(lv.value) { 1262 Some(loc) => loc, 1263 None => self.cur.func.locations[lv.value], 1264 }; 1265 regs.input.free(rc, loc.unwrap_reg()); 1266 if !lv.is_local { 1267 regs.global 1268 .free(rc, self.cur.func.locations[lv.value].unwrap_reg()); 1269 } 1270 } 1271 } 1272 } 1273 } 1274 1275 /// Keep track of the set of available registers in two interference domains: all registers 1276 /// considering diversions and global registers not considering diversions. 1277 struct AvailableRegs { 1278 /// The exact set of registers available on the input side of the current instruction. This 1279 /// takes into account register diversions, and it includes both local and global live ranges. 1280 input: RegisterSet, 1281 1282 /// Registers available for allocating globally live values. This set ignores any local values, 1283 /// and it does not account for register diversions. 1284 /// 1285 /// Global values must be allocated out of this set because conflicts with other global values 1286 /// can't be resolved with local diversions. 1287 global: RegisterSet, 1288 } 1289 1290 impl AvailableRegs { 1291 /// Initialize both the input and global sets from `regs`. new(regs: &RegisterSet) -> Self1292 pub fn new(regs: &RegisterSet) -> Self { 1293 Self { 1294 input: regs.clone(), 1295 global: regs.clone(), 1296 } 1297 } 1298 1299 /// Take an un-diverted register from one or both sets. take(&mut self, rc: RegClass, reg: RegUnit, is_local: bool)1300 pub fn take(&mut self, rc: RegClass, reg: RegUnit, is_local: bool) { 1301 self.input.take(rc, reg); 1302 if !is_local { 1303 self.global.take(rc, reg); 1304 } 1305 } 1306 1307 /// Take a diverted register from both sets for a non-local allocation. take_divert(&mut self, rc: RegClass, reg: RegUnit, reg_divert: RegUnit)1308 pub fn take_divert(&mut self, rc: RegClass, reg: RegUnit, reg_divert: RegUnit) { 1309 self.input.take(rc, reg_divert); 1310 self.global.take(rc, reg); 1311 } 1312 } 1313