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