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