1// Copyright 2014 the V8 project authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#ifndef V8_REGISTER_ALLOCATOR_H_ 6#define V8_REGISTER_ALLOCATOR_H_ 7 8#include "src/allocation.h" 9#include "src/compiler/instruction.h" 10#include "src/compiler/node.h" 11#include "src/compiler/schedule.h" 12#include "src/macro-assembler.h" 13#include "src/zone.h" 14 15namespace v8 { 16namespace internal { 17 18// Forward declarations. 19class BitVector; 20class InstructionOperand; 21class UnallocatedOperand; 22class ParallelMove; 23class PointerMap; 24 25namespace compiler { 26 27enum RegisterKind { 28 UNALLOCATED_REGISTERS, 29 GENERAL_REGISTERS, 30 DOUBLE_REGISTERS 31}; 32 33 34// This class represents a single point of a InstructionOperand's lifetime. For 35// each instruction there are exactly two lifetime positions: the beginning and 36// the end of the instruction. Lifetime positions for different instructions are 37// disjoint. 38class LifetimePosition { 39 public: 40 // Return the lifetime position that corresponds to the beginning of 41 // the instruction with the given index. 42 static LifetimePosition FromInstructionIndex(int index) { 43 return LifetimePosition(index * kStep); 44 } 45 46 // Returns a numeric representation of this lifetime position. 47 int Value() const { return value_; } 48 49 // Returns the index of the instruction to which this lifetime position 50 // corresponds. 51 int InstructionIndex() const { 52 DCHECK(IsValid()); 53 return value_ / kStep; 54 } 55 56 // Returns true if this lifetime position corresponds to the instruction 57 // start. 58 bool IsInstructionStart() const { return (value_ & (kStep - 1)) == 0; } 59 60 // Returns the lifetime position for the start of the instruction which 61 // corresponds to this lifetime position. 62 LifetimePosition InstructionStart() const { 63 DCHECK(IsValid()); 64 return LifetimePosition(value_ & ~(kStep - 1)); 65 } 66 67 // Returns the lifetime position for the end of the instruction which 68 // corresponds to this lifetime position. 69 LifetimePosition InstructionEnd() const { 70 DCHECK(IsValid()); 71 return LifetimePosition(InstructionStart().Value() + kStep / 2); 72 } 73 74 // Returns the lifetime position for the beginning of the next instruction. 75 LifetimePosition NextInstruction() const { 76 DCHECK(IsValid()); 77 return LifetimePosition(InstructionStart().Value() + kStep); 78 } 79 80 // Returns the lifetime position for the beginning of the previous 81 // instruction. 82 LifetimePosition PrevInstruction() const { 83 DCHECK(IsValid()); 84 DCHECK(value_ > 1); 85 return LifetimePosition(InstructionStart().Value() - kStep); 86 } 87 88 // Constructs the lifetime position which does not correspond to any 89 // instruction. 90 LifetimePosition() : value_(-1) {} 91 92 // Returns true if this lifetime positions corrensponds to some 93 // instruction. 94 bool IsValid() const { return value_ != -1; } 95 96 static inline LifetimePosition Invalid() { return LifetimePosition(); } 97 98 static inline LifetimePosition MaxPosition() { 99 // We have to use this kind of getter instead of static member due to 100 // crash bug in GDB. 101 return LifetimePosition(kMaxInt); 102 } 103 104 private: 105 static const int kStep = 2; 106 107 // Code relies on kStep being a power of two. 108 STATIC_ASSERT(IS_POWER_OF_TWO(kStep)); 109 110 explicit LifetimePosition(int value) : value_(value) {} 111 112 int value_; 113}; 114 115 116// Representation of the non-empty interval [start,end[. 117class UseInterval : public ZoneObject { 118 public: 119 UseInterval(LifetimePosition start, LifetimePosition end) 120 : start_(start), end_(end), next_(NULL) { 121 DCHECK(start.Value() < end.Value()); 122 } 123 124 LifetimePosition start() const { return start_; } 125 LifetimePosition end() const { return end_; } 126 UseInterval* next() const { return next_; } 127 128 // Split this interval at the given position without effecting the 129 // live range that owns it. The interval must contain the position. 130 void SplitAt(LifetimePosition pos, Zone* zone); 131 132 // If this interval intersects with other return smallest position 133 // that belongs to both of them. 134 LifetimePosition Intersect(const UseInterval* other) const { 135 if (other->start().Value() < start_.Value()) return other->Intersect(this); 136 if (other->start().Value() < end_.Value()) return other->start(); 137 return LifetimePosition::Invalid(); 138 } 139 140 bool Contains(LifetimePosition point) const { 141 return start_.Value() <= point.Value() && point.Value() < end_.Value(); 142 } 143 144 void set_start(LifetimePosition start) { start_ = start; } 145 void set_next(UseInterval* next) { next_ = next; } 146 147 LifetimePosition start_; 148 LifetimePosition end_; 149 UseInterval* next_; 150}; 151 152// Representation of a use position. 153class UsePosition : public ZoneObject { 154 public: 155 UsePosition(LifetimePosition pos, InstructionOperand* operand, 156 InstructionOperand* hint); 157 158 InstructionOperand* operand() const { return operand_; } 159 bool HasOperand() const { return operand_ != NULL; } 160 161 InstructionOperand* hint() const { return hint_; } 162 bool HasHint() const; 163 bool RequiresRegister() const; 164 bool RegisterIsBeneficial() const; 165 166 LifetimePosition pos() const { return pos_; } 167 UsePosition* next() const { return next_; } 168 169 void set_next(UsePosition* next) { next_ = next; } 170 171 InstructionOperand* const operand_; 172 InstructionOperand* const hint_; 173 LifetimePosition const pos_; 174 UsePosition* next_; 175 bool requires_reg_; 176 bool register_beneficial_; 177}; 178 179// Representation of SSA values' live ranges as a collection of (continuous) 180// intervals over the instruction ordering. 181class LiveRange : public ZoneObject { 182 public: 183 static const int kInvalidAssignment = 0x7fffffff; 184 185 LiveRange(int id, Zone* zone); 186 187 UseInterval* first_interval() const { return first_interval_; } 188 UsePosition* first_pos() const { return first_pos_; } 189 LiveRange* parent() const { return parent_; } 190 LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } 191 LiveRange* next() const { return next_; } 192 bool IsChild() const { return parent() != NULL; } 193 int id() const { return id_; } 194 bool IsFixed() const { return id_ < 0; } 195 bool IsEmpty() const { return first_interval() == NULL; } 196 InstructionOperand* CreateAssignedOperand(Zone* zone); 197 int assigned_register() const { return assigned_register_; } 198 int spill_start_index() const { return spill_start_index_; } 199 void set_assigned_register(int reg, Zone* zone); 200 void MakeSpilled(Zone* zone); 201 bool is_phi() const { return is_phi_; } 202 void set_is_phi(bool is_phi) { is_phi_ = is_phi; } 203 bool is_non_loop_phi() const { return is_non_loop_phi_; } 204 void set_is_non_loop_phi(bool is_non_loop_phi) { 205 is_non_loop_phi_ = is_non_loop_phi; 206 } 207 208 // Returns use position in this live range that follows both start 209 // and last processed use position. 210 // Modifies internal state of live range! 211 UsePosition* NextUsePosition(LifetimePosition start); 212 213 // Returns use position for which register is required in this live 214 // range and which follows both start and last processed use position 215 // Modifies internal state of live range! 216 UsePosition* NextRegisterPosition(LifetimePosition start); 217 218 // Returns use position for which register is beneficial in this live 219 // range and which follows both start and last processed use position 220 // Modifies internal state of live range! 221 UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start); 222 223 // Returns use position for which register is beneficial in this live 224 // range and which precedes start. 225 UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start); 226 227 // Can this live range be spilled at this position. 228 bool CanBeSpilled(LifetimePosition pos); 229 230 // Split this live range at the given position which must follow the start of 231 // the range. 232 // All uses following the given position will be moved from this 233 // live range to the result live range. 234 void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); 235 236 RegisterKind Kind() const { return kind_; } 237 bool HasRegisterAssigned() const { 238 return assigned_register_ != kInvalidAssignment; 239 } 240 bool IsSpilled() const { return spilled_; } 241 242 InstructionOperand* current_hint_operand() const { 243 DCHECK(current_hint_operand_ == FirstHint()); 244 return current_hint_operand_; 245 } 246 InstructionOperand* FirstHint() const { 247 UsePosition* pos = first_pos_; 248 while (pos != NULL && !pos->HasHint()) pos = pos->next(); 249 if (pos != NULL) return pos->hint(); 250 return NULL; 251 } 252 253 LifetimePosition Start() const { 254 DCHECK(!IsEmpty()); 255 return first_interval()->start(); 256 } 257 258 LifetimePosition End() const { 259 DCHECK(!IsEmpty()); 260 return last_interval_->end(); 261 } 262 263 bool HasAllocatedSpillOperand() const; 264 InstructionOperand* GetSpillOperand() const { return spill_operand_; } 265 void SetSpillOperand(InstructionOperand* operand); 266 267 void SetSpillStartIndex(int start) { 268 spill_start_index_ = Min(start, spill_start_index_); 269 } 270 271 bool ShouldBeAllocatedBefore(const LiveRange* other) const; 272 bool CanCover(LifetimePosition position) const; 273 bool Covers(LifetimePosition position); 274 LifetimePosition FirstIntersection(LiveRange* other); 275 276 // Add a new interval or a new use position to this live range. 277 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); 278 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); 279 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, 280 InstructionOperand* hint, Zone* zone); 281 282 // Shorten the most recently added interval by setting a new start. 283 void ShortenTo(LifetimePosition start); 284 285#ifdef DEBUG 286 // True if target overlaps an existing interval. 287 bool HasOverlap(UseInterval* target) const; 288 void Verify() const; 289#endif 290 291 private: 292 void ConvertOperands(Zone* zone); 293 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; 294 void AdvanceLastProcessedMarker(UseInterval* to_start_of, 295 LifetimePosition but_not_past) const; 296 297 int id_; 298 bool spilled_; 299 bool is_phi_; 300 bool is_non_loop_phi_; 301 RegisterKind kind_; 302 int assigned_register_; 303 UseInterval* last_interval_; 304 UseInterval* first_interval_; 305 UsePosition* first_pos_; 306 LiveRange* parent_; 307 LiveRange* next_; 308 // This is used as a cache, it doesn't affect correctness. 309 mutable UseInterval* current_interval_; 310 UsePosition* last_processed_use_; 311 // This is used as a cache, it's invalid outside of BuildLiveRanges. 312 InstructionOperand* current_hint_operand_; 313 InstructionOperand* spill_operand_; 314 int spill_start_index_; 315 316 friend class RegisterAllocator; // Assigns to kind_. 317}; 318 319 320class RegisterAllocator BASE_EMBEDDED { 321 public: 322 explicit RegisterAllocator(InstructionSequence* code); 323 324 static void TraceAlloc(const char* msg, ...); 325 326 // Checks whether the value of a given virtual register is a reference. 327 // TODO(titzer): rename this to IsReference. 328 bool HasTaggedValue(int virtual_register) const; 329 330 // Returns the register kind required by the given virtual register. 331 RegisterKind RequiredRegisterKind(int virtual_register) const; 332 333 bool Allocate(); 334 335 const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } 336 const Vector<LiveRange*>* fixed_live_ranges() const { 337 return &fixed_live_ranges_; 338 } 339 const Vector<LiveRange*>* fixed_double_live_ranges() const { 340 return &fixed_double_live_ranges_; 341 } 342 343 inline InstructionSequence* code() const { return code_; } 344 345 // This zone is for datastructures only needed during register allocation. 346 inline Zone* zone() { return &zone_; } 347 348 // This zone is for InstructionOperands and moves that live beyond register 349 // allocation. 350 inline Zone* code_zone() { return code()->zone(); } 351 352 int GetVirtualRegister() { 353 int vreg = code()->NextVirtualRegister(); 354 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { 355 allocation_ok_ = false; 356 // Maintain the invariant that we return something below the maximum. 357 return 0; 358 } 359 return vreg; 360 } 361 362 bool AllocationOk() { return allocation_ok_; } 363 364#ifdef DEBUG 365 void Verify() const; 366#endif 367 368 BitVector* assigned_registers() { return assigned_registers_; } 369 BitVector* assigned_double_registers() { return assigned_double_registers_; } 370 371 private: 372 void MeetRegisterConstraints(); 373 void ResolvePhis(); 374 void BuildLiveRanges(); 375 void AllocateGeneralRegisters(); 376 void AllocateDoubleRegisters(); 377 void ConnectRanges(); 378 void ResolveControlFlow(); 379 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. 380 void AllocateRegisters(); 381 bool CanEagerlyResolveControlFlow(BasicBlock* block) const; 382 inline bool SafePointsAreInOrder() const; 383 384 // Liveness analysis support. 385 void InitializeLivenessAnalysis(); 386 BitVector* ComputeLiveOut(BasicBlock* block); 387 void AddInitialIntervals(BasicBlock* block, BitVector* live_out); 388 bool IsOutputRegisterOf(Instruction* instr, int index); 389 bool IsOutputDoubleRegisterOf(Instruction* instr, int index); 390 void ProcessInstructions(BasicBlock* block, BitVector* live); 391 void MeetRegisterConstraints(BasicBlock* block); 392 void MeetConstraintsBetween(Instruction* first, Instruction* second, 393 int gap_index); 394 void MeetRegisterConstraintsForLastInstructionInBlock(BasicBlock* block); 395 void ResolvePhis(BasicBlock* block); 396 397 // Helper methods for building intervals. 398 InstructionOperand* AllocateFixed(UnallocatedOperand* operand, int pos, 399 bool is_tagged); 400 LiveRange* LiveRangeFor(InstructionOperand* operand); 401 void Define(LifetimePosition position, InstructionOperand* operand, 402 InstructionOperand* hint); 403 void Use(LifetimePosition block_start, LifetimePosition position, 404 InstructionOperand* operand, InstructionOperand* hint); 405 void AddConstraintsGapMove(int index, InstructionOperand* from, 406 InstructionOperand* to); 407 408 // Helper methods for updating the life range lists. 409 void AddToActive(LiveRange* range); 410 void AddToInactive(LiveRange* range); 411 void AddToUnhandledSorted(LiveRange* range); 412 void AddToUnhandledUnsorted(LiveRange* range); 413 void SortUnhandled(); 414 bool UnhandledIsSorted(); 415 void ActiveToHandled(LiveRange* range); 416 void ActiveToInactive(LiveRange* range); 417 void InactiveToHandled(LiveRange* range); 418 void InactiveToActive(LiveRange* range); 419 void FreeSpillSlot(LiveRange* range); 420 InstructionOperand* TryReuseSpillSlot(LiveRange* range); 421 422 // Helper methods for allocating registers. 423 bool TryAllocateFreeReg(LiveRange* range); 424 void AllocateBlockedReg(LiveRange* range); 425 426 // Live range splitting helpers. 427 428 // Split the given range at the given position. 429 // If range starts at or after the given position then the 430 // original range is returned. 431 // Otherwise returns the live range that starts at pos and contains 432 // all uses from the original range that follow pos. Uses at pos will 433 // still be owned by the original range after splitting. 434 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); 435 436 // Split the given range in a position from the interval [start, end]. 437 LiveRange* SplitBetween(LiveRange* range, LifetimePosition start, 438 LifetimePosition end); 439 440 // Find a lifetime position in the interval [start, end] which 441 // is optimal for splitting: it is either header of the outermost 442 // loop covered by this interval or the latest possible position. 443 LifetimePosition FindOptimalSplitPos(LifetimePosition start, 444 LifetimePosition end); 445 446 // Spill the given life range after position pos. 447 void SpillAfter(LiveRange* range, LifetimePosition pos); 448 449 // Spill the given life range after position [start] and up to position [end]. 450 void SpillBetween(LiveRange* range, LifetimePosition start, 451 LifetimePosition end); 452 453 // Spill the given life range after position [start] and up to position [end]. 454 // Range is guaranteed to be spilled at least until position [until]. 455 void SpillBetweenUntil(LiveRange* range, LifetimePosition start, 456 LifetimePosition until, LifetimePosition end); 457 458 void SplitAndSpillIntersecting(LiveRange* range); 459 460 // If we are trying to spill a range inside the loop try to 461 // hoist spill position out to the point just before the loop. 462 LifetimePosition FindOptimalSpillingPos(LiveRange* range, 463 LifetimePosition pos); 464 465 void Spill(LiveRange* range); 466 bool IsBlockBoundary(LifetimePosition pos); 467 468 // Helper methods for resolving control flow. 469 void ResolveControlFlow(LiveRange* range, BasicBlock* block, 470 BasicBlock* pred); 471 472 inline void SetLiveRangeAssignedRegister(LiveRange* range, int reg); 473 474 // Return parallel move that should be used to connect ranges split at the 475 // given position. 476 ParallelMove* GetConnectingParallelMove(LifetimePosition pos); 477 478 // Return the block which contains give lifetime position. 479 BasicBlock* GetBlock(LifetimePosition pos); 480 481 // Helper methods for the fixed registers. 482 int RegisterCount() const; 483 static int FixedLiveRangeID(int index) { return -index - 1; } 484 static int FixedDoubleLiveRangeID(int index); 485 LiveRange* FixedLiveRangeFor(int index); 486 LiveRange* FixedDoubleLiveRangeFor(int index); 487 LiveRange* LiveRangeFor(int index); 488 GapInstruction* GetLastGap(BasicBlock* block); 489 490 const char* RegisterName(int allocation_index); 491 492 inline Instruction* InstructionAt(int index) { 493 return code()->InstructionAt(index); 494 } 495 496 Zone zone_; 497 InstructionSequence* code_; 498 499 // During liveness analysis keep a mapping from block id to live_in sets 500 // for blocks already analyzed. 501 ZoneList<BitVector*> live_in_sets_; 502 503 // Liveness analysis results. 504 ZoneList<LiveRange*> live_ranges_; 505 506 // Lists of live ranges 507 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> 508 fixed_live_ranges_; 509 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> 510 fixed_double_live_ranges_; 511 ZoneList<LiveRange*> unhandled_live_ranges_; 512 ZoneList<LiveRange*> active_live_ranges_; 513 ZoneList<LiveRange*> inactive_live_ranges_; 514 ZoneList<LiveRange*> reusable_slots_; 515 516 RegisterKind mode_; 517 int num_registers_; 518 519 BitVector* assigned_registers_; 520 BitVector* assigned_double_registers_; 521 522 // Indicates success or failure during register allocation. 523 bool allocation_ok_; 524 525#ifdef DEBUG 526 LifetimePosition allocation_finger_; 527#endif 528 529 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); 530}; 531 532 533class RegisterAllocatorPhase : public CompilationPhase { 534 public: 535 RegisterAllocatorPhase(const char* name, RegisterAllocator* allocator); 536 ~RegisterAllocatorPhase(); 537 538 private: 539 RegisterAllocator* allocator_; 540 unsigned allocator_zone_start_allocation_size_; 541 542 DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorPhase); 543}; 544} 545} 546} // namespace v8::internal::compiler 547 548#endif // V8_REGISTER_ALLOCATOR_H_ 549