OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_REGISTER_ALLOCATOR_H_ | 5 #ifndef V8_REGISTER_ALLOCATOR_H_ |
6 #define V8_REGISTER_ALLOCATOR_H_ | 6 #define V8_REGISTER_ALLOCATOR_H_ |
7 | 7 |
8 #include "src/compiler/instruction.h" | 8 #include "src/compiler/instruction.h" |
9 #include "src/zone-containers.h" | 9 #include "src/zone-containers.h" |
10 | 10 |
(...skipping 153 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
164 InstructionOperand* const hint_; | 164 InstructionOperand* const hint_; |
165 LifetimePosition const pos_; | 165 LifetimePosition const pos_; |
166 UsePosition* next_; | 166 UsePosition* next_; |
167 bool requires_reg_ : 1; | 167 bool requires_reg_ : 1; |
168 bool register_beneficial_ : 1; | 168 bool register_beneficial_ : 1; |
169 | 169 |
170 private: | 170 private: |
171 DISALLOW_COPY_AND_ASSIGN(UsePosition); | 171 DISALLOW_COPY_AND_ASSIGN(UsePosition); |
172 }; | 172 }; |
173 | 173 |
| 174 class SpillRange; |
174 | 175 |
175 // Representation of SSA values' live ranges as a collection of (continuous) | 176 // Representation of SSA values' live ranges as a collection of (continuous) |
176 // intervals over the instruction ordering. | 177 // intervals over the instruction ordering. |
177 class LiveRange FINAL : public ZoneObject { | 178 class LiveRange FINAL : public ZoneObject { |
178 public: | 179 public: |
179 static const int kInvalidAssignment = 0x7fffffff; | 180 static const int kInvalidAssignment = 0x7fffffff; |
180 | 181 |
181 LiveRange(int id, Zone* zone); | 182 LiveRange(int id, Zone* zone); |
182 | 183 |
183 UseInterval* first_interval() const { return first_interval_; } | 184 UseInterval* first_interval() const { return first_interval_; } |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
250 | 251 |
251 LifetimePosition End() const { | 252 LifetimePosition End() const { |
252 DCHECK(!IsEmpty()); | 253 DCHECK(!IsEmpty()); |
253 return last_interval_->end(); | 254 return last_interval_->end(); |
254 } | 255 } |
255 | 256 |
256 bool HasAllocatedSpillOperand() const; | 257 bool HasAllocatedSpillOperand() const; |
257 InstructionOperand* GetSpillOperand() const { return spill_operand_; } | 258 InstructionOperand* GetSpillOperand() const { return spill_operand_; } |
258 void SetSpillOperand(InstructionOperand* operand); | 259 void SetSpillOperand(InstructionOperand* operand); |
259 | 260 |
| 261 void SetSpillRange(SpillRange* spill_range) { spill_range_ = spill_range; } |
| 262 SpillRange* GetSpillRange() const { return spill_range_; } |
| 263 void CommitSpillOperand(InstructionOperand* operand); |
| 264 |
260 void SetSpillStartIndex(int start) { | 265 void SetSpillStartIndex(int start) { |
261 spill_start_index_ = Min(start, spill_start_index_); | 266 spill_start_index_ = Min(start, spill_start_index_); |
262 } | 267 } |
263 | 268 |
264 bool ShouldBeAllocatedBefore(const LiveRange* other) const; | 269 bool ShouldBeAllocatedBefore(const LiveRange* other) const; |
265 bool CanCover(LifetimePosition position) const; | 270 bool CanCover(LifetimePosition position) const; |
266 bool Covers(LifetimePosition position); | 271 bool Covers(LifetimePosition position); |
267 LifetimePosition FirstIntersection(LiveRange* other); | 272 LifetimePosition FirstIntersection(LiveRange* other); |
268 | 273 |
269 // Add a new interval or a new use position to this live range. | 274 // Add a new interval or a new use position to this live range. |
270 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 275 void EnsureInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
271 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); | 276 void AddUseInterval(LifetimePosition start, LifetimePosition end, Zone* zone); |
272 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, | 277 void AddUsePosition(LifetimePosition pos, InstructionOperand* operand, |
273 InstructionOperand* hint, Zone* zone); | 278 InstructionOperand* hint, Zone* zone); |
274 | 279 |
275 // Shorten the most recently added interval by setting a new start. | 280 // Shorten the most recently added interval by setting a new start. |
276 void ShortenTo(LifetimePosition start); | 281 void ShortenTo(LifetimePosition start); |
277 | 282 |
278 #ifdef DEBUG | 283 #ifdef DEBUG |
279 // True if target overlaps an existing interval. | 284 // True if target overlaps an existing interval. |
280 bool HasOverlap(UseInterval* target) const; | 285 bool HasOverlap(UseInterval* target) const; |
281 void Verify() const; | 286 void Verify() const; |
282 #endif | 287 #endif |
283 | 288 |
284 private: | 289 private: |
285 void ConvertOperands(Zone* zone); | 290 void ConvertOperands(Zone* zone); |
| 291 void ConvertUsesToOperand(InstructionOperand* op); |
286 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; | 292 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; |
287 void AdvanceLastProcessedMarker(UseInterval* to_start_of, | 293 void AdvanceLastProcessedMarker(UseInterval* to_start_of, |
288 LifetimePosition but_not_past) const; | 294 LifetimePosition but_not_past) const; |
289 | 295 |
290 int id_; | 296 int id_; |
291 bool spilled_; | 297 bool spilled_; |
292 RegisterKind kind_; | 298 RegisterKind kind_; |
293 int assigned_register_; | 299 int assigned_register_; |
294 UseInterval* last_interval_; | 300 UseInterval* last_interval_; |
295 UseInterval* first_interval_; | 301 UseInterval* first_interval_; |
296 UsePosition* first_pos_; | 302 UsePosition* first_pos_; |
297 LiveRange* parent_; | 303 LiveRange* parent_; |
298 LiveRange* next_; | 304 LiveRange* next_; |
299 // This is used as a cache, it doesn't affect correctness. | 305 // This is used as a cache, it doesn't affect correctness. |
300 mutable UseInterval* current_interval_; | 306 mutable UseInterval* current_interval_; |
301 UsePosition* last_processed_use_; | 307 UsePosition* last_processed_use_; |
302 // This is used as a cache, it's invalid outside of BuildLiveRanges. | 308 // This is used as a cache, it's invalid outside of BuildLiveRanges. |
303 InstructionOperand* current_hint_operand_; | 309 InstructionOperand* current_hint_operand_; |
304 InstructionOperand* spill_operand_; | 310 InstructionOperand* spill_operand_; |
305 int spill_start_index_; | 311 int spill_start_index_; |
| 312 SpillRange* spill_range_; |
306 | 313 |
307 friend class RegisterAllocator; // Assigns to kind_. | 314 friend class RegisterAllocator; // Assigns to kind_. |
308 | 315 |
309 DISALLOW_COPY_AND_ASSIGN(LiveRange); | 316 DISALLOW_COPY_AND_ASSIGN(LiveRange); |
310 }; | 317 }; |
311 | 318 |
312 | 319 |
| 320 class SpillRange : public ZoneObject { |
| 321 public: |
| 322 SpillRange(LiveRange* range, int id, Zone* zone); |
| 323 bool TryMerge(SpillRange* other, Zone* zone); |
| 324 void SetOperand(InstructionOperand* op); |
| 325 bool IsEmpty() { return live_ranges_.length() == 0; } |
| 326 int id() const { return id_; } |
| 327 UseInterval* interval() { return use_interval_; } |
| 328 RegisterKind Kind() const { return live_ranges_.at(0)->Kind(); } |
| 329 LifetimePosition End() const { return end_position_; } |
| 330 bool IsIntersectingWith(SpillRange* other); |
| 331 |
| 332 private: |
| 333 int id_; |
| 334 ZoneList<LiveRange*> live_ranges_; |
| 335 UseInterval* use_interval_; |
| 336 LifetimePosition end_position_; |
| 337 |
| 338 // Merge intervals, making sure the use intervals are sorted |
| 339 void MergeDisjointIntervals(UseInterval* other, Zone* zone); |
| 340 }; |
| 341 |
| 342 |
313 class RegisterAllocator FINAL : public ZoneObject { | 343 class RegisterAllocator FINAL : public ZoneObject { |
314 public: | 344 public: |
315 explicit RegisterAllocator(const RegisterConfiguration* config, | 345 explicit RegisterAllocator(const RegisterConfiguration* config, |
316 Zone* local_zone, Frame* frame, | 346 Zone* local_zone, Frame* frame, |
317 InstructionSequence* code, | 347 InstructionSequence* code, |
318 const char* debug_name = nullptr); | 348 const char* debug_name = nullptr); |
319 | 349 |
320 bool AllocationOk() { return allocation_ok_; } | 350 bool AllocationOk() { return allocation_ok_; } |
321 | 351 |
322 const ZoneList<LiveRange*>& live_ranges() const { return live_ranges_; } | 352 const ZoneList<LiveRange*>& live_ranges() const { return live_ranges_; } |
(...skipping 11 matching lines...) Expand all Loading... |
334 void MeetRegisterConstraints(); | 364 void MeetRegisterConstraints(); |
335 | 365 |
336 // Phase 2: compute liveness of all virtual register. | 366 // Phase 2: compute liveness of all virtual register. |
337 void BuildLiveRanges(); | 367 void BuildLiveRanges(); |
338 bool ExistsUseWithoutDefinition(); | 368 bool ExistsUseWithoutDefinition(); |
339 | 369 |
340 // Phase 3: compute register assignments. | 370 // Phase 3: compute register assignments. |
341 void AllocateGeneralRegisters(); | 371 void AllocateGeneralRegisters(); |
342 void AllocateDoubleRegisters(); | 372 void AllocateDoubleRegisters(); |
343 | 373 |
344 // Phase 4: compute values for pointer maps. | 374 // Phase 4: reassign spill splots for maximal reuse. |
| 375 void ReuseSpillSlots(); |
| 376 |
| 377 // Phase 5: compute values for pointer maps. |
345 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. | 378 void PopulatePointerMaps(); // TODO(titzer): rename to PopulateReferenceMaps. |
346 | 379 |
347 // Phase 5: reconnect split ranges with moves. | 380 // Phase 6: reconnect split ranges with moves. |
348 void ConnectRanges(); | 381 void ConnectRanges(); |
349 | 382 |
350 // Phase 6: insert moves to connect ranges across basic blocks. | 383 // Phase 7: insert moves to connect ranges across basic blocks. |
351 void ResolveControlFlow(); | 384 void ResolveControlFlow(); |
352 | 385 |
353 private: | 386 private: |
354 int GetVirtualRegister() { | 387 int GetVirtualRegister() { |
355 int vreg = code()->NextVirtualRegister(); | 388 int vreg = code()->NextVirtualRegister(); |
356 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { | 389 if (vreg >= UnallocatedOperand::kMaxVirtualRegisters) { |
357 allocation_ok_ = false; | 390 allocation_ok_ = false; |
358 // Maintain the invariant that we return something below the maximum. | 391 // Maintain the invariant that we return something below the maximum. |
359 return 0; | 392 return 0; |
360 } | 393 } |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
412 void AddToActive(LiveRange* range); | 445 void AddToActive(LiveRange* range); |
413 void AddToInactive(LiveRange* range); | 446 void AddToInactive(LiveRange* range); |
414 void AddToUnhandledSorted(LiveRange* range); | 447 void AddToUnhandledSorted(LiveRange* range); |
415 void AddToUnhandledUnsorted(LiveRange* range); | 448 void AddToUnhandledUnsorted(LiveRange* range); |
416 void SortUnhandled(); | 449 void SortUnhandled(); |
417 bool UnhandledIsSorted(); | 450 bool UnhandledIsSorted(); |
418 void ActiveToHandled(LiveRange* range); | 451 void ActiveToHandled(LiveRange* range); |
419 void ActiveToInactive(LiveRange* range); | 452 void ActiveToInactive(LiveRange* range); |
420 void InactiveToHandled(LiveRange* range); | 453 void InactiveToHandled(LiveRange* range); |
421 void InactiveToActive(LiveRange* range); | 454 void InactiveToActive(LiveRange* range); |
422 void FreeSpillSlot(LiveRange* range); | |
423 InstructionOperand* TryReuseSpillSlot(LiveRange* range); | |
424 | 455 |
425 // Helper methods for allocating registers. | 456 // Helper methods for allocating registers. |
426 bool TryAllocateFreeReg(LiveRange* range); | 457 bool TryAllocateFreeReg(LiveRange* range); |
427 void AllocateBlockedReg(LiveRange* range); | 458 void AllocateBlockedReg(LiveRange* range); |
| 459 SpillRange* AssignSpillRangeToLiveRange(LiveRange* range); |
428 | 460 |
429 // Live range splitting helpers. | 461 // Live range splitting helpers. |
430 | 462 |
431 // Split the given range at the given position. | 463 // Split the given range at the given position. |
432 // If range starts at or after the given position then the | 464 // If range starts at or after the given position then the |
433 // original range is returned. | 465 // original range is returned. |
434 // Otherwise returns the live range that starts at pos and contains | 466 // Otherwise returns the live range that starts at pos and contains |
435 // all uses from the original range that follow pos. Uses at pos will | 467 // all uses from the original range that follow pos. Uses at pos will |
436 // still be owned by the original range after splitting. | 468 // still be owned by the original range after splitting. |
437 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); | 469 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
514 // Liveness analysis results. | 546 // Liveness analysis results. |
515 ZoneList<LiveRange*> live_ranges_; | 547 ZoneList<LiveRange*> live_ranges_; |
516 | 548 |
517 // Lists of live ranges | 549 // Lists of live ranges |
518 ZoneVector<LiveRange*> fixed_live_ranges_; | 550 ZoneVector<LiveRange*> fixed_live_ranges_; |
519 ZoneVector<LiveRange*> fixed_double_live_ranges_; | 551 ZoneVector<LiveRange*> fixed_double_live_ranges_; |
520 ZoneList<LiveRange*> unhandled_live_ranges_; | 552 ZoneList<LiveRange*> unhandled_live_ranges_; |
521 ZoneList<LiveRange*> active_live_ranges_; | 553 ZoneList<LiveRange*> active_live_ranges_; |
522 ZoneList<LiveRange*> inactive_live_ranges_; | 554 ZoneList<LiveRange*> inactive_live_ranges_; |
523 ZoneList<LiveRange*> reusable_slots_; | 555 ZoneList<LiveRange*> reusable_slots_; |
| 556 ZoneList<SpillRange*> spill_ranges_; |
524 | 557 |
525 RegisterKind mode_; | 558 RegisterKind mode_; |
526 int num_registers_; | 559 int num_registers_; |
527 | 560 |
528 BitVector* assigned_registers_; | 561 BitVector* assigned_registers_; |
529 BitVector* assigned_double_registers_; | 562 BitVector* assigned_double_registers_; |
530 | 563 |
531 // Indicates success or failure during register allocation. | 564 // Indicates success or failure during register allocation. |
532 bool allocation_ok_; | 565 bool allocation_ok_; |
533 | 566 |
534 #ifdef DEBUG | 567 #ifdef DEBUG |
535 LifetimePosition allocation_finger_; | 568 LifetimePosition allocation_finger_; |
536 #endif | 569 #endif |
537 | 570 |
538 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); | 571 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
539 }; | 572 }; |
540 | 573 |
541 } | 574 } |
542 } | 575 } |
543 } // namespace v8::internal::compiler | 576 } // namespace v8::internal::compiler |
544 | 577 |
545 #endif // V8_REGISTER_ALLOCATOR_H_ | 578 #endif // V8_REGISTER_ALLOCATOR_H_ |
OLD | NEW |