1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #ifndef V8_LITHIUM_ALLOCATOR_H_ 29 #define V8_LITHIUM_ALLOCATOR_H_ 30 31 #include "v8.h" 32 33 #include "allocation.h" 34 #include "lithium.h" 35 #include "zone.h" 36 37 namespace v8 { 38 namespace internal { 39 40 // Forward declarations. 41 class HBasicBlock; 42 class HGraph; 43 class HInstruction; 44 class HPhi; 45 class HTracer; 46 class HValue; 47 class BitVector; 48 class StringStream; 49 50 class LArgument; 51 class LPlatformChunk; 52 class LOperand; 53 class LUnallocated; 54 class LConstantOperand; 55 class LGap; 56 class LParallelMove; 57 class LPointerMap; 58 class LStackSlot; 59 class LRegister; 60 61 62 // This class represents a single point of a LOperand's lifetime. 63 // For each lithium instruction there are exactly two lifetime positions: 64 // the beginning and the end of the instruction. Lifetime positions for 65 // different lithium instructions are disjoint. 66 class LifetimePosition { 67 public: 68 // Return the lifetime position that corresponds to the beginning of 69 // the instruction with the given index. 70 static LifetimePosition FromInstructionIndex(int index) { 71 return LifetimePosition(index * kStep); 72 } 73 74 // Returns a numeric representation of this lifetime position. 75 int Value() const { 76 return value_; 77 } 78 79 // Returns the index of the instruction to which this lifetime position 80 // corresponds. 81 int InstructionIndex() const { 82 ASSERT(IsValid()); 83 return value_ / kStep; 84 } 85 86 // Returns true if this lifetime position corresponds to the instruction 87 // start. 88 bool IsInstructionStart() const { 89 return (value_ & (kStep - 1)) == 0; 90 } 91 92 // Returns the lifetime position for the start of the instruction which 93 // corresponds to this lifetime position. 94 LifetimePosition InstructionStart() const { 95 ASSERT(IsValid()); 96 return LifetimePosition(value_ & ~(kStep - 1)); 97 } 98 99 // Returns the lifetime position for the end of the instruction which 100 // corresponds to this lifetime position. 101 LifetimePosition InstructionEnd() const { 102 ASSERT(IsValid()); 103 return LifetimePosition(InstructionStart().Value() + kStep/2); 104 } 105 106 // Returns the lifetime position for the beginning of the next instruction. 107 LifetimePosition NextInstruction() const { 108 ASSERT(IsValid()); 109 return LifetimePosition(InstructionStart().Value() + kStep); 110 } 111 112 // Returns the lifetime position for the beginning of the previous 113 // instruction. 114 LifetimePosition PrevInstruction() const { 115 ASSERT(IsValid()); 116 ASSERT(value_ > 1); 117 return LifetimePosition(InstructionStart().Value() - kStep); 118 } 119 120 // Constructs the lifetime position which does not correspond to any 121 // instruction. 122 LifetimePosition() : value_(-1) {} 123 124 // Returns true if this lifetime positions corrensponds to some 125 // instruction. 126 bool IsValid() const { return value_ != -1; } 127 128 static inline LifetimePosition Invalid() { return LifetimePosition(); } 129 130 static inline LifetimePosition MaxPosition() { 131 // We have to use this kind of getter instead of static member due to 132 // crash bug in GDB. 133 return LifetimePosition(kMaxInt); 134 } 135 136 private: 137 static const int kStep = 2; 138 139 // Code relies on kStep being a power of two. 140 STATIC_ASSERT(IS_POWER_OF_TWO(kStep)); 141 142 explicit LifetimePosition(int value) : value_(value) { } 143 144 int value_; 145 }; 146 147 148 enum RegisterKind { 149 GENERAL_REGISTERS, 150 DOUBLE_REGISTERS 151 }; 152 153 154 // A register-allocator view of a Lithium instruction. It contains the id of 155 // the output operand and a list of input operand uses. 156 157 class LInstruction; 158 class LEnvironment; 159 160 // Iterator for non-null temp operands. 161 class TempIterator BASE_EMBEDDED { 162 public: 163 inline explicit TempIterator(LInstruction* instr); 164 inline bool Done(); 165 inline LOperand* Current(); 166 inline void Advance(); 167 168 private: 169 inline void SkipUninteresting(); 170 LInstruction* instr_; 171 int limit_; 172 int current_; 173 }; 174 175 176 // Iterator for non-constant input operands. 177 class InputIterator BASE_EMBEDDED { 178 public: 179 inline explicit InputIterator(LInstruction* instr); 180 inline bool Done(); 181 inline LOperand* Current(); 182 inline void Advance(); 183 184 private: 185 inline void SkipUninteresting(); 186 LInstruction* instr_; 187 int limit_; 188 int current_; 189 }; 190 191 192 class UseIterator BASE_EMBEDDED { 193 public: 194 inline explicit UseIterator(LInstruction* instr); 195 inline bool Done(); 196 inline LOperand* Current(); 197 inline void Advance(); 198 199 private: 200 InputIterator input_iterator_; 201 DeepIterator env_iterator_; 202 }; 203 204 205 // Representation of the non-empty interval [start,end[. 206 class UseInterval: public ZoneObject { 207 public: 208 UseInterval(LifetimePosition start, LifetimePosition end) 209 : start_(start), end_(end), next_(NULL) { 210 ASSERT(start.Value() < end.Value()); 211 } 212 213 LifetimePosition start() const { return start_; } 214 LifetimePosition end() const { return end_; } 215 UseInterval* next() const { return next_; } 216 217 // Split this interval at the given position without effecting the 218 // live range that owns it. The interval must contain the position. 219 void SplitAt(LifetimePosition pos, Zone* zone); 220 221 // If this interval intersects with other return smallest position 222 // that belongs to both of them. 223 LifetimePosition Intersect(const UseInterval* other) const { 224 if (other->start().Value() < start_.Value()) return other->Intersect(this); 225 if (other->start().Value() < end_.Value()) return other->start(); 226 return LifetimePosition::Invalid(); 227 } 228 229 bool Contains(LifetimePosition point) const { 230 return start_.Value() <= point.Value() && point.Value() < end_.Value(); 231 } 232 233 private: 234 void set_start(LifetimePosition start) { start_ = start; } 235 void set_next(UseInterval* next) { next_ = next; } 236 237 LifetimePosition start_; 238 LifetimePosition end_; 239 UseInterval* next_; 240 241 friend class LiveRange; // Assigns to start_. 242 }; 243 244 // Representation of a use position. 245 class UsePosition: public ZoneObject { 246 public: 247 UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint); 248 249 LOperand* operand() const { return operand_; } 250 bool HasOperand() const { return operand_ != NULL; } 251 252 LOperand* hint() const { return hint_; } 253 bool HasHint() const; 254 bool RequiresRegister() const; 255 bool RegisterIsBeneficial() const; 256 257 LifetimePosition pos() const { return pos_; } 258 UsePosition* next() const { return next_; } 259 260 private: 261 void set_next(UsePosition* next) { next_ = next; } 262 263 LOperand* const operand_; 264 LOperand* const hint_; 265 LifetimePosition const pos_; 266 UsePosition* next_; 267 bool requires_reg_; 268 bool register_beneficial_; 269 270 friend class LiveRange; 271 }; 272 273 // Representation of SSA values' live ranges as a collection of (continuous) 274 // intervals over the instruction ordering. 275 class LiveRange: public ZoneObject { 276 public: 277 static const int kInvalidAssignment = 0x7fffffff; 278 279 LiveRange(int id, Zone* zone); 280 281 UseInterval* first_interval() const { return first_interval_; } 282 UsePosition* first_pos() const { return first_pos_; } 283 LiveRange* parent() const { return parent_; } 284 LiveRange* TopLevel() { return (parent_ == NULL) ? this : parent_; } 285 LiveRange* next() const { return next_; } 286 bool IsChild() const { return parent() != NULL; } 287 int id() const { return id_; } 288 bool IsFixed() const { return id_ < 0; } 289 bool IsEmpty() const { return first_interval() == NULL; } 290 LOperand* CreateAssignedOperand(Zone* zone); 291 int assigned_register() const { return assigned_register_; } 292 int spill_start_index() const { return spill_start_index_; } 293 void set_assigned_register(int reg, 294 RegisterKind register_kind, 295 Zone* zone); 296 void MakeSpilled(Zone* zone); 297 298 // Returns use position in this live range that follows both start 299 // and last processed use position. 300 // Modifies internal state of live range! 301 UsePosition* NextUsePosition(LifetimePosition start); 302 303 // Returns use position for which register is required in this live 304 // range and which follows both start and last processed use position 305 // Modifies internal state of live range! 306 UsePosition* NextRegisterPosition(LifetimePosition start); 307 308 // Returns use position for which register is beneficial in this live 309 // range and which follows both start and last processed use position 310 // Modifies internal state of live range! 311 UsePosition* NextUsePositionRegisterIsBeneficial(LifetimePosition start); 312 313 // Returns use position for which register is beneficial in this live 314 // range and which precedes start. 315 UsePosition* PreviousUsePositionRegisterIsBeneficial(LifetimePosition start); 316 317 // Can this live range be spilled at this position. 318 bool CanBeSpilled(LifetimePosition pos); 319 320 // Split this live range at the given position which must follow the start of 321 // the range. 322 // All uses following the given position will be moved from this 323 // live range to the result live range. 324 void SplitAt(LifetimePosition position, LiveRange* result, Zone* zone); 325 326 bool IsDouble() const { return is_double_; } 327 bool HasRegisterAssigned() const { 328 return assigned_register_ != kInvalidAssignment; 329 } 330 bool IsSpilled() const { return spilled_; } 331 332 LOperand* current_hint_operand() const { 333 ASSERT(current_hint_operand_ == FirstHint()); 334 return current_hint_operand_; 335 } 336 LOperand* FirstHint() const { 337 UsePosition* pos = first_pos_; 338 while (pos != NULL && !pos->HasHint()) pos = pos->next(); 339 if (pos != NULL) return pos->hint(); 340 return NULL; 341 } 342 343 LifetimePosition Start() const { 344 ASSERT(!IsEmpty()); 345 return first_interval()->start(); 346 } 347 348 LifetimePosition End() const { 349 ASSERT(!IsEmpty()); 350 return last_interval_->end(); 351 } 352 353 bool HasAllocatedSpillOperand() const; 354 LOperand* GetSpillOperand() const { return spill_operand_; } 355 void SetSpillOperand(LOperand* operand); 356 357 void SetSpillStartIndex(int start) { 358 spill_start_index_ = Min(start, spill_start_index_); 359 } 360 361 bool ShouldBeAllocatedBefore(const LiveRange* other) const; 362 bool CanCover(LifetimePosition position) const; 363 bool Covers(LifetimePosition position); 364 LifetimePosition FirstIntersection(LiveRange* other); 365 366 // Add a new interval or a new use position to this live range. 367 void EnsureInterval(LifetimePosition start, 368 LifetimePosition end, 369 Zone* zone); 370 void AddUseInterval(LifetimePosition start, 371 LifetimePosition end, 372 Zone* zone); 373 void AddUsePosition(LifetimePosition pos, 374 LOperand* operand, 375 LOperand* hint, 376 Zone* zone); 377 378 // Shorten the most recently added interval by setting a new start. 379 void ShortenTo(LifetimePosition start); 380 381 #ifdef DEBUG 382 // True if target overlaps an existing interval. 383 bool HasOverlap(UseInterval* target) const; 384 void Verify() const; 385 #endif 386 387 private: 388 void ConvertOperands(Zone* zone); 389 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; 390 void AdvanceLastProcessedMarker(UseInterval* to_start_of, 391 LifetimePosition but_not_past) const; 392 393 int id_; 394 bool spilled_; 395 bool is_double_; 396 int assigned_register_; 397 UseInterval* last_interval_; 398 UseInterval* first_interval_; 399 UsePosition* first_pos_; 400 LiveRange* parent_; 401 LiveRange* next_; 402 // This is used as a cache, it doesn't affect correctness. 403 mutable UseInterval* current_interval_; 404 UsePosition* last_processed_use_; 405 // This is used as a cache, it's invalid outside of BuildLiveRanges. 406 LOperand* current_hint_operand_; 407 LOperand* spill_operand_; 408 int spill_start_index_; 409 }; 410 411 412 class LAllocator BASE_EMBEDDED { 413 public: 414 LAllocator(int first_virtual_register, HGraph* graph); 415 416 static void TraceAlloc(const char* msg, ...); 417 418 // Checks whether the value of a given virtual register is tagged. 419 bool HasTaggedValue(int virtual_register) const; 420 421 // Returns the register kind required by the given virtual register. 422 RegisterKind RequiredRegisterKind(int virtual_register) const; 423 424 bool Allocate(LChunk* chunk); 425 426 const ZoneList<LiveRange*>* live_ranges() const { return &live_ranges_; } 427 const Vector<LiveRange*>* fixed_live_ranges() const { 428 return &fixed_live_ranges_; 429 } 430 const Vector<LiveRange*>* fixed_double_live_ranges() const { 431 return &fixed_double_live_ranges_; 432 } 433 434 LPlatformChunk* chunk() const { return chunk_; } 435 HGraph* graph() const { return graph_; } 436 Isolate* isolate() const { return graph_->isolate(); } 437 Zone* zone() { return &zone_; } 438 439 int GetVirtualRegister() { 440 if (next_virtual_register_ >= LUnallocated::kMaxVirtualRegisters) { 441 allocation_ok_ = false; 442 // Maintain the invariant that we return something below the maximum. 443 return 0; 444 } 445 return next_virtual_register_++; 446 } 447 448 bool AllocationOk() { return allocation_ok_; } 449 450 void MarkAsOsrEntry() { 451 // There can be only one. 452 ASSERT(!has_osr_entry_); 453 // Simply set a flag to find and process instruction later. 454 has_osr_entry_ = true; 455 } 456 457 #ifdef DEBUG 458 void Verify() const; 459 #endif 460 461 BitVector* assigned_registers() { 462 return assigned_registers_; 463 } 464 BitVector* assigned_double_registers() { 465 return assigned_double_registers_; 466 } 467 468 private: 469 void MeetRegisterConstraints(); 470 void ResolvePhis(); 471 void BuildLiveRanges(); 472 void AllocateGeneralRegisters(); 473 void AllocateDoubleRegisters(); 474 void ConnectRanges(); 475 void ResolveControlFlow(); 476 void PopulatePointerMaps(); 477 void AllocateRegisters(); 478 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; 479 inline bool SafePointsAreInOrder() const; 480 481 // Liveness analysis support. 482 void InitializeLivenessAnalysis(); 483 BitVector* ComputeLiveOut(HBasicBlock* block); 484 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); 485 void ProcessInstructions(HBasicBlock* block, BitVector* live); 486 void MeetRegisterConstraints(HBasicBlock* block); 487 void MeetConstraintsBetween(LInstruction* first, 488 LInstruction* second, 489 int gap_index); 490 void ResolvePhis(HBasicBlock* block); 491 492 // Helper methods for building intervals. 493 LOperand* AllocateFixed(LUnallocated* operand, int pos, bool is_tagged); 494 LiveRange* LiveRangeFor(LOperand* operand); 495 void Define(LifetimePosition position, LOperand* operand, LOperand* hint); 496 void Use(LifetimePosition block_start, 497 LifetimePosition position, 498 LOperand* operand, 499 LOperand* hint); 500 void AddConstraintsGapMove(int index, LOperand* from, LOperand* to); 501 502 // Helper methods for updating the life range lists. 503 void AddToActive(LiveRange* range); 504 void AddToInactive(LiveRange* range); 505 void AddToUnhandledSorted(LiveRange* range); 506 void AddToUnhandledUnsorted(LiveRange* range); 507 void SortUnhandled(); 508 bool UnhandledIsSorted(); 509 void ActiveToHandled(LiveRange* range); 510 void ActiveToInactive(LiveRange* range); 511 void InactiveToHandled(LiveRange* range); 512 void InactiveToActive(LiveRange* range); 513 void FreeSpillSlot(LiveRange* range); 514 LOperand* TryReuseSpillSlot(LiveRange* range); 515 516 // Helper methods for allocating registers. 517 bool TryAllocateFreeReg(LiveRange* range); 518 void AllocateBlockedReg(LiveRange* range); 519 520 // Live range splitting helpers. 521 522 // Split the given range at the given position. 523 // If range starts at or after the given position then the 524 // original range is returned. 525 // Otherwise returns the live range that starts at pos and contains 526 // all uses from the original range that follow pos. Uses at pos will 527 // still be owned by the original range after splitting. 528 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); 529 530 // Split the given range in a position from the interval [start, end]. 531 LiveRange* SplitBetween(LiveRange* range, 532 LifetimePosition start, 533 LifetimePosition end); 534 535 // Find a lifetime position in the interval [start, end] which 536 // is optimal for splitting: it is either header of the outermost 537 // loop covered by this interval or the latest possible position. 538 LifetimePosition FindOptimalSplitPos(LifetimePosition start, 539 LifetimePosition end); 540 541 // Spill the given life range after position pos. 542 void SpillAfter(LiveRange* range, LifetimePosition pos); 543 544 // Spill the given life range after position [start] and up to position [end]. 545 void SpillBetween(LiveRange* range, 546 LifetimePosition start, 547 LifetimePosition end); 548 549 // Spill the given life range after position [start] and up to position [end]. 550 // Range is guaranteed to be spilled at least until position [until]. 551 void SpillBetweenUntil(LiveRange* range, 552 LifetimePosition start, 553 LifetimePosition until, 554 LifetimePosition end); 555 556 void SplitAndSpillIntersecting(LiveRange* range); 557 558 // If we are trying to spill a range inside the loop try to 559 // hoist spill position out to the point just before the loop. 560 LifetimePosition FindOptimalSpillingPos(LiveRange* range, 561 LifetimePosition pos); 562 563 void Spill(LiveRange* range); 564 bool IsBlockBoundary(LifetimePosition pos); 565 566 // Helper methods for resolving control flow. 567 void ResolveControlFlow(LiveRange* range, 568 HBasicBlock* block, 569 HBasicBlock* pred); 570 571 inline void SetLiveRangeAssignedRegister(LiveRange* range, 572 int reg, 573 RegisterKind register_kind); 574 575 // Return parallel move that should be used to connect ranges split at the 576 // given position. 577 LParallelMove* GetConnectingParallelMove(LifetimePosition pos); 578 579 // Return the block which contains give lifetime position. 580 HBasicBlock* GetBlock(LifetimePosition pos); 581 582 // Helper methods for the fixed registers. 583 int RegisterCount() const; 584 static int FixedLiveRangeID(int index) { return -index - 1; } 585 static int FixedDoubleLiveRangeID(int index); 586 LiveRange* FixedLiveRangeFor(int index); 587 LiveRange* FixedDoubleLiveRangeFor(int index); 588 LiveRange* LiveRangeFor(int index); 589 HPhi* LookupPhi(LOperand* operand) const; 590 LGap* GetLastGap(HBasicBlock* block); 591 592 const char* RegisterName(int allocation_index); 593 594 inline bool IsGapAt(int index); 595 596 inline LInstruction* InstructionAt(int index); 597 598 inline LGap* GapAt(int index); 599 600 Zone zone_; 601 602 LPlatformChunk* chunk_; 603 604 // During liveness analysis keep a mapping from block id to live_in sets 605 // for blocks already analyzed. 606 ZoneList<BitVector*> live_in_sets_; 607 608 // Liveness analysis results. 609 ZoneList<LiveRange*> live_ranges_; 610 611 // Lists of live ranges 612 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> 613 fixed_live_ranges_; 614 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> 615 fixed_double_live_ranges_; 616 ZoneList<LiveRange*> unhandled_live_ranges_; 617 ZoneList<LiveRange*> active_live_ranges_; 618 ZoneList<LiveRange*> inactive_live_ranges_; 619 ZoneList<LiveRange*> reusable_slots_; 620 621 // Next virtual register number to be assigned to temporaries. 622 int next_virtual_register_; 623 int first_artificial_register_; 624 GrowableBitVector double_artificial_registers_; 625 626 RegisterKind mode_; 627 int num_registers_; 628 629 BitVector* assigned_registers_; 630 BitVector* assigned_double_registers_; 631 632 HGraph* graph_; 633 634 bool has_osr_entry_; 635 636 // Indicates success or failure during register allocation. 637 bool allocation_ok_; 638 639 #ifdef DEBUG 640 LifetimePosition allocation_finger_; 641 #endif 642 643 DISALLOW_COPY_AND_ASSIGN(LAllocator); 644 }; 645 646 647 class LAllocatorPhase : public CompilationPhase { 648 public: 649 LAllocatorPhase(const char* name, LAllocator* allocator); 650 ~LAllocatorPhase(); 651 652 private: 653 LAllocator* allocator_; 654 unsigned allocator_zone_start_allocation_size_; 655 656 DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase); 657 }; 658 659 660 } } // namespace v8::internal 661 662 #endif // V8_LITHIUM_ALLOCATOR_H_ 663