Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(819)

Side by Side Diff: src/lithium-allocator.h

Issue 310003003: More aggressive reuse of spill slots in the register allocator. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Created 6 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 // Copyright 2012 the V8 project authors. All rights reserved. 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 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_LITHIUM_ALLOCATOR_H_ 5 #ifndef V8_LITHIUM_ALLOCATOR_H_
6 #define V8_LITHIUM_ALLOCATOR_H_ 6 #define V8_LITHIUM_ALLOCATOR_H_
7 7
8 #include "src/v8.h" 8 #include "src/v8.h"
9 9
10 #include "src/allocation.h" 10 #include "src/allocation.h"
(...skipping 194 matching lines...) Expand 10 before | Expand all | Expand 10 after
205 } 205 }
206 206
207 private: 207 private:
208 void set_start(LifetimePosition start) { start_ = start; } 208 void set_start(LifetimePosition start) { start_ = start; }
209 void set_next(UseInterval* next) { next_ = next; } 209 void set_next(UseInterval* next) { next_ = next; }
210 210
211 LifetimePosition start_; 211 LifetimePosition start_;
212 LifetimePosition end_; 212 LifetimePosition end_;
213 UseInterval* next_; 213 UseInterval* next_;
214 214
215 friend class LAllocator; // Assigns to next_.
216 friend class SpillRange; // Assigns to next_.
215 friend class LiveRange; // Assigns to start_. 217 friend class LiveRange; // Assigns to start_.
216 }; 218 };
217 219
218 // Representation of a use position. 220 // Representation of a use position.
219 class UsePosition: public ZoneObject { 221 class UsePosition: public ZoneObject {
220 public: 222 public:
221 UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint); 223 UsePosition(LifetimePosition pos, LOperand* operand, LOperand* hint);
222 224
223 LOperand* operand() const { return operand_; } 225 LOperand* operand() const { return operand_; }
224 bool HasOperand() const { return operand_ != NULL; } 226 bool HasOperand() const { return operand_ != NULL; }
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after
319 321
320 LifetimePosition End() const { 322 LifetimePosition End() const {
321 ASSERT(!IsEmpty()); 323 ASSERT(!IsEmpty());
322 return last_interval_->end(); 324 return last_interval_->end();
323 } 325 }
324 326
325 bool HasAllocatedSpillOperand() const; 327 bool HasAllocatedSpillOperand() const;
326 LOperand* GetSpillOperand() const { return spill_operand_; } 328 LOperand* GetSpillOperand() const { return spill_operand_; }
327 void SetSpillOperand(LOperand* operand); 329 void SetSpillOperand(LOperand* operand);
328 330
331 void SetSpillRangeId(int spill_index) { spill_range_id_ = spill_index; }
332 int GetSpillRangeId() { return spill_range_id_; }
333 void CommitSpillOperand(LOperand* operand);
334
329 void SetSpillStartIndex(int start) { 335 void SetSpillStartIndex(int start) {
330 spill_start_index_ = Min(start, spill_start_index_); 336 spill_start_index_ = Min(start, spill_start_index_);
331 } 337 }
332 338
333 bool ShouldBeAllocatedBefore(const LiveRange* other) const; 339 bool ShouldBeAllocatedBefore(const LiveRange* other) const;
334 bool CanCover(LifetimePosition position) const; 340 bool CanCover(LifetimePosition position) const;
335 bool Covers(LifetimePosition position); 341 bool Covers(LifetimePosition position);
336 LifetimePosition FirstIntersection(LiveRange* other); 342 LifetimePosition FirstIntersection(LiveRange* other);
337 343
338 // Add a new interval or a new use position to this live range. 344 // Add a new interval or a new use position to this live range.
(...skipping 12 matching lines...) Expand all
351 void ShortenTo(LifetimePosition start); 357 void ShortenTo(LifetimePosition start);
352 358
353 #ifdef DEBUG 359 #ifdef DEBUG
354 // True if target overlaps an existing interval. 360 // True if target overlaps an existing interval.
355 bool HasOverlap(UseInterval* target) const; 361 bool HasOverlap(UseInterval* target) const;
356 void Verify() const; 362 void Verify() const;
357 #endif 363 #endif
358 364
359 private: 365 private:
360 void ConvertOperands(Zone* zone); 366 void ConvertOperands(Zone* zone);
367 void ConvertUsesToOperand(LOperand* op);
361 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const; 368 UseInterval* FirstSearchIntervalForPosition(LifetimePosition position) const;
362 void AdvanceLastProcessedMarker(UseInterval* to_start_of, 369 void AdvanceLastProcessedMarker(UseInterval* to_start_of,
363 LifetimePosition but_not_past) const; 370 LifetimePosition but_not_past) const;
364 371
365 int id_; 372 int id_;
366 bool spilled_; 373 bool spilled_;
367 RegisterKind kind_; 374 RegisterKind kind_;
368 int assigned_register_; 375 int assigned_register_;
369 UseInterval* last_interval_; 376 UseInterval* last_interval_;
370 UseInterval* first_interval_; 377 UseInterval* first_interval_;
371 UsePosition* first_pos_; 378 UsePosition* first_pos_;
372 LiveRange* parent_; 379 LiveRange* parent_;
373 LiveRange* next_; 380 LiveRange* next_;
374 // This is used as a cache, it doesn't affect correctness. 381 // This is used as a cache, it doesn't affect correctness.
375 mutable UseInterval* current_interval_; 382 mutable UseInterval* current_interval_;
376 UsePosition* last_processed_use_; 383 UsePosition* last_processed_use_;
377 // This is used as a cache, it's invalid outside of BuildLiveRanges. 384 // This is used as a cache, it's invalid outside of BuildLiveRanges.
378 LOperand* current_hint_operand_; 385 LOperand* current_hint_operand_;
379 LOperand* spill_operand_; 386 LOperand* spill_operand_;
380 int spill_start_index_; 387 int spill_start_index_;
388 int spill_range_id_;
titzer 2014/06/17 09:01:34 Why not a direct pointer to the SpillRange?
Jarin 2014/06/24 21:49:58 Done.
381 389
382 friend class LAllocator; // Assigns to kind_. 390 friend class LAllocator; // Assigns to kind_.
383 }; 391 };
384 392
385 393
394 class SpillRange: public ZoneObject {
395 public:
396 SpillRange(LiveRange* range, int id, Zone* zone);
397
398 bool TryMerge(SpillRange* other, Zone* zone);
399 void SetOperand(LOperand* op);
400 bool IsEmpty() { return live_ranges_.length() == 0; }
401 int id() const { return id_; }
402 UseInterval* interval() { return use_interval_; }
403 RegisterKind Kind() const { return live_ranges_.at(0)->Kind(); }
404
405 static const int INVALID_ID = -1;
406
407 private:
408 int id_;
409 ZoneList<LiveRange*> live_ranges_;
410 UseInterval* use_interval_;
411
412 static void Swap(UseInterval*& a, UseInterval*& b);
413
414 // Merge intervals, making sure the use intervals are sorted
415 void MergeDisjointIntervals(UseInterval* other, Zone* zone);
416 };
417
418
386 class LAllocator BASE_EMBEDDED { 419 class LAllocator BASE_EMBEDDED {
387 public: 420 public:
388 LAllocator(int first_virtual_register, HGraph* graph); 421 LAllocator(int first_virtual_register, HGraph* graph);
389 422
390 static void TraceAlloc(const char* msg, ...); 423 static void TraceAlloc(const char* msg, ...);
391 424
392 // Checks whether the value of a given virtual register is tagged. 425 // Checks whether the value of a given virtual register is tagged.
393 bool HasTaggedValue(int virtual_register) const; 426 bool HasTaggedValue(int virtual_register) const;
394 427
395 // Returns the register kind required by the given virtual register. 428 // Returns the register kind required by the given virtual register.
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
442 private: 475 private:
443 void MeetRegisterConstraints(); 476 void MeetRegisterConstraints();
444 void ResolvePhis(); 477 void ResolvePhis();
445 void BuildLiveRanges(); 478 void BuildLiveRanges();
446 void AllocateGeneralRegisters(); 479 void AllocateGeneralRegisters();
447 void AllocateDoubleRegisters(); 480 void AllocateDoubleRegisters();
448 void ConnectRanges(); 481 void ConnectRanges();
449 void ResolveControlFlow(); 482 void ResolveControlFlow();
450 void PopulatePointerMaps(); 483 void PopulatePointerMaps();
451 void AllocateRegisters(); 484 void AllocateRegisters();
485 void ReuseSpillSlots();
452 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const; 486 bool CanEagerlyResolveControlFlow(HBasicBlock* block) const;
453 inline bool SafePointsAreInOrder() const; 487 inline bool SafePointsAreInOrder() const;
454 488
455 // Liveness analysis support. 489 // Liveness analysis support.
456 void InitializeLivenessAnalysis(); 490 void InitializeLivenessAnalysis();
457 BitVector* ComputeLiveOut(HBasicBlock* block); 491 BitVector* ComputeLiveOut(HBasicBlock* block);
458 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out); 492 void AddInitialIntervals(HBasicBlock* block, BitVector* live_out);
459 void ProcessInstructions(HBasicBlock* block, BitVector* live); 493 void ProcessInstructions(HBasicBlock* block, BitVector* live);
460 void MeetRegisterConstraints(HBasicBlock* block); 494 void MeetRegisterConstraints(HBasicBlock* block);
461 void MeetConstraintsBetween(LInstruction* first, 495 void MeetConstraintsBetween(LInstruction* first,
(...skipping 15 matching lines...) Expand all
477 void AddToActive(LiveRange* range); 511 void AddToActive(LiveRange* range);
478 void AddToInactive(LiveRange* range); 512 void AddToInactive(LiveRange* range);
479 void AddToUnhandledSorted(LiveRange* range); 513 void AddToUnhandledSorted(LiveRange* range);
480 void AddToUnhandledUnsorted(LiveRange* range); 514 void AddToUnhandledUnsorted(LiveRange* range);
481 void SortUnhandled(); 515 void SortUnhandled();
482 bool UnhandledIsSorted(); 516 bool UnhandledIsSorted();
483 void ActiveToHandled(LiveRange* range); 517 void ActiveToHandled(LiveRange* range);
484 void ActiveToInactive(LiveRange* range); 518 void ActiveToInactive(LiveRange* range);
485 void InactiveToHandled(LiveRange* range); 519 void InactiveToHandled(LiveRange* range);
486 void InactiveToActive(LiveRange* range); 520 void InactiveToActive(LiveRange* range);
487 void FreeSpillSlot(LiveRange* range); 521 SpillRange* AssignSpillRangeToLiveRange(LiveRange* range);
488 LOperand* TryReuseSpillSlot(LiveRange* range);
489 522
490 // Helper methods for allocating registers. 523 // Helper methods for allocating registers.
491 bool TryAllocateFreeReg(LiveRange* range); 524 bool TryAllocateFreeReg(LiveRange* range);
492 void AllocateBlockedReg(LiveRange* range); 525 void AllocateBlockedReg(LiveRange* range);
526 bool TryReuseSpillForPhi(LiveRange* range);
493 527
494 // Live range splitting helpers. 528 // Live range splitting helpers.
495 529
496 // Split the given range at the given position. 530 // Split the given range at the given position.
497 // If range starts at or after the given position then the 531 // If range starts at or after the given position then the
498 // original range is returned. 532 // original range is returned.
499 // Otherwise returns the live range that starts at pos and contains 533 // Otherwise returns the live range that starts at pos and contains
500 // all uses from the original range that follow pos. Uses at pos will 534 // all uses from the original range that follow pos. Uses at pos will
501 // still be owned by the original range after splitting. 535 // still be owned by the original range after splitting.
502 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos); 536 LiveRange* SplitRangeAt(LiveRange* range, LifetimePosition pos);
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after
582 616
583 // Lists of live ranges 617 // Lists of live ranges
584 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters> 618 EmbeddedVector<LiveRange*, Register::kMaxNumAllocatableRegisters>
585 fixed_live_ranges_; 619 fixed_live_ranges_;
586 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters> 620 EmbeddedVector<LiveRange*, DoubleRegister::kMaxNumAllocatableRegisters>
587 fixed_double_live_ranges_; 621 fixed_double_live_ranges_;
588 ZoneList<LiveRange*> unhandled_live_ranges_; 622 ZoneList<LiveRange*> unhandled_live_ranges_;
589 ZoneList<LiveRange*> active_live_ranges_; 623 ZoneList<LiveRange*> active_live_ranges_;
590 ZoneList<LiveRange*> inactive_live_ranges_; 624 ZoneList<LiveRange*> inactive_live_ranges_;
591 ZoneList<LiveRange*> reusable_slots_; 625 ZoneList<LiveRange*> reusable_slots_;
626 ZoneList<SpillRange*> spill_ranges_;
592 627
593 // Next virtual register number to be assigned to temporaries. 628 // Next virtual register number to be assigned to temporaries.
594 int next_virtual_register_; 629 int next_virtual_register_;
595 int first_artificial_register_; 630 int first_artificial_register_;
596 GrowableBitVector double_artificial_registers_; 631 GrowableBitVector double_artificial_registers_;
597 632
598 RegisterKind mode_; 633 RegisterKind mode_;
599 int num_registers_; 634 int num_registers_;
600 635
601 BitVector* assigned_registers_; 636 BitVector* assigned_registers_;
(...skipping 23 matching lines...) Expand all
625 LAllocator* allocator_; 660 LAllocator* allocator_;
626 unsigned allocator_zone_start_allocation_size_; 661 unsigned allocator_zone_start_allocation_size_;
627 662
628 DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase); 663 DISALLOW_COPY_AND_ASSIGN(LAllocatorPhase);
629 }; 664 };
630 665
631 666
632 } } // namespace v8::internal 667 } } // namespace v8::internal
633 668
634 #endif // V8_LITHIUM_ALLOCATOR_H_ 669 #endif // V8_LITHIUM_ALLOCATOR_H_
OLDNEW
« no previous file with comments | « src/hydrogen.cc ('k') | src/lithium-allocator.cc » ('j') | src/lithium-allocator.cc » ('J')

Powered by Google App Engine
This is Rietveld 408576698