1 //! Constraint solver for register coloring. 2 //! 3 //! The coloring phase of SSA-based register allocation is very simple in theory, but in practice 4 //! it is complicated by the various constraints imposed by individual instructions: 5 //! 6 //! - Call and return instructions have to satisfy ABI requirements for arguments and return 7 //! values. 8 //! - Values live across a call must be in a callee-saved register. 9 //! - Some instructions have operand constraints such as register sub-classes, fixed registers, or 10 //! tied operands. 11 //! 12 //! # The instruction register coloring problem 13 //! 14 //! The constraint solver addresses the problem of satisfying the constraints of a single 15 //! instruction. We have: 16 //! 17 //! - A set of values that are live in registers before the instruction, with current register 18 //! assignments. Some are used by the instruction, some are not. 19 //! - A subset of the live register values that are killed by the instruction. 20 //! - A set of new register values that are defined by the instruction. 21 //! 22 //! We are not concerned with stack values at all. The reload pass ensures that all values required 23 //! to be in a register by the instruction are already in a register. 24 //! 25 //! A solution to the register coloring problem consists of: 26 //! 27 //! - Register reassignment prescriptions for a subset of the live register values. 28 //! - Register assignments for the instruction's defined values. 29 //! 30 //! The solution ensures that when live registers are reassigned as prescribed before the 31 //! instruction, all its operand constraints are satisfied, and the definition assignments won't 32 //! conflict. 33 //! 34 //! # Register diversions and global interference 35 //! 36 //! We can divert register values temporarily to satisfy constraints, but we need to put the 37 //! values back into their originally assigned register locations before leaving the block. 38 //! Otherwise, values won't be in the right register at the entry point of other blocks. 39 //! 40 //! Some values are *local*, and we don't need to worry about putting those values back since they 41 //! are not used in any other blocks. 42 //! 43 //! When we assign register locations to defines, we are assigning both the register used locally 44 //! immediately after the instruction and the register used globally when the defined value is used 45 //! in a different block. We need to avoid interference both locally at the instruction and globally. 46 //! 47 //! We have multiple mappings of values to registers: 48 //! 49 //! 1. The initial local mapping before the instruction. This includes any diversions from previous 50 //! instructions in the block, but not diversions for the current instruction. 51 //! 2. The local mapping after applying the additional reassignments required to satisfy the 52 //! constraints of the current instruction. 53 //! 3. The local mapping after the instruction. This excludes values killed by the instruction and 54 //! includes values defined by the instruction. 55 //! 4. The global mapping after the instruction. This mapping only contains values with global live 56 //! ranges, and it does not include any diversions. 57 //! 58 //! All four mappings must be kept free of interference. 59 //! 60 //! # Problems handled by previous passes. 61 //! 62 //! The constraint solver can only reassign registers, it can't create spill code, so some 63 //! constraints are handled by earlier passes: 64 //! 65 //! - There will be enough free registers available for the defines. Ensuring this is the primary 66 //! purpose of the spilling phase. 67 //! - When the same value is used for multiple operands, the intersection of operand constraints is 68 //! non-empty. The spilling phase will insert copies to handle mutually incompatible constraints, 69 //! such as when the same value is bound to two different function arguments. 70 //! - Values bound to tied operands must be killed by the instruction. Also enforced by the 71 //! spiller. 72 //! - Values used by register operands are in registers, and values used by stack operands are in 73 //! stack slots. This is enforced by the reload pass. 74 //! 75 //! # Solver algorithm 76 //! 77 //! The goal of the solver is to satisfy the instruction constraints with a minimal number of 78 //! register assignments before the instruction. 79 //! 80 //! 1. Compute the set of values used by operands with a fixed register constraint that isn't 81 //! already satisfied. These are mandatory predetermined reassignments. 82 //! 2. Compute the set of values that don't satisfy their register class constraint. These are 83 //! mandatory reassignments that we need to solve. 84 //! 3. Add the set of defines to the set of variables computed in 2. Exclude defines tied to an 85 //! input operand since their value is pre-determined. 86 //! 87 //! The set of values computed in 2. and 3. are the *variables* for the solver. Given a set of 88 //! variables, we can also compute a set of allocatable registers by removing the variables from 89 //! the set of assigned registers before the instruction. 90 //! 91 //! 1. For each variable, compute its domain as the intersection of the allocatable registers and 92 //! its register class constraint. 93 //! 2. Sort the variables in order of increasing domain size. 94 //! 3. Search for a solution that assigns each variable a register from its domain without 95 //! interference between variables. 96 //! 97 //! If the search fails to find a solution, we may need to reassign more registers. Find an 98 //! appropriate candidate among the set of live register values, add it as a variable and start 99 //! over. 100 101 use super::RegisterSet; 102 use crate::dbg::DisplayList; 103 use crate::entity::{SparseMap, SparseMapValue}; 104 use crate::ir::Value; 105 use crate::isa::{RegClass, RegUnit}; 106 use crate::regalloc::register_set::RegSetIter; 107 use alloc::vec::Vec; 108 use core::cmp; 109 use core::fmt; 110 use core::mem; 111 use core::u16; 112 113 /// A variable in the constraint problem. 114 /// 115 /// Variables represent register values that can be assigned to any register unit within the 116 /// constraint register class. This includes live register values that can be reassigned to a new 117 /// register and values defined by the instruction which must be assigned to a register. 118 /// 119 /// Besides satisfying the register class constraint, variables must also be mutually 120 /// non-interfering in up to three contexts: 121 /// 122 /// 1. Input side live registers, after applying all the reassignments. 123 /// 2. Output side live registers, considering all the local register diversions. 124 /// 3. Global live register, not considering any local diversions. 125 /// 126 pub struct Variable { 127 /// The value whose register assignment we're looking for. 128 pub value: Value, 129 130 /// Original register unit holding this live value before the instruction, or `None` for a 131 /// value that is defined by the instruction. 132 from: Option<RegUnit>, 133 134 /// Avoid interference on the input side. 135 is_input: bool, 136 137 /// Avoid interference on the output side. 138 is_output: bool, 139 140 /// Avoid interference with the global registers. 141 is_global: bool, 142 143 /// Number of registers available in the domain of this variable. 144 domain: u16, 145 146 /// The assigned register unit after a full solution was found. 147 pub solution: RegUnit, 148 149 /// Any solution must belong to the constraint register class. 150 constraint: RegClass, 151 } 152 153 impl Variable { new_live(value: Value, constraint: RegClass, from: RegUnit, is_output: bool) -> Self154 fn new_live(value: Value, constraint: RegClass, from: RegUnit, is_output: bool) -> Self { 155 Self { 156 value, 157 constraint, 158 from: Some(from), 159 is_input: true, 160 is_output, 161 is_global: false, 162 domain: 0, 163 solution: !0, 164 } 165 } 166 new_def(value: Value, constraint: RegClass, is_global: bool) -> Self167 fn new_def(value: Value, constraint: RegClass, is_global: bool) -> Self { 168 Self { 169 value, 170 constraint, 171 from: None, 172 is_input: false, 173 is_output: true, 174 is_global, 175 domain: 0, 176 solution: !0, 177 } 178 } 179 180 /// Does this variable represent a value defined by the current instruction? is_define(&self) -> bool181 pub fn is_define(&self) -> bool { 182 self.from.is_none() 183 } 184 185 /// Get an iterator over possible register choices, given the available registers on the input 186 /// and output sides as well as the available global register set. iter(&self, iregs: &RegisterSet, oregs: &RegisterSet, gregs: &RegisterSet) -> RegSetIter187 fn iter(&self, iregs: &RegisterSet, oregs: &RegisterSet, gregs: &RegisterSet) -> RegSetIter { 188 if !self.is_output { 189 debug_assert!(!self.is_global, "Global implies output"); 190 debug_assert!(self.is_input, "Missing interference set"); 191 return iregs.iter(self.constraint); 192 } 193 194 let mut r = oregs.clone(); 195 if self.is_input { 196 r.intersect(iregs); 197 } 198 if self.is_global { 199 r.intersect(gregs); 200 } 201 r.iter(self.constraint) 202 } 203 } 204 205 impl fmt::Display for Variable { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result206 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 207 write!(f, "{}({}", self.value, self.constraint)?; 208 if let Some(reg) = self.from { 209 write!(f, ", from {}", self.constraint.info.display_regunit(reg))?; 210 } 211 if self.is_input { 212 write!(f, ", in")?; 213 } 214 if self.is_output { 215 write!(f, ", out")?; 216 } 217 if self.is_global { 218 write!(f, ", global")?; 219 } 220 if self.is_define() { 221 write!(f, ", def")?; 222 } 223 if self.domain > 0 { 224 write!(f, ", {}", self.domain)?; 225 } 226 write!(f, ")") 227 } 228 } 229 230 #[derive(Clone, Debug)] 231 pub struct Assignment { 232 pub value: Value, 233 pub from: RegUnit, 234 pub to: RegUnit, 235 pub rc: RegClass, 236 } 237 238 impl SparseMapValue<Value> for Assignment { key(&self) -> Value239 fn key(&self) -> Value { 240 self.value 241 } 242 } 243 244 impl fmt::Display for Assignment { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result245 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 246 let ri = self.rc.info; 247 write!( 248 f, 249 "{}:{}({} -> {})", 250 self.value, 251 self.rc, 252 ri.display_regunit(self.from), 253 ri.display_regunit(self.to) 254 ) 255 } 256 } 257 258 /// A move operation between two registers or between a register and an emergency spill slot. 259 #[derive(Clone, PartialEq)] 260 pub enum Move { 261 Reg { 262 value: Value, 263 rc: RegClass, 264 from: RegUnit, 265 to: RegUnit, 266 }, 267 #[allow(dead_code)] // rustc doesn't see it isn't dead. 268 Spill { 269 value: Value, 270 rc: RegClass, 271 from: RegUnit, 272 to_slot: usize, 273 }, 274 Fill { 275 value: Value, 276 rc: RegClass, 277 from_slot: usize, 278 to: RegUnit, 279 }, 280 } 281 282 impl Move { 283 /// Create a register move from an assignment, but not for identity assignments. with_assignment(a: &Assignment) -> Option<Self>284 fn with_assignment(a: &Assignment) -> Option<Self> { 285 if a.from != a.to { 286 Some(Self::Reg { 287 value: a.value, 288 from: a.from, 289 to: a.to, 290 rc: a.rc, 291 }) 292 } else { 293 None 294 } 295 } 296 297 /// Get the "from" register and register class, if possible. 298 #[cfg_attr(feature = "cargo-clippy", allow(clippy::wrong_self_convention))] from_reg(&self) -> Option<(RegClass, RegUnit)>299 fn from_reg(&self) -> Option<(RegClass, RegUnit)> { 300 match *self { 301 Self::Reg { rc, from, .. } | Self::Spill { rc, from, .. } => Some((rc, from)), 302 Self::Fill { .. } => None, 303 } 304 } 305 306 /// Get the "to" register and register class, if possible. to_reg(&self) -> Option<(RegClass, RegUnit)>307 fn to_reg(&self) -> Option<(RegClass, RegUnit)> { 308 match *self { 309 Self::Reg { rc, to, .. } | Self::Fill { rc, to, .. } => Some((rc, to)), 310 Self::Spill { .. } => None, 311 } 312 } 313 314 /// Replace the "to" register with `new` and return the old value. replace_to_reg(&mut self, new: RegUnit) -> RegUnit315 fn replace_to_reg(&mut self, new: RegUnit) -> RegUnit { 316 mem::replace( 317 match *self { 318 Self::Reg { ref mut to, .. } | Self::Fill { ref mut to, .. } => to, 319 Self::Spill { .. } => panic!("No to register in a spill {}", self), 320 }, 321 new, 322 ) 323 } 324 325 /// Convert this `Reg` move to a spill to `slot` and return the old "to" register. change_to_spill(&mut self, slot: usize) -> RegUnit326 fn change_to_spill(&mut self, slot: usize) -> RegUnit { 327 match self.clone() { 328 Self::Reg { 329 value, 330 rc, 331 from, 332 to, 333 } => { 334 *self = Self::Spill { 335 value, 336 rc, 337 from, 338 to_slot: slot, 339 }; 340 to 341 } 342 _ => panic!("Expected reg move: {}", self), 343 } 344 } 345 346 /// Get the value being moved. value(&self) -> Value347 fn value(&self) -> Value { 348 match *self { 349 Self::Reg { value, .. } | Self::Fill { value, .. } | Self::Spill { value, .. } => value, 350 } 351 } 352 353 /// Get the associated register class. rc(&self) -> RegClass354 fn rc(&self) -> RegClass { 355 match *self { 356 Self::Reg { rc, .. } | Self::Fill { rc, .. } | Self::Spill { rc, .. } => rc, 357 } 358 } 359 } 360 361 impl fmt::Display for Move { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result362 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 363 match *self { 364 Self::Reg { 365 value, 366 from, 367 to, 368 rc, 369 } => write!( 370 f, 371 "{}:{}({} -> {})", 372 value, 373 rc, 374 rc.info.display_regunit(from), 375 rc.info.display_regunit(to) 376 ), 377 Self::Spill { 378 value, 379 from, 380 to_slot, 381 rc, 382 } => write!( 383 f, 384 "{}:{}({} -> slot {})", 385 value, 386 rc, 387 rc.info.display_regunit(from), 388 to_slot 389 ), 390 Self::Fill { 391 value, 392 from_slot, 393 to, 394 rc, 395 } => write!( 396 f, 397 "{}:{}(slot {} -> {})", 398 value, 399 rc, 400 from_slot, 401 rc.info.display_regunit(to) 402 ), 403 } 404 } 405 } 406 407 impl fmt::Debug for Move { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result408 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 409 let as_display: &dyn fmt::Display = self; 410 as_display.fmt(f) 411 } 412 } 413 414 /// Constraint solver for register allocation around a single instruction. 415 /// 416 /// Start by programming in the instruction constraints. 417 /// 418 /// 1. Initialize the solver by calling `reset()` with the set of allocatable registers before the 419 /// instruction. 420 /// 2. Program the input side constraints: Call `reassign_in()` for all fixed register constraints, 421 /// and `add_var()` for any input operands whose constraints are not already satisfied. 422 /// 3. Check for conflicts between fixed input assignments and existing live values by calling 423 /// `has_fixed_input_conflicts()`. Resolve any conflicts by calling `add_var()` with the 424 /// conflicting values. 425 /// 4. Prepare for adding output side constraints by calling `inputs_done()`. 426 /// 5. Add any killed register values that no longer cause interference on the output side by 427 /// calling `add_kill()`. 428 /// 6. Program the output side constraints: Call `add_fixed_output()` for all fixed register 429 /// constraints and `add_def()` for free defines. Resolve fixed output conflicts by calling 430 /// `add_through_var()`. 431 /// 432 pub struct Solver { 433 /// Register reassignments that are required or decided as part of a full solution. 434 /// This includes identity assignments for values that are already in the correct fixed 435 /// register. 436 assignments: SparseMap<Value, Assignment>, 437 438 /// Variables are the values that should be reassigned as part of a solution. 439 /// Values with fixed register constraints are not considered variables. They are represented 440 /// in the `assignments` vector if necessary. 441 vars: Vec<Variable>, 442 443 /// Are we finished adding input-side constraints? This changes the meaning of the `regs_in` 444 /// and `regs_out` register sets. 445 inputs_done: bool, 446 447 /// Available registers on the input side of the instruction. 448 /// 449 /// While we're adding input constraints (`!inputs_done`): 450 /// 451 /// - Live values on the input side are marked as unavailable. 452 /// - The 'from' registers of fixed input reassignments are marked as available as they are 453 /// added. 454 /// - Input-side variables are marked as available. 455 /// 456 /// After finishing input constraints (`inputs_done`): 457 /// 458 /// - Live values on the input side are marked as unavailable. 459 /// - The 'to' registers of fixed input reassignments are marked as unavailable. 460 /// - Input-side variables are marked as available. 461 /// 462 regs_in: RegisterSet, 463 464 /// Available registers on the output side of the instruction / fixed input scratch space. 465 /// 466 /// While we're adding input constraints (`!inputs_done`): 467 /// 468 /// - The 'to' registers of fixed input reassignments are marked as unavailable. 469 /// 470 /// After finishing input constraints (`inputs_done`): 471 /// 472 /// - Live-through values are marked as unavailable. 473 /// - Fixed output assignments are marked as unavailable. 474 /// - Live-through variables are marked as available. 475 /// 476 regs_out: RegisterSet, 477 478 /// List of register moves scheduled to avoid conflicts. 479 /// 480 /// This is used as working space by the `schedule_moves()` function. 481 moves: Vec<Move>, 482 483 /// List of pending fill moves. This is only used during `schedule_moves()`. 484 fills: Vec<Move>, 485 } 486 487 /// Interface for programming the constraints into the solver. 488 impl Solver { 489 /// Create a new empty solver. new() -> Self490 pub fn new() -> Self { 491 Self { 492 assignments: SparseMap::new(), 493 vars: Vec::new(), 494 inputs_done: false, 495 regs_in: RegisterSet::new(), 496 regs_out: RegisterSet::new(), 497 moves: Vec::new(), 498 fills: Vec::new(), 499 } 500 } 501 502 /// Clear all data structures in this coloring pass. clear(&mut self)503 pub fn clear(&mut self) { 504 self.assignments.clear(); 505 self.vars.clear(); 506 self.inputs_done = false; 507 self.regs_in = RegisterSet::new(); 508 self.regs_out = RegisterSet::new(); 509 self.moves.clear(); 510 self.fills.clear(); 511 } 512 513 /// Reset the solver state and prepare solving for a new instruction with an initial set of 514 /// allocatable registers. 515 /// 516 /// The `regs` set is the allocatable registers before any reassignments are applied. reset(&mut self, regs: &RegisterSet)517 pub fn reset(&mut self, regs: &RegisterSet) { 518 self.assignments.clear(); 519 self.vars.clear(); 520 self.inputs_done = false; 521 self.regs_in = regs.clone(); 522 // Used for tracking fixed input assignments while `!inputs_done`: 523 self.regs_out = RegisterSet::new(); 524 self.moves.clear(); 525 self.fills.clear(); 526 } 527 528 /// Add a fixed input reassignment of `value`. 529 /// 530 /// This means that `value` must be assigned to `to` and can't become a variable. Call with 531 /// `from == to` to ensure that `value` is not reassigned from its existing register location. 532 /// 533 /// In either case, `to` will not be available for variables on the input side of the 534 /// instruction. reassign_in(&mut self, value: Value, rc: RegClass, from: RegUnit, to: RegUnit)535 pub fn reassign_in(&mut self, value: Value, rc: RegClass, from: RegUnit, to: RegUnit) { 536 log::trace!( 537 "reassign_in({}:{}, {} -> {})", 538 value, 539 rc, 540 rc.info.display_regunit(from), 541 rc.info.display_regunit(to) 542 ); 543 debug_assert!(!self.inputs_done); 544 if self.regs_in.is_avail(rc, from) { 545 // It looks like `value` was already removed from the register set. It must have been 546 // added as a variable previously. A fixed constraint beats a variable, so convert it. 547 if let Some(idx) = self.vars.iter().position(|v| v.value == value) { 548 let v = self.vars.remove(idx); 549 log::trace!("-> converting variable {} to a fixed constraint", v); 550 // The spiller is responsible for ensuring that all constraints on the uses of a 551 // value are compatible. 552 debug_assert!( 553 v.constraint.contains(to), 554 "Incompatible constraints for {}", 555 value 556 ); 557 } else { 558 panic!("Invalid from register for fixed {} constraint", value); 559 } 560 } 561 self.regs_in.free(rc, from); 562 self.regs_out.take(rc, to); 563 self.assignments.insert(Assignment { 564 value, 565 rc, 566 from, 567 to, 568 }); 569 } 570 571 /// Add a variable representing an input side value with an existing register assignment. 572 /// 573 /// A variable is a value that should be reassigned to something in the `constraint` register 574 /// class. 575 /// 576 /// It is assumed initially that the value is also live on the output side of the instruction. 577 /// This can be changed by calling to `add_kill()`. 578 /// 579 /// This function can only be used before calling `inputs_done()`. Afterwards, more input-side 580 /// variables can be added by calling `add_killed_var()` and `add_through_var()` add_var(&mut self, value: Value, constraint: RegClass, from: RegUnit)581 pub fn add_var(&mut self, value: Value, constraint: RegClass, from: RegUnit) { 582 log::trace!( 583 "add_var({}:{}, from={})", 584 value, 585 constraint, 586 constraint.info.display_regunit(from) 587 ); 588 debug_assert!(!self.inputs_done); 589 self.add_live_var(value, constraint, from, true); 590 } 591 592 /// Add an extra input-side variable representing a value that is killed by the current 593 /// instruction. 594 /// 595 /// This function should be called after `inputs_done()` only. Use `add_var()` before. add_killed_var(&mut self, value: Value, rc: RegClass, from: RegUnit)596 pub fn add_killed_var(&mut self, value: Value, rc: RegClass, from: RegUnit) { 597 log::trace!( 598 "add_killed_var({}:{}, from={})", 599 value, 600 rc, 601 rc.info.display_regunit(from) 602 ); 603 debug_assert!(self.inputs_done); 604 self.add_live_var(value, rc, from, false); 605 } 606 607 /// Add an extra input-side variable representing a value that is live through the current 608 /// instruction. 609 /// 610 /// This function should be called after `inputs_done()` only. Use `add_var()` before. add_through_var(&mut self, value: Value, rc: RegClass, from: RegUnit)611 pub fn add_through_var(&mut self, value: Value, rc: RegClass, from: RegUnit) { 612 log::trace!( 613 "add_through_var({}:{}, from={})", 614 value, 615 rc, 616 rc.info.display_regunit(from) 617 ); 618 debug_assert!(self.inputs_done); 619 self.add_live_var(value, rc, from, true); 620 } 621 622 /// Shared code for `add_var`, `add_killed_var`, and `add_through_var`. 623 /// 624 /// Add a variable that is live before the instruction, and possibly live through. Merge 625 /// constraints if the value has already been added as a variable or fixed assignment. add_live_var(&mut self, value: Value, rc: RegClass, from: RegUnit, live_through: bool)626 fn add_live_var(&mut self, value: Value, rc: RegClass, from: RegUnit, live_through: bool) { 627 // Check for existing entries for this value. 628 if !self.can_add_var(rc, from) { 629 // There could be an existing variable entry. 630 if let Some(v) = self.vars.iter_mut().find(|v| v.value == value) { 631 // We have an existing variable entry for `value`. Combine the constraints. 632 if let Some(rc) = v.constraint.intersect(rc) { 633 log::trace!("-> combining constraint with {} yields {}", v, rc); 634 v.constraint = rc; 635 return; 636 } else { 637 // The spiller should have made sure the same value is not used with disjoint 638 // constraints. 639 panic!("Incompatible constraints: {} + {}", rc, v) 640 } 641 } 642 643 // No variable, then it must be a fixed reassignment. 644 if let Some(a) = self.assignments.get(value) { 645 log::trace!("-> already fixed assignment {}", a); 646 debug_assert!(rc.contains(a.to), "Incompatible constraints for {}", value); 647 return; 648 } 649 650 log::trace!("{}", self); 651 panic!("Wrong from register for {}", value); 652 } 653 654 let new_var = Variable::new_live(value, rc, from, live_through); 655 log::trace!("-> new var: {}", new_var); 656 657 self.regs_in.free(rc, from); 658 if self.inputs_done && live_through { 659 self.regs_out.free(rc, from); 660 } 661 self.vars.push(new_var); 662 } 663 664 /// Check for conflicts between fixed input assignments and existing live values. 665 /// 666 /// Returns true if one of the live values conflicts with a fixed input assignment. Such a 667 /// conflicting value must be turned into a variable. has_fixed_input_conflicts(&self) -> bool668 pub fn has_fixed_input_conflicts(&self) -> bool { 669 debug_assert!(!self.inputs_done); 670 // The `from` side of the fixed input diversions are taken from `regs_out`. 671 self.regs_out.interferes_with(&self.regs_in) 672 } 673 674 /// Check if `rc, reg` specifically conflicts with the fixed input assignments. is_fixed_input_conflict(&self, rc: RegClass, reg: RegUnit) -> bool675 pub fn is_fixed_input_conflict(&self, rc: RegClass, reg: RegUnit) -> bool { 676 debug_assert!(!self.inputs_done); 677 !self.regs_out.is_avail(rc, reg) 678 } 679 680 /// Finish adding input side constraints. 681 /// 682 /// Call this method to indicate that there will be no more fixed input reassignments added 683 /// and prepare for the output side constraints. inputs_done(&mut self)684 pub fn inputs_done(&mut self) { 685 debug_assert!(!self.has_fixed_input_conflicts()); 686 687 // At this point, `regs_out` contains the `to` side of the input reassignments, and the 688 // `from` side has already been marked as available in `regs_in`. 689 // 690 // Remove the `to` assignments from `regs_in` so it now indicates the registers available 691 // to variables at the input side. 692 self.regs_in.intersect(&self.regs_out); 693 694 // The meaning of `regs_out` now changes completely to indicate the registers available to 695 // variables on the output side. 696 // The initial mask will be modified by `add_kill()` and `add_fixed_output()`. 697 self.regs_out = self.regs_in.clone(); 698 699 // Now we can't add more fixed input assignments, but `add_var()` is still allowed. 700 self.inputs_done = true; 701 } 702 703 /// Record that an input register value is killed by the instruction. 704 /// 705 /// Even if a fixed reassignment has been added for the value, the `reg` argument should be the 706 /// original location before the reassignments. 707 /// 708 /// This means that the register is available on the output side. add_kill(&mut self, value: Value, rc: RegClass, reg: RegUnit)709 pub fn add_kill(&mut self, value: Value, rc: RegClass, reg: RegUnit) { 710 debug_assert!(self.inputs_done); 711 712 // If a fixed assignment is killed, the `to` register becomes available on the output side. 713 if let Some(a) = self.assignments.get(value) { 714 debug_assert_eq!(a.from, reg); 715 self.regs_out.free(a.rc, a.to); 716 return; 717 } 718 719 // It's also possible that a variable is killed. That means it doesn't need to satisfy 720 // interference constraints on the output side. 721 // Variables representing tied operands will get their `is_output` flag set again later. 722 if let Some(v) = self.vars.iter_mut().find(|v| v.value == value) { 723 debug_assert!(v.is_input); 724 v.is_output = false; 725 return; 726 } 727 728 // Alright, this is just a boring value being killed by the instruction. Just reclaim 729 // the assigned register. 730 self.regs_out.free(rc, reg); 731 } 732 733 /// Record that an input register is tied to an output register. 734 /// 735 /// It is assumed that `add_kill` was called previously with the same arguments. 736 /// 737 /// The output value that must have the same register as the input value is not recorded in the 738 /// solver. 739 /// 740 /// If the value has already been assigned to a fixed register, return that. add_tied_input( &mut self, value: Value, rc: RegClass, reg: RegUnit, is_global: bool, ) -> Option<RegUnit>741 pub fn add_tied_input( 742 &mut self, 743 value: Value, 744 rc: RegClass, 745 reg: RegUnit, 746 is_global: bool, 747 ) -> Option<RegUnit> { 748 debug_assert!(self.inputs_done); 749 750 // If a fixed assignment is tied, the `to` register is not available on the output side. 751 if let Some(a) = self.assignments.get(value) { 752 debug_assert_eq!(a.from, reg); 753 self.regs_out.take(a.rc, a.to); 754 return Some(a.to); 755 } 756 757 // Check if a variable was created. 758 if let Some(v) = self.vars.iter_mut().find(|v| v.value == value) { 759 debug_assert!(v.is_input); 760 v.is_output = true; 761 v.is_global = is_global; 762 return None; 763 } 764 765 // No variable exists for `value` because its constraints are already satisfied. 766 // However, if the tied output value has a global live range, we must create a variable to 767 // avoid global interference too. 768 if is_global { 769 let mut new_var = Variable::new_live(value, rc, reg, true); 770 new_var.is_global = true; 771 log::trace!("add_tied_input: new tied-global value: {}", new_var); 772 self.vars.push(new_var); 773 self.regs_in.free(rc, reg); 774 } else { 775 self.regs_out.take(rc, reg); 776 } 777 778 None 779 } 780 781 /// Add a fixed output assignment. 782 /// 783 /// This means that `to` will not be available for variables on the output side of the 784 /// instruction. 785 /// 786 /// Returns `false` if a live value conflicts with `to`, so it couldn't be added. Find the 787 /// conflicting live-through value and turn it into a variable before calling this method 788 /// again. 789 #[allow(dead_code)] add_fixed_output(&mut self, rc: RegClass, reg: RegUnit) -> bool790 pub fn add_fixed_output(&mut self, rc: RegClass, reg: RegUnit) -> bool { 791 debug_assert!(self.inputs_done); 792 if self.regs_out.is_avail(rc, reg) { 793 self.regs_out.take(rc, reg); 794 true 795 } else { 796 false 797 } 798 } 799 800 /// Add a defined output value. 801 /// 802 /// This is similar to `add_var`, except the value doesn't have a prior register assignment. add_def(&mut self, value: Value, constraint: RegClass, is_global: bool)803 pub fn add_def(&mut self, value: Value, constraint: RegClass, is_global: bool) { 804 debug_assert!(self.inputs_done); 805 self.vars 806 .push(Variable::new_def(value, constraint, is_global)); 807 } 808 809 /// Clear the `is_global` flag on all solver variables. 810 /// 811 /// This is used when there are not enough global registers available, and global defines have 812 /// to be replaced with local defines followed by a copy. clear_all_global_flags(&mut self)813 pub fn clear_all_global_flags(&mut self) { 814 for v in &mut self.vars { 815 v.is_global = false; 816 } 817 } 818 } 819 820 /// Error reported when the solver fails to find a solution with the current constraints. 821 /// 822 /// When no solution can be found, the error indicates how constraints could be loosened to help. 823 pub enum SolverError { 824 /// There are not available registers in the given register class. 825 /// 826 /// This should be resolved by turning live-through values into variables so they can be moved 827 /// out of the way. 828 Divert(RegClass), 829 830 /// There are insufficient available registers in the global set to assign an `is_global` 831 /// variable with the given value. 832 /// 833 /// This should be resolved by converting the variable to a local one. 834 Global(Value), 835 } 836 837 /// Interface for searching for a solution. 838 impl Solver { 839 /// Try a quick-and-dirty solution. 840 /// 841 /// This is expected to succeed for most instructions since the constraint problem is almost 842 /// always trivial. 843 /// 844 /// Returns `Ok(regs)` if a solution was found. quick_solve( &mut self, global_regs: &RegisterSet, is_reload: bool, ) -> Result<RegisterSet, SolverError>845 pub fn quick_solve( 846 &mut self, 847 global_regs: &RegisterSet, 848 is_reload: bool, 849 ) -> Result<RegisterSet, SolverError> { 850 self.find_solution(global_regs, is_reload) 851 } 852 853 /// Try harder to find a solution. 854 /// 855 /// Call this method after `quick_solve()` fails. 856 /// 857 /// This may return an error with a register class that has run out of registers. If registers 858 /// can be freed up in the starving class, this method can be called again after adding 859 /// variables for the freed registers. real_solve( &mut self, global_regs: &RegisterSet, is_reload: bool, ) -> Result<RegisterSet, SolverError>860 pub fn real_solve( 861 &mut self, 862 global_regs: &RegisterSet, 863 is_reload: bool, 864 ) -> Result<RegisterSet, SolverError> { 865 // Compute domain sizes for all the variables given the current register sets. 866 for v in &mut self.vars { 867 let d = v.iter(&self.regs_in, &self.regs_out, global_regs).len(); 868 v.domain = cmp::min(d, u16::MAX as usize) as u16; 869 } 870 871 // Solve for vars with small domains first to increase the chance of finding a solution. 872 // 873 // Also consider this case: 874 // 875 // v0: out, global 876 // v1: in 877 // v2: in+out 878 // 879 // If only %r0 and %r1 are available, the global constraint may cause us to assign: 880 // 881 // v0 -> %r1 882 // v1 -> %r0 883 // v2 -> ! 884 // 885 // Usually in+out variables will have a smaller domain, but in the above case the domain 886 // size is the same, so we also prioritize in+out variables. 887 // 888 // Include the reversed previous solution for this variable partly as a stable tie breaker, 889 // partly to shake things up on a second attempt. 890 // 891 // Use the `from` register and value number as a tie breaker to get a stable sort. 892 self.vars.sort_unstable_by_key(|v| { 893 ( 894 v.domain, 895 !(v.is_input && v.is_output), 896 !v.solution, 897 v.from.unwrap_or(0), 898 v.value, 899 ) 900 }); 901 902 log::trace!("real_solve for {}", self); 903 self.find_solution(global_regs, is_reload) 904 } 905 906 /// Search for a solution with the current list of variables. 907 /// 908 /// If a solution was found, returns `Ok(regs)` with the set of available registers on the 909 /// output side after the solution. If no solution could be found, returns `Err(rc)` with the 910 /// constraint register class that needs more available registers. find_solution( &mut self, global_regs: &RegisterSet, is_reload: bool, ) -> Result<RegisterSet, SolverError>911 fn find_solution( 912 &mut self, 913 global_regs: &RegisterSet, 914 is_reload: bool, 915 ) -> Result<RegisterSet, SolverError> { 916 // Available registers on the input and output sides respectively. 917 let mut iregs = self.regs_in.clone(); 918 let mut oregs = self.regs_out.clone(); 919 let mut gregs = global_regs.clone(); 920 921 for v in &mut self.vars { 922 let rc = v.constraint; 923 924 // Decide which register to assign. In order to try and keep registers holding 925 // reloaded values separate from all other registers to the extent possible, we choose 926 // the first available register in the normal case, but the last available one in the 927 // case of a reload. See "A side note on register choice heuristics" in 928 // src/redundant_reload_remover.rs for further details. 929 let mut reg_set_iter = v.iter(&iregs, &oregs, &gregs); 930 let maybe_reg = if is_reload { 931 reg_set_iter.rnext() 932 } else { 933 reg_set_iter.next() 934 }; 935 936 let reg = match maybe_reg { 937 Some(reg) => reg, 938 None => { 939 // If `v` must avoid global interference, there is not point in requesting 940 // live registers be diverted. We need to make it a non-global value. 941 if v.is_global && gregs.iter(rc).next().is_none() { 942 return Err(SolverError::Global(v.value)); 943 } 944 return Err(SolverError::Divert(rc)); 945 } 946 }; 947 948 v.solution = reg; 949 if v.is_input { 950 iregs.take(rc, reg); 951 } 952 if v.is_output { 953 oregs.take(rc, reg); 954 } 955 if v.is_global { 956 gregs.take(rc, reg); 957 } 958 } 959 960 Ok(oregs) 961 } 962 963 /// Get all the variables. vars(&self) -> &[Variable]964 pub fn vars(&self) -> &[Variable] { 965 &self.vars 966 } 967 968 /// Check if `value` can be added as a variable to help find a solution. can_add_var(&mut self, constraint: RegClass, from: RegUnit) -> bool969 pub fn can_add_var(&mut self, constraint: RegClass, from: RegUnit) -> bool { 970 !self.regs_in.is_avail(constraint, from) 971 && !self.vars.iter().any(|var| var.from == Some(from)) 972 } 973 } 974 975 /// Interface for working with parallel copies once a solution has been found. 976 impl Solver { 977 /// Collect all the register moves we need to execute. collect_moves(&mut self)978 fn collect_moves(&mut self) { 979 self.moves.clear(); 980 981 // Collect moves from the chosen solution for all non-define variables. 982 for v in &self.vars { 983 if let Some(from) = v.from { 984 // Omit variable solutions that don't require the value to be moved. 985 if from != v.solution { 986 self.moves.push(Move::Reg { 987 value: v.value, 988 from, 989 to: v.solution, 990 rc: v.constraint, 991 }); 992 } 993 } 994 } 995 996 // Convert all of the fixed register assignments into moves, but omit the ones that are 997 // already in the right register. 998 self.moves 999 .extend(self.assignments.values().filter_map(Move::with_assignment)); 1000 1001 if !self.moves.is_empty() { 1002 log::trace!("collect_moves: {}", DisplayList(&self.moves)); 1003 } 1004 } 1005 1006 /// Try to schedule a sequence of `regmove` instructions that will shuffle registers into 1007 /// place. 1008 /// 1009 /// This may require the use of additional available registers, and it can fail if no 1010 /// additional registers are available. 1011 /// 1012 /// TODO: Handle failure by generating a sequence of register swaps, or by temporarily spilling 1013 /// a register. 1014 /// 1015 /// Returns the number of spills that had to be emitted. schedule_moves(&mut self, regs: &RegisterSet) -> usize1016 pub fn schedule_moves(&mut self, regs: &RegisterSet) -> usize { 1017 self.collect_moves(); 1018 debug_assert!(self.fills.is_empty()); 1019 1020 let mut num_spill_slots = 0; 1021 let mut avail = regs.clone(); 1022 let mut i = 0; 1023 while i < self.moves.len() + self.fills.len() { 1024 // Don't even look at the fills until we've spent all the moves. Deferring these lets 1025 // us potentially reuse the claimed registers to resolve multiple cycles. 1026 if i >= self.moves.len() { 1027 self.moves.append(&mut self.fills); 1028 } 1029 1030 // Find the first move that can be executed now. 1031 if let Some(j) = self.moves[i..].iter().position(|m| match m.to_reg() { 1032 Some((rc, reg)) => avail.is_avail(rc, reg), 1033 None => true, 1034 }) { 1035 // This move can be executed now. 1036 self.moves.swap(i, i + j); 1037 let m = &self.moves[i]; 1038 if let Some((rc, reg)) = m.to_reg() { 1039 avail.take(rc, reg); 1040 } 1041 if let Some((rc, reg)) = m.from_reg() { 1042 avail.free(rc, reg); 1043 } 1044 log::trace!("move #{}: {}", i, m); 1045 i += 1; 1046 continue; 1047 } 1048 1049 // When we get here, none of the `moves[i..]` can be executed. This means there are 1050 // only cycles remaining. The cycles can be broken in a few ways: 1051 // 1052 // 1. Grab an available register and use it to break a cycle. 1053 // 2. Move a value temporarily into a stack slot instead of a register. 1054 // 3. Use swap instructions. 1055 // 1056 // TODO: So far we only implement 1 and 2. 1057 1058 // Pick an assignment with the largest possible width. This is more likely to break up 1059 // a cycle than an assignment with fewer register units. For example, it may be 1060 // necessary to move two arm32 S-registers out of the way before a D-register can move 1061 // into place. 1062 // 1063 // We use `min_by_key` and `!` instead of `max_by_key` because it preserves the 1064 // existing order of moves with the same width. 1065 let j = self.moves[i..] 1066 .iter() 1067 .enumerate() 1068 .min_by_key(|&(_, m)| !m.rc().width) 1069 .unwrap() 1070 .0; 1071 self.moves.swap(i, i + j); 1072 1073 // Check the top-level register class for an available register. It is an axiom of the 1074 // register allocator that we can move between all registers in the top-level RC. 1075 let m = self.moves[i].clone(); 1076 let toprc = m.rc().toprc(); 1077 if let Some(reg) = avail.iter(toprc).next() { 1078 log::trace!( 1079 "breaking cycle at {} with available {} register {}", 1080 m, 1081 toprc, 1082 toprc.info.display_regunit(reg) 1083 ); 1084 1085 // Alter the move so it is guaranteed to be picked up when we loop. It is important 1086 // that this move is scheduled immediately, otherwise we would have multiple moves 1087 // of the same value, and they would not be commutable. 1088 let old_to_reg = self.moves[i].replace_to_reg(reg); 1089 // Append a fixup move so we end up in the right place. This move will be scheduled 1090 // later. That's ok because it is the single remaining move of `m.value` after the 1091 // next iteration. 1092 self.moves.push(Move::Reg { 1093 value: m.value(), 1094 rc: toprc, 1095 from: reg, 1096 to: old_to_reg, 1097 }); 1098 // TODO: What if allocating an extra register is not enough to break a cycle? This 1099 // can happen when there are registers of different widths in a cycle. For ARM, we 1100 // may have to move two S-registers out of the way before we can resolve a cycle 1101 // involving a D-register. 1102 continue; 1103 } 1104 1105 // It was impossible to free up a register in toprc, so use an emergency spill slot as 1106 // a last resort. 1107 let slot = num_spill_slots; 1108 num_spill_slots += 1; 1109 log::trace!("breaking cycle at {} with slot {}", m, slot); 1110 let old_to_reg = self.moves[i].change_to_spill(slot); 1111 self.fills.push(Move::Fill { 1112 value: m.value(), 1113 rc: toprc, 1114 from_slot: slot, 1115 to: old_to_reg, 1116 }); 1117 } 1118 1119 num_spill_slots 1120 } 1121 1122 /// Borrow the scheduled set of register moves that was computed by `schedule_moves()`. moves(&self) -> &[Move]1123 pub fn moves(&self) -> &[Move] { 1124 &self.moves 1125 } 1126 } 1127 1128 impl fmt::Display for Solver { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result1129 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 1130 let reginfo = self.vars.first().map(|v| v.constraint.info); 1131 writeln!(f, "Solver {{ inputs_done: {},", self.inputs_done)?; 1132 writeln!(f, " in: {}", self.regs_in.display(reginfo))?; 1133 writeln!(f, " out: {}", self.regs_out.display(reginfo))?; 1134 writeln!( 1135 f, 1136 " assignments: {}", 1137 DisplayList(self.assignments.as_slice()) 1138 )?; 1139 writeln!(f, " vars: {}", DisplayList(&self.vars))?; 1140 writeln!(f, " moves: {}", DisplayList(&self.moves))?; 1141 writeln!(f, "}}") 1142 } 1143 } 1144 1145 #[cfg(test)] 1146 #[cfg(feature = "arm32")] 1147 mod tests { 1148 use super::{Move, Solver}; 1149 use crate::entity::EntityRef; 1150 use crate::ir::Value; 1151 use crate::isa::registers::{RegBank, RegClassData}; 1152 use crate::isa::{RegClass, RegInfo, RegUnit}; 1153 use crate::regalloc::RegisterSet; 1154 use core::borrow::Borrow; 1155 1156 // Arm32 `TargetIsa` is now `TargetIsaAdapter`, which does not hold any info 1157 // about registers, so we directly access `INFO` from registers-arm32.rs. 1158 include!(concat!(env!("OUT_DIR"), "/registers-arm32.rs")); 1159 1160 // Get a register class by name. rc_by_name(reginfo: &RegInfo, name: &str) -> RegClass1161 fn rc_by_name(reginfo: &RegInfo, name: &str) -> RegClass { 1162 reginfo 1163 .classes 1164 .iter() 1165 .find(|rc| rc.name == name) 1166 .expect("Can't find named register class.") 1167 } 1168 1169 // Construct a register move. mov(value: Value, rc: RegClass, from: RegUnit, to: RegUnit) -> Move1170 fn mov(value: Value, rc: RegClass, from: RegUnit, to: RegUnit) -> Move { 1171 Move::Reg { 1172 value, 1173 rc, 1174 from, 1175 to, 1176 } 1177 } 1178 spill(value: Value, rc: RegClass, from: RegUnit, to_slot: usize) -> Move1179 fn spill(value: Value, rc: RegClass, from: RegUnit, to_slot: usize) -> Move { 1180 Move::Spill { 1181 value, 1182 rc, 1183 from, 1184 to_slot, 1185 } 1186 } 1187 fill(value: Value, rc: RegClass, from_slot: usize, to: RegUnit) -> Move1188 fn fill(value: Value, rc: RegClass, from_slot: usize, to: RegUnit) -> Move { 1189 Move::Fill { 1190 value, 1191 rc, 1192 from_slot, 1193 to, 1194 } 1195 } 1196 1197 #[test] simple_moves()1198 fn simple_moves() { 1199 let reginfo = INFO.borrow(); 1200 let gpr = rc_by_name(®info, "GPR"); 1201 let r0 = gpr.unit(0); 1202 let r1 = gpr.unit(1); 1203 let r2 = gpr.unit(2); 1204 let gregs = RegisterSet::new(); 1205 let mut regs = RegisterSet::new(); 1206 let mut solver = Solver::new(); 1207 let v10 = Value::new(10); 1208 let v11 = Value::new(11); 1209 1210 // As simple as it gets: Value is in r1, we want r0. 1211 regs.take(gpr, r1); 1212 solver.reset(®s); 1213 solver.reassign_in(v10, gpr, r1, r0); 1214 solver.inputs_done(); 1215 assert!(solver.quick_solve(&gregs, false).is_ok()); 1216 assert_eq!(solver.schedule_moves(®s), 0); 1217 assert_eq!(solver.moves(), &[mov(v10, gpr, r1, r0)]); 1218 1219 // A bit harder: r0, r1 need to go in r1, r2. 1220 regs.take(gpr, r0); 1221 solver.reset(®s); 1222 solver.reassign_in(v10, gpr, r0, r1); 1223 solver.reassign_in(v11, gpr, r1, r2); 1224 solver.inputs_done(); 1225 assert!(solver.quick_solve(&gregs, false).is_ok()); 1226 assert_eq!(solver.schedule_moves(®s), 0); 1227 assert_eq!( 1228 solver.moves(), 1229 &[mov(v11, gpr, r1, r2), mov(v10, gpr, r0, r1)] 1230 ); 1231 1232 // Swap r0 and r1 in three moves using r2 as a scratch. 1233 solver.reset(®s); 1234 solver.reassign_in(v10, gpr, r0, r1); 1235 solver.reassign_in(v11, gpr, r1, r0); 1236 solver.inputs_done(); 1237 assert!(solver.quick_solve(&gregs, false).is_ok()); 1238 assert_eq!(solver.schedule_moves(®s), 0); 1239 assert_eq!( 1240 solver.moves(), 1241 &[ 1242 mov(v10, gpr, r0, r2), 1243 mov(v11, gpr, r1, r0), 1244 mov(v10, gpr, r2, r1), 1245 ] 1246 ); 1247 } 1248 1249 #[test] harder_move_cycles()1250 fn harder_move_cycles() { 1251 let reginfo = INFO.borrow(); 1252 let s = rc_by_name(®info, "S"); 1253 let d = rc_by_name(®info, "D"); 1254 let d0 = d.unit(0); 1255 let d1 = d.unit(1); 1256 let d2 = d.unit(2); 1257 let s0 = s.unit(0); 1258 let s1 = s.unit(1); 1259 let s2 = s.unit(2); 1260 let s3 = s.unit(3); 1261 let gregs = RegisterSet::new(); 1262 let mut regs = RegisterSet::new(); 1263 let mut solver = Solver::new(); 1264 let v10 = Value::new(10); 1265 let v11 = Value::new(11); 1266 let v12 = Value::new(12); 1267 1268 // Not a simple cycle: Swap d0 <-> (s2, s3) 1269 regs.take(d, d0); 1270 regs.take(d, d1); 1271 solver.reset(®s); 1272 solver.reassign_in(v10, d, d0, d1); 1273 solver.reassign_in(v11, s, s2, s0); 1274 solver.reassign_in(v12, s, s3, s1); 1275 solver.inputs_done(); 1276 assert!(solver.quick_solve(&gregs, false).is_ok()); 1277 assert_eq!(solver.schedule_moves(®s), 0); 1278 assert_eq!( 1279 solver.moves(), 1280 &[ 1281 mov(v10, d, d0, d2), 1282 mov(v11, s, s2, s0), 1283 mov(v12, s, s3, s1), 1284 mov(v10, d, d2, d1), 1285 ] 1286 ); 1287 1288 // Same problem in the other direction: Swap (s0, s1) <-> d1. 1289 // 1290 // If we divert the moves in order, we will need to allocate *two* temporary S registers. A 1291 // trivial algorithm might assume that allocating a single temp is enough. 1292 solver.reset(®s); 1293 solver.reassign_in(v11, s, s0, s2); 1294 solver.reassign_in(v12, s, s1, s3); 1295 solver.reassign_in(v10, d, d1, d0); 1296 solver.inputs_done(); 1297 assert!(solver.quick_solve(&gregs, false).is_ok()); 1298 assert_eq!(solver.schedule_moves(®s), 0); 1299 assert_eq!( 1300 solver.moves(), 1301 &[ 1302 mov(v10, d, d1, d2), 1303 mov(v12, s, s1, s3), 1304 mov(v11, s, s0, s2), 1305 mov(v10, d, d2, d0), 1306 ] 1307 ); 1308 } 1309 1310 #[test] emergency_spill()1311 fn emergency_spill() { 1312 let reginfo = INFO.borrow(); 1313 let gpr = rc_by_name(®info, "GPR"); 1314 let r0 = gpr.unit(0); 1315 let r1 = gpr.unit(1); 1316 let r2 = gpr.unit(2); 1317 let r3 = gpr.unit(3); 1318 let r4 = gpr.unit(4); 1319 let r5 = gpr.unit(5); 1320 let gregs = RegisterSet::new(); 1321 let mut regs = RegisterSet::new(); 1322 let mut solver = Solver::new(); 1323 let v10 = Value::new(10); 1324 let v11 = Value::new(11); 1325 let v12 = Value::new(12); 1326 let v13 = Value::new(13); 1327 let v14 = Value::new(14); 1328 let v15 = Value::new(15); 1329 1330 // Claim r0--r2 and r3--r15 for other values. 1331 for i in 0..16 { 1332 regs.take(gpr, gpr.unit(i)); 1333 } 1334 1335 // Request a permutation cycle. 1336 solver.reset(®s); 1337 solver.reassign_in(v10, gpr, r0, r1); 1338 solver.reassign_in(v11, gpr, r1, r2); 1339 solver.reassign_in(v12, gpr, r2, r0); 1340 solver.inputs_done(); 1341 assert!(solver.quick_solve(&gregs, false).is_ok()); 1342 assert_eq!(solver.schedule_moves(®s), 1); 1343 assert_eq!( 1344 solver.moves(), 1345 &[ 1346 spill(v10, gpr, r0, 0), 1347 mov(v12, gpr, r2, r0), 1348 mov(v11, gpr, r1, r2), 1349 fill(v10, gpr, 0, r1), 1350 ] 1351 ); 1352 1353 // Two cycles should only require a single spill. 1354 solver.reset(®s); 1355 // Cycle 1. 1356 solver.reassign_in(v10, gpr, r0, r1); 1357 solver.reassign_in(v11, gpr, r1, r2); 1358 solver.reassign_in(v12, gpr, r2, r0); 1359 // Cycle 2. 1360 solver.reassign_in(v13, gpr, r3, r4); 1361 solver.reassign_in(v14, gpr, r4, r5); 1362 solver.reassign_in(v15, gpr, r5, r3); 1363 1364 solver.inputs_done(); 1365 assert!(solver.quick_solve(&gregs, false).is_ok()); 1366 // We resolve two cycles with one spill. 1367 assert_eq!(solver.schedule_moves(®s), 1); 1368 assert_eq!( 1369 solver.moves(), 1370 &[ 1371 spill(v10, gpr, r0, 0), 1372 mov(v12, gpr, r2, r0), 1373 mov(v11, gpr, r1, r2), 1374 mov(v13, gpr, r3, r1), // Use available r1 to break cycle 2. 1375 mov(v15, gpr, r5, r3), 1376 mov(v14, gpr, r4, r5), 1377 mov(v13, gpr, r1, r4), 1378 fill(v10, gpr, 0, r1), // Finally complete cycle 1. 1379 ] 1380 ); 1381 } 1382 } 1383