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