raassignment_p.h (17038B)
1 // This file is part of AsmJit project <https://asmjit.com> 2 // 3 // See <asmjit/core.h> or LICENSE.md for license and copyright information 4 // SPDX-License-Identifier: Zlib 5 6 #ifndef ASMJIT_CORE_RAASSIGNMENT_P_H_INCLUDED 7 #define ASMJIT_CORE_RAASSIGNMENT_P_H_INCLUDED 8 9 #include "../core/api-config.h" 10 #ifndef ASMJIT_NO_COMPILER 11 12 #include "../core/radefs_p.h" 13 #include "../core/rareg_p.h" 14 15 ASMJIT_BEGIN_NAMESPACE 16 17 //! \cond INTERNAL 18 //! \addtogroup asmjit_ra 19 //! \{ 20 21 //! Holds the current register assignment. 22 //! 23 //! Has two purposes: 24 //! 25 //! 1. Holds register assignment of a local register allocator (see \ref RALocalAllocator). 26 //! 2. Holds register assignment of the entry of basic blocks (see \ref RABlock). 27 class RAAssignment { 28 public: 29 ASMJIT_NONCOPYABLE(RAAssignment) 30 31 static inline constexpr uint32_t kPhysNone = 0xFF; 32 33 enum DirtyBit : uint32_t { 34 kClean = 0, 35 kDirty = 1 36 }; 37 38 struct Layout { 39 //! Index of architecture registers per group. 40 RARegIndex phys_index; 41 //! Count of architecture registers per group. 42 RARegCount phys_count; 43 //! Count of physical registers of all groups. 44 uint32_t phys_total; 45 //! Count of work registers. 46 uint32_t work_count; 47 //! WorkRegs data (vector). 48 const ArenaVector<RAWorkReg*>* work_regs; 49 50 inline void reset() noexcept { 51 phys_index.reset(); 52 phys_count.reset(); 53 phys_total = 0; 54 work_count = 0; 55 work_regs = nullptr; 56 } 57 }; 58 59 struct PhysToWorkMap { 60 //! Assigned registers (each bit represents one physical reg). 61 RARegMask assigned; 62 //! Dirty registers (spill slot out of sync or no spill slot). 63 RARegMask dirty; 64 //! PhysReg to WorkReg mapping. 65 RAWorkId work_ids[1 /* ... */]; 66 67 [[nodiscard]] 68 static ASMJIT_INLINE_NODEBUG size_t size_of(size_t count) noexcept { 69 return Arena::aligned_size(sizeof(PhysToWorkMap) - sizeof(uint32_t) + count * sizeof(uint32_t)); 70 } 71 72 ASMJIT_INLINE void reset(size_t count) noexcept { 73 assigned.reset(); 74 dirty.reset(); 75 76 for (size_t i = 0; i < count; i++) { 77 work_ids[i] = kBadWorkId; 78 } 79 } 80 81 ASMJIT_INLINE void copy_from(const PhysToWorkMap* other, size_t count) noexcept { 82 size_t size = size_of(count); 83 memcpy(this, other, size); 84 } 85 86 ASMJIT_INLINE void unassign(RegGroup group, uint32_t phys_id, uint32_t index_in_work_ids) noexcept { 87 assigned.clear(group, Support::bit_mask<RegMask>(phys_id)); 88 dirty.clear(group, Support::bit_mask<RegMask>(phys_id)); 89 work_ids[index_in_work_ids] = kBadWorkId; 90 } 91 }; 92 93 struct WorkToPhysMap { 94 //! WorkReg to PhysReg mapping 95 uint8_t phys_ids[1 /* ... */]; 96 97 [[nodiscard]] 98 static ASMJIT_INLINE_NODEBUG size_t size_of(size_t count) noexcept { 99 return Arena::aligned_size(size_t(count) * sizeof(uint8_t)); 100 } 101 102 ASMJIT_INLINE void reset(size_t count) noexcept { 103 for (size_t i = 0; i < count; i++) { 104 phys_ids[i] = kPhysNone; 105 } 106 } 107 108 ASMJIT_INLINE void copy_from(const WorkToPhysMap* other, size_t count) noexcept { 109 size_t size = size_of(count); 110 if (ASMJIT_LIKELY(size)) { 111 memcpy(this, other, size); 112 } 113 } 114 }; 115 116 //! \name Members 117 //! \{ 118 119 //! Physical registers layout. 120 Layout _layout; 121 //! WorkReg to PhysReg mapping. 122 WorkToPhysMap* _work_to_phys_map; 123 //! PhysReg to WorkReg mapping and assigned/dirty bits. 124 PhysToWorkMap* _phys_to_work_map; 125 //! Optimization to translate PhysRegs to WorkRegs faster. 126 Support::Array<RAWorkId*, Globals::kNumVirtGroups> _phys_to_work_ids; 127 128 //! \} 129 130 //! \name Construction & Destruction 131 //! \{ 132 133 inline RAAssignment() noexcept { 134 _layout.reset(); 135 reset_maps(); 136 } 137 138 ASMJIT_INLINE void init_layout(const RARegCount& phys_count, const ArenaVector<RAWorkReg*>& work_regs) noexcept { 139 // Layout must be initialized before data. 140 ASMJIT_ASSERT(_phys_to_work_map == nullptr); 141 ASMJIT_ASSERT(_work_to_phys_map == nullptr); 142 143 _layout.phys_index.build_indexes(phys_count); 144 _layout.phys_count = phys_count; 145 _layout.phys_total = uint32_t(_layout.phys_index[RegGroup::kMaxVirt]) + 146 uint32_t(_layout.phys_count[RegGroup::kMaxVirt]) ; 147 _layout.work_count = uint32_t(work_regs.size()); 148 _layout.work_regs = &work_regs; 149 } 150 151 ASMJIT_INLINE void init_maps(PhysToWorkMap* phys_to_work_map, WorkToPhysMap* work_to_phys_map) noexcept { 152 _phys_to_work_map = phys_to_work_map; 153 _work_to_phys_map = work_to_phys_map; 154 for (RegGroup group : Support::enumerate(RegGroup::kMaxVirt)) { 155 _phys_to_work_ids[group] = phys_to_work_map->work_ids + _layout.phys_index.get(group); 156 } 157 } 158 159 ASMJIT_INLINE void reset_maps() noexcept { 160 _phys_to_work_map = nullptr; 161 _work_to_phys_map = nullptr; 162 _phys_to_work_ids.fill(nullptr); 163 } 164 165 //! \} 166 167 //! \name Accessors 168 //! \{ 169 170 [[nodiscard]] 171 ASMJIT_INLINE_NODEBUG PhysToWorkMap* phys_to_work_map() const noexcept { return _phys_to_work_map; } 172 173 [[nodiscard]] 174 ASMJIT_INLINE_NODEBUG WorkToPhysMap* work_to_phys_map() const noexcept { return _work_to_phys_map; } 175 176 [[nodiscard]] 177 ASMJIT_INLINE_NODEBUG RARegMask& assigned() noexcept { return _phys_to_work_map->assigned; } 178 179 [[nodiscard]] 180 ASMJIT_INLINE_NODEBUG const RARegMask& assigned() const noexcept { return _phys_to_work_map->assigned; } 181 182 [[nodiscard]] 183 ASMJIT_INLINE_NODEBUG uint32_t assigned(RegGroup group) const noexcept { return _phys_to_work_map->assigned[group]; } 184 185 [[nodiscard]] 186 ASMJIT_INLINE_NODEBUG RARegMask& dirty() noexcept { return _phys_to_work_map->dirty; } 187 188 [[nodiscard]] 189 ASMJIT_INLINE_NODEBUG const RARegMask& dirty() const noexcept { return _phys_to_work_map->dirty; } 190 191 [[nodiscard]] 192 ASMJIT_INLINE_NODEBUG RegMask dirty(RegGroup group) const noexcept { return _phys_to_work_map->dirty[group]; } 193 194 [[nodiscard]] 195 inline uint32_t work_to_phys_id(RegGroup group, RAWorkId work_id) const noexcept { 196 Support::maybe_unused(group); 197 ASMJIT_ASSERT(work_id != kBadWorkId); 198 ASMJIT_ASSERT(uint32_t(work_id) < _layout.work_count); 199 return _work_to_phys_map->phys_ids[uint32_t(work_id)]; 200 } 201 202 [[nodiscard]] 203 inline RAWorkId phys_to_work_id(RegGroup group, uint32_t phys_id) const noexcept { 204 ASMJIT_ASSERT(phys_id < Globals::kMaxPhysRegs); 205 return _phys_to_work_ids[group][phys_id]; 206 } 207 208 [[nodiscard]] 209 inline bool is_phys_assigned(RegGroup group, uint32_t phys_id) const noexcept { 210 ASMJIT_ASSERT(phys_id < Globals::kMaxPhysRegs); 211 return Support::bit_test(_phys_to_work_map->assigned[group], phys_id); 212 } 213 214 [[nodiscard]] 215 inline bool is_phys_dirty(RegGroup group, uint32_t phys_id) const noexcept { 216 ASMJIT_ASSERT(phys_id < Globals::kMaxPhysRegs); 217 return Support::bit_test(_phys_to_work_map->dirty[group], phys_id); 218 } 219 220 //! \} 221 222 //! \name Assignment 223 //! 224 //! These are low-level allocation helpers that are used to update the current mappings between physical and 225 //! virt/work registers and also to update masks that represent allocated and dirty registers. These functions 226 //! don't emit any code; they are only used to update and keep all mappings in sync. 227 //! 228 //! \{ 229 230 //! Assign [VirtReg/WorkReg] to a physical register. 231 inline void assign(RegGroup group, RAWorkId work_id, uint32_t phys_id, bool dirty) noexcept { 232 ASMJIT_ASSERT(work_to_phys_id(group, work_id) == kPhysNone); 233 ASMJIT_ASSERT(phys_to_work_id(group, phys_id) == kBadWorkId); 234 ASMJIT_ASSERT(!is_phys_assigned(group, phys_id)); 235 ASMJIT_ASSERT(!is_phys_dirty(group, phys_id)); 236 237 _work_to_phys_map->phys_ids[uint32_t(work_id)] = uint8_t(phys_id); 238 _phys_to_work_ids[group][phys_id] = work_id; 239 240 RegMask reg_mask = Support::bit_mask<RegMask>(phys_id); 241 _phys_to_work_map->assigned[group] |= reg_mask; 242 _phys_to_work_map->dirty[group] |= reg_mask & Support::bool_as_mask<RegMask>(dirty); 243 244 verify(); 245 } 246 247 //! Reassign [VirtReg/WorkReg] to `dst_phys_id` from `src_phys_id`. 248 inline void reassign(RegGroup group, RAWorkId work_id, uint32_t dst_phys_id, uint32_t src_phys_id) noexcept { 249 ASMJIT_ASSERT(dst_phys_id != src_phys_id); 250 ASMJIT_ASSERT(work_to_phys_id(group, work_id) == src_phys_id); 251 ASMJIT_ASSERT(phys_to_work_id(group, src_phys_id) == work_id); 252 ASMJIT_ASSERT(is_phys_assigned(group, src_phys_id) == true); 253 ASMJIT_ASSERT(is_phys_assigned(group, dst_phys_id) == false); 254 255 _work_to_phys_map->phys_ids[uint32_t(work_id)] = uint8_t(dst_phys_id); 256 _phys_to_work_ids[group][src_phys_id] = kBadWorkId; 257 _phys_to_work_ids[group][dst_phys_id] = work_id; 258 259 RegMask src_mask = Support::bit_mask<RegMask>(src_phys_id); 260 RegMask dst_mask = Support::bit_mask<RegMask>(dst_phys_id); 261 262 bool dirty = (_phys_to_work_map->dirty[group] & src_mask) != 0; 263 RegMask reg_mask = dst_mask | src_mask; 264 265 _phys_to_work_map->assigned[group] ^= reg_mask; 266 _phys_to_work_map->dirty[group] ^= reg_mask & Support::bool_as_mask<RegMask>(dirty); 267 268 verify(); 269 } 270 271 inline void swap(RegGroup group, RAWorkId a_work_id, uint32_t a_phys_id, RAWorkId b_work_id, uint32_t b_phys_id) noexcept { 272 ASMJIT_ASSERT(a_phys_id != b_phys_id); 273 274 ASMJIT_ASSERT(work_to_phys_id(group, a_work_id) == a_phys_id); 275 ASMJIT_ASSERT(work_to_phys_id(group, b_work_id) == b_phys_id); 276 ASMJIT_ASSERT(phys_to_work_id(group, a_phys_id) == a_work_id); 277 ASMJIT_ASSERT(phys_to_work_id(group, b_phys_id) == b_work_id); 278 279 ASMJIT_ASSERT(is_phys_assigned(group, a_phys_id)); 280 ASMJIT_ASSERT(is_phys_assigned(group, b_phys_id)); 281 282 _work_to_phys_map->phys_ids[uint32_t(a_work_id)] = uint8_t(b_phys_id); 283 _work_to_phys_map->phys_ids[uint32_t(b_work_id)] = uint8_t(a_phys_id); 284 _phys_to_work_ids[group][a_phys_id] = b_work_id; 285 _phys_to_work_ids[group][b_phys_id] = a_work_id; 286 287 RegMask a_mask = Support::bit_mask<RegMask>(a_phys_id); 288 RegMask b_mask = Support::bit_mask<RegMask>(b_phys_id); 289 RegMask flip_mask = Support::bool_as_mask<RegMask>(((_phys_to_work_map->dirty[group] & a_mask) != 0) ^ ((_phys_to_work_map->dirty[group] & b_mask) != 0)); 290 RegMask reg_mask = a_mask | b_mask; 291 _phys_to_work_map->dirty[group] ^= reg_mask & flip_mask; 292 293 verify(); 294 } 295 296 //! Unassign [VirtReg/WorkReg] from a physical register. 297 inline void unassign(RegGroup group, RAWorkId work_id, uint32_t phys_id) noexcept { 298 ASMJIT_ASSERT(phys_id < Globals::kMaxPhysRegs); 299 ASMJIT_ASSERT(work_to_phys_id(group, work_id) == phys_id); 300 ASMJIT_ASSERT(phys_to_work_id(group, phys_id) == work_id); 301 ASMJIT_ASSERT(is_phys_assigned(group, phys_id)); 302 303 _work_to_phys_map->phys_ids[uint32_t(work_id)] = kPhysNone; 304 _phys_to_work_ids[group][phys_id] = kBadWorkId; 305 306 RegMask reg_mask = Support::bit_mask<RegMask>(phys_id); 307 _phys_to_work_map->assigned[group] &= ~reg_mask; 308 _phys_to_work_map->dirty[group] &= ~reg_mask; 309 310 verify(); 311 } 312 313 inline void make_clean(RegGroup group, RAWorkId work_id, uint32_t phys_id) noexcept { 314 Support::maybe_unused(work_id); 315 RegMask reg_mask = Support::bit_mask<RegMask>(phys_id); 316 _phys_to_work_map->dirty[group] &= ~reg_mask; 317 } 318 319 inline void make_dirty(RegGroup group, RAWorkId work_id, uint32_t phys_id) noexcept { 320 Support::maybe_unused(work_id); 321 RegMask reg_mask = Support::bit_mask<RegMask>(phys_id); 322 _phys_to_work_map->dirty[group] |= reg_mask; 323 } 324 325 //! \} 326 327 //! \name Utilities 328 //! \{ 329 330 ASMJIT_INLINE void swap(RAAssignment& other) noexcept { 331 std::swap(_work_to_phys_map, other._work_to_phys_map); 332 std::swap(_phys_to_work_map, other._phys_to_work_map); 333 _phys_to_work_ids.swap(other._phys_to_work_ids); 334 } 335 336 inline void assign_work_ids_from_phys_ids() noexcept { 337 memset(_work_to_phys_map, uint8_t(Reg::kIdBad), WorkToPhysMap::size_of(_layout.work_count)); 338 339 for (RegGroup group : Support::enumerate(RegGroup::kMaxVirt)) { 340 uint32_t phys_base_index = _layout.phys_index[group]; 341 Support::BitWordIterator<RegMask> it(_phys_to_work_map->assigned[group]); 342 343 while (it.has_next()) { 344 uint32_t phys_id = it.next(); 345 RAWorkId work_id = _phys_to_work_map->work_ids[phys_base_index + phys_id]; 346 347 ASMJIT_ASSERT(work_id != kBadWorkId); 348 _work_to_phys_map->phys_ids[uint32_t(work_id)] = uint8_t(phys_id); 349 } 350 } 351 } 352 353 inline void copy_from(const PhysToWorkMap* phys_to_work_map) noexcept { 354 memcpy(_phys_to_work_map, phys_to_work_map, PhysToWorkMap::size_of(_layout.phys_total)); 355 assign_work_ids_from_phys_ids(); 356 } 357 358 inline void copy_from(const PhysToWorkMap* phys_to_work_map, const WorkToPhysMap* work_to_phys_map) noexcept { 359 memcpy(_phys_to_work_map, phys_to_work_map, PhysToWorkMap::size_of(_layout.phys_total)); 360 memcpy(_work_to_phys_map, work_to_phys_map, WorkToPhysMap::size_of(_layout.work_count)); 361 } 362 363 inline void copy_from(const RAAssignment& other) noexcept { 364 copy_from(other.phys_to_work_map(), other.work_to_phys_map()); 365 } 366 367 // Not really useful outside of debugging. 368 [[nodiscard]] 369 bool equals(const RAAssignment& other) const noexcept { 370 // Layout should always match. 371 if (_layout.phys_index != other._layout.phys_index || 372 _layout.phys_count != other._layout.phys_count || 373 _layout.phys_total != other._layout.phys_total || 374 _layout.work_count != other._layout.work_count || 375 _layout.work_regs != other._layout.work_regs) { 376 return false; 377 } 378 379 uint32_t phys_total = _layout.phys_total; 380 uint32_t work_count = _layout.work_count; 381 382 for (uint32_t phys_id = 0; phys_id < phys_total; phys_id++) { 383 RAWorkId this_work_id = _phys_to_work_map->work_ids[phys_id]; 384 RAWorkId other_work_id = other._phys_to_work_map->work_ids[phys_id]; 385 if (this_work_id != other_work_id) { 386 return false; 387 } 388 } 389 390 for (uint32_t work_id = 0; work_id < work_count; work_id++) { 391 uint32_t this_phys_id = _work_to_phys_map->phys_ids[work_id]; 392 uint32_t other_phys_id = other._work_to_phys_map->phys_ids[work_id]; 393 394 if (this_phys_id != other_phys_id) { 395 return false; 396 } 397 } 398 399 if (_phys_to_work_map->assigned != other._phys_to_work_map->assigned || 400 _phys_to_work_map->dirty != other._phys_to_work_map->dirty ) { 401 return false; 402 } 403 404 return true; 405 } 406 407 #if defined(ASMJIT_BUILD_DEBUG) 408 ASMJIT_NOINLINE void verify() noexcept { 409 // Verify WorkToPhysMap. 410 { 411 for (uint32_t work_id = 0; work_id < _layout.work_count; work_id++) { 412 uint32_t phys_id = _work_to_phys_map->phys_ids[work_id]; 413 if (phys_id != kPhysNone) { 414 const RAWorkReg* work_reg = _layout.work_regs->at(work_id); 415 RegGroup group = work_reg->group(); 416 ASMJIT_ASSERT(_phys_to_work_ids[group][phys_id] == RAWorkId(work_id)); 417 } 418 } 419 } 420 421 // Verify PhysToWorkMap. 422 { 423 for (RegGroup group : Support::enumerate(RegGroup::kMaxVirt)) { 424 uint32_t phys_count = _layout.phys_count[group]; 425 for (uint32_t phys_id = 0; phys_id < phys_count; phys_id++) { 426 RAWorkId work_id = _phys_to_work_ids[group][phys_id]; 427 if (work_id != kBadWorkId) { 428 ASMJIT_ASSERT(_work_to_phys_map->phys_ids[uint32_t(work_id)] == phys_id); 429 } 430 } 431 } 432 } 433 } 434 #else 435 inline void verify() noexcept {} 436 #endif 437 438 //! \} 439 }; 440 441 //! Intersection of multiple register assignments. 442 //! 443 //! See \ref RAAssignment for more information about register assignments. 444 class RASharedAssignment { 445 public: 446 //! \name Types 447 //! \{ 448 449 using PhysToWorkMap = RAAssignment::PhysToWorkMap; 450 using WorkToPhysMap = RAAssignment::WorkToPhysMap; 451 452 //! \} 453 454 //! \name Members 455 //! \{ 456 457 //! Bit-mask of registers that cannot be used upon a block entry, for each block that has this shared assignment. 458 //! Scratch registers can come from ISA limits (like jecx/loop instructions on x86) or because the registers are 459 //! used by jump/branch instruction that uses registers to perform an indirect jump. 460 RegMask _entry_scratch_gp_regs = 0; 461 //! Union of all live-in registers. 462 ArenaBitSet _live_in {}; 463 //! Register assignment (PhysToWork). 464 PhysToWorkMap* _phys_to_work_map = nullptr; 465 466 //! \} 467 468 //! \name Accessors 469 //! \{ 470 471 [[nodiscard]] 472 ASMJIT_INLINE_NODEBUG bool is_empty() const noexcept { return _phys_to_work_map == nullptr; } 473 474 [[nodiscard]] 475 ASMJIT_INLINE_NODEBUG RegMask entry_scratch_gp_regs() const noexcept { return _entry_scratch_gp_regs; } 476 477 ASMJIT_INLINE_NODEBUG void add_entry_scratch_gp_regs(RegMask mask) noexcept { _entry_scratch_gp_regs |= mask; } 478 479 [[nodiscard]] 480 ASMJIT_INLINE_NODEBUG Span<const BitWord> live_in() const noexcept { return _live_in.as_span(); } 481 482 [[nodiscard]] 483 ASMJIT_INLINE_NODEBUG PhysToWorkMap* phys_to_work_map() const noexcept { return _phys_to_work_map; } 484 485 ASMJIT_INLINE_NODEBUG void assign_phys_to_work_map(PhysToWorkMap* phys_to_work_map) noexcept { _phys_to_work_map = phys_to_work_map; } 486 487 //! \} 488 }; 489 490 //! \} 491 //! \endcond 492 493 ASMJIT_END_NAMESPACE 494 495 #endif // !ASMJIT_NO_COMPILER 496 #endif // ASMJIT_CORE_RAASSIGNMENT_P_H_INCLUDED