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

Side by Side Diff: src/compiler/register-allocator.cc

Issue 1111563004: [turbofan] Cleanup LiveRange a bit. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 8 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
« no previous file with comments | « src/compiler/register-allocator.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 #include "src/base/adapters.h" 5 #include "src/base/adapters.h"
6 #include "src/compiler/linkage.h" 6 #include "src/compiler/linkage.h"
7 #include "src/compiler/register-allocator.h" 7 #include "src/compiler/register-allocator.h"
8 #include "src/string-stream.h" 8 #include "src/string-stream.h"
9 9
10 namespace v8 { 10 namespace v8 {
(...skipping 198 matching lines...) Expand 10 before | Expand all | Expand 10 after
209 SpillAtDefinitionList* next) 209 SpillAtDefinitionList* next)
210 : gap_index(gap_index), operand(operand), next(next) {} 210 : gap_index(gap_index), operand(operand), next(next) {}
211 const int gap_index; 211 const int gap_index;
212 InstructionOperand* const operand; 212 InstructionOperand* const operand;
213 SpillAtDefinitionList* const next; 213 SpillAtDefinitionList* const next;
214 }; 214 };
215 215
216 216
217 LiveRange::LiveRange(int id) 217 LiveRange::LiveRange(int id)
218 : id_(id), 218 : id_(id),
219 spilled_(false), 219 spill_start_index_(kMaxInt),
220 has_slot_use_(false), 220 bits_(0),
221 is_phi_(false),
222 is_non_loop_phi_(false),
223 kind_(UNALLOCATED_REGISTERS),
224 assigned_register_(kUnassignedRegister),
225 last_interval_(nullptr), 221 last_interval_(nullptr),
226 first_interval_(nullptr), 222 first_interval_(nullptr),
227 first_pos_(nullptr), 223 first_pos_(nullptr),
228 parent_(nullptr), 224 parent_(nullptr),
229 next_(nullptr), 225 next_(nullptr),
226 spill_operand_(nullptr),
227 spills_at_definition_(nullptr),
230 current_interval_(nullptr), 228 current_interval_(nullptr),
231 last_processed_use_(nullptr), 229 last_processed_use_(nullptr),
232 current_hint_position_(nullptr), 230 current_hint_position_(nullptr) {
233 spill_start_index_(kMaxInt), 231 bits_ = SpillTypeField::encode(SpillType::kNoSpillType) |
234 spill_type_(SpillType::kNoSpillType), 232 AssignedRegisterField::encode(kUnassignedRegister);
235 spill_operand_(nullptr), 233 }
236 spills_at_definition_(nullptr) {}
237 234
238 235
239 void LiveRange::Verify() const { 236 void LiveRange::Verify() const {
240 // Walk the positions, verifying that each is in an interval. 237 // Walk the positions, verifying that each is in an interval.
241 auto interval = first_interval_; 238 auto interval = first_interval_;
242 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { 239 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
243 CHECK(Start() <= pos->pos()); 240 CHECK(Start() <= pos->pos());
244 CHECK(pos->pos() <= End()); 241 CHECK(pos->pos() <= End());
245 CHECK(interval != nullptr); 242 CHECK(interval != nullptr);
246 while (!interval->Contains(pos->pos()) && interval->end() != pos->pos()) { 243 while (!interval->Contains(pos->pos()) && interval->end() != pos->pos()) {
247 interval = interval->next(); 244 interval = interval->next();
248 CHECK(interval != nullptr); 245 CHECK(interval != nullptr);
249 } 246 }
250 } 247 }
251 } 248 }
252 249
253 250
254 void LiveRange::set_assigned_register(int reg) { 251 void LiveRange::set_assigned_register(int reg) {
255 DCHECK(!HasRegisterAssigned() && !IsSpilled()); 252 DCHECK(!HasRegisterAssigned() && !spilled());
256 assigned_register_ = reg; 253 bits_ = AssignedRegisterField::update(bits_, reg);
257 } 254 }
258 255
259 256
260 void LiveRange::UnsetAssignedRegister() { 257 void LiveRange::UnsetAssignedRegister() {
261 DCHECK(HasRegisterAssigned() && !IsSpilled()); 258 DCHECK(HasRegisterAssigned() && !spilled());
262 assigned_register_ = kUnassignedRegister; 259 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister);
263 } 260 }
264 261
265 262
266 void LiveRange::MakeSpilled() { 263 void LiveRange::Spill() {
267 DCHECK(!IsSpilled()); 264 DCHECK(!spilled());
268 DCHECK(!TopLevel()->HasNoSpillType()); 265 DCHECK(!TopLevel()->HasNoSpillType());
269 spilled_ = true; 266 set_spilled(true);
270 assigned_register_ = kUnassignedRegister; 267 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister);
271 } 268 }
272 269
273 270
274 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index, 271 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index,
275 InstructionOperand* operand) { 272 InstructionOperand* operand) {
276 DCHECK(HasNoSpillType()); 273 DCHECK(HasNoSpillType());
277 spills_at_definition_ = new (zone) 274 spills_at_definition_ = new (zone)
278 SpillAtDefinitionList(gap_index, operand, spills_at_definition_); 275 SpillAtDefinitionList(gap_index, operand, spills_at_definition_);
279 } 276 }
280 277
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after
312 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { 309 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
313 if (pos->HintRegister(register_index)) return pos; 310 if (pos->HintRegister(register_index)) return pos;
314 } 311 }
315 return nullptr; 312 return nullptr;
316 } 313 }
317 314
318 315
319 void LiveRange::SetSpillOperand(InstructionOperand* operand) { 316 void LiveRange::SetSpillOperand(InstructionOperand* operand) {
320 DCHECK(HasNoSpillType()); 317 DCHECK(HasNoSpillType());
321 DCHECK(!operand->IsUnallocated() && !operand->IsImmediate()); 318 DCHECK(!operand->IsUnallocated() && !operand->IsImmediate());
322 spill_type_ = SpillType::kSpillOperand; 319 set_spill_type(SpillType::kSpillOperand);
323 spill_operand_ = operand; 320 spill_operand_ = operand;
324 } 321 }
325 322
326 323
327 void LiveRange::SetSpillRange(SpillRange* spill_range) { 324 void LiveRange::SetSpillRange(SpillRange* spill_range) {
328 DCHECK(HasNoSpillType() || HasSpillRange()); 325 DCHECK(HasNoSpillType() || HasSpillRange());
329 DCHECK(spill_range); 326 DCHECK(spill_range);
330 spill_type_ = SpillType::kSpillRange; 327 set_spill_type(SpillType::kSpillRange);
331 spill_range_ = spill_range; 328 spill_range_ = spill_range;
332 } 329 }
333 330
334 331
335 void LiveRange::CommitSpillOperand(AllocatedOperand* operand) { 332 void LiveRange::CommitSpillOperand(AllocatedOperand* operand) {
336 DCHECK(HasSpillRange()); 333 DCHECK(HasSpillRange());
337 DCHECK(!IsChild()); 334 DCHECK(!IsChild());
338 spill_type_ = SpillType::kSpillOperand; 335 set_spill_type(SpillType::kSpillOperand);
339 spill_operand_ = operand; 336 spill_operand_ = operand;
340 } 337 }
341 338
342 339
343 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const { 340 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const {
344 UsePosition* use_pos = last_processed_use_; 341 UsePosition* use_pos = last_processed_use_;
345 if (use_pos == nullptr || use_pos->pos() > start) { 342 if (use_pos == nullptr || use_pos->pos() > start) {
346 use_pos = first_pos(); 343 use_pos = first_pos();
347 } 344 }
348 while (use_pos != nullptr && use_pos->pos() < start) { 345 while (use_pos != nullptr && use_pos->pos() < start) {
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after
388 // We cannot spill a live range that has a use requiring a register 385 // We cannot spill a live range that has a use requiring a register
389 // at the current or the immediate next position. 386 // at the current or the immediate next position.
390 auto use_pos = NextRegisterPosition(pos); 387 auto use_pos = NextRegisterPosition(pos);
391 if (use_pos == nullptr) return true; 388 if (use_pos == nullptr) return true;
392 return use_pos->pos() > pos.NextStart().End(); 389 return use_pos->pos() > pos.NextStart().End();
393 } 390 }
394 391
395 392
396 InstructionOperand LiveRange::GetAssignedOperand() const { 393 InstructionOperand LiveRange::GetAssignedOperand() const {
397 if (HasRegisterAssigned()) { 394 if (HasRegisterAssigned()) {
398 DCHECK(!IsSpilled()); 395 DCHECK(!spilled());
399 switch (Kind()) { 396 switch (kind()) {
400 case GENERAL_REGISTERS: 397 case GENERAL_REGISTERS:
401 return RegisterOperand(assigned_register()); 398 return RegisterOperand(assigned_register());
402 case DOUBLE_REGISTERS: 399 case DOUBLE_REGISTERS:
403 return DoubleRegisterOperand(assigned_register()); 400 return DoubleRegisterOperand(assigned_register());
404 default: 401 default:
405 UNREACHABLE(); 402 UNREACHABLE();
406 } 403 }
407 } 404 }
408 DCHECK(IsSpilled()); 405 DCHECK(spilled());
409 DCHECK(!HasRegisterAssigned()); 406 DCHECK(!HasRegisterAssigned());
410 auto op = TopLevel()->GetSpillOperand(); 407 auto op = TopLevel()->GetSpillOperand();
411 DCHECK(!op->IsUnallocated()); 408 DCHECK(!op->IsUnallocated());
412 return *op; 409 return *op;
413 } 410 }
414 411
415 412
416 UseInterval* LiveRange::FirstSearchIntervalForPosition( 413 UseInterval* LiveRange::FirstSearchIntervalForPosition(
417 LifetimePosition position) const { 414 LifetimePosition position) const {
418 if (current_interval_ == nullptr) return first_interval_; 415 if (current_interval_ == nullptr) return first_interval_;
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after
462 } 459 }
463 auto next = current->next(); 460 auto next = current->next();
464 if (next->start() >= position) { 461 if (next->start() >= position) {
465 split_at_start = (next->start() == position); 462 split_at_start = (next->start() == position);
466 after = next; 463 after = next;
467 current->set_next(nullptr); 464 current->set_next(nullptr);
468 break; 465 break;
469 } 466 }
470 current = next; 467 current = next;
471 } 468 }
469 DCHECK(nullptr != after);
472 470
473 // Partition original use intervals to the two live ranges. 471 // Partition original use intervals to the two live ranges.
474 auto before = current; 472 auto before = current;
475 result->last_interval_ = 473 result->last_interval_ =
476 (last_interval_ == before) 474 (last_interval_ == before)
477 ? after // Only interval in the range after split. 475 ? after // Only interval in the range after split.
478 : last_interval_; // Last interval of the original range. 476 : last_interval_; // Last interval of the original range.
479 result->first_interval_ = after; 477 result->first_interval_ = after;
480 last_interval_ = before; 478 last_interval_ = before;
481 479
(...skipping 25 matching lines...) Expand all
507 result->first_pos_ = use_after; 505 result->first_pos_ = use_after;
508 506
509 // Discard cached iteration state. It might be pointing 507 // Discard cached iteration state. It might be pointing
510 // to the use that no longer belongs to this live range. 508 // to the use that no longer belongs to this live range.
511 last_processed_use_ = nullptr; 509 last_processed_use_ = nullptr;
512 current_interval_ = nullptr; 510 current_interval_ = nullptr;
513 511
514 // Link the new live range in the chain before any of the other 512 // Link the new live range in the chain before any of the other
515 // ranges linked from the range before the split. 513 // ranges linked from the range before the split.
516 result->parent_ = (parent_ == nullptr) ? this : parent_; 514 result->parent_ = (parent_ == nullptr) ? this : parent_;
517 result->kind_ = result->parent_->kind_; 515 result->set_kind(result->parent_->kind());
518 result->next_ = next_; 516 result->next_ = next_;
519 next_ = result; 517 next_ = result;
520 518
521 #ifdef DEBUG 519 #ifdef DEBUG
522 Verify(); 520 Verify();
523 result->Verify(); 521 result->Verify();
524 #endif 522 #endif
525 } 523 }
526 524
527 525
(...skipping 230 matching lines...) Expand 10 before | Expand all | Expand 10 after
758 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr || 756 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr ||
759 this->End() <= other->use_interval_->start() || 757 this->End() <= other->use_interval_->start() ||
760 other->End() <= this->use_interval_->start()) { 758 other->End() <= this->use_interval_->start()) {
761 return false; 759 return false;
762 } 760 }
763 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_); 761 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_);
764 } 762 }
765 763
766 764
767 bool SpillRange::TryMerge(SpillRange* other) { 765 bool SpillRange::TryMerge(SpillRange* other) {
768 if (Kind() != other->Kind() || IsIntersectingWith(other)) return false; 766 if (kind() != other->kind() || IsIntersectingWith(other)) return false;
769 767
770 auto max = LifetimePosition::MaxPosition(); 768 auto max = LifetimePosition::MaxPosition();
771 if (End() < other->End() && other->End() != max) { 769 if (End() < other->End() && other->End() != max) {
772 end_position_ = other->End(); 770 end_position_ = other->End();
773 } 771 }
774 other->end_position_ = max; 772 other->end_position_ = max;
775 773
776 MergeDisjointIntervals(other->use_interval_); 774 MergeDisjointIntervals(other->use_interval_);
777 other->use_interval_ = nullptr; 775 other->use_interval_ = nullptr;
778 776
(...skipping 952 matching lines...) Expand 10 before | Expand all | Expand 10 after
1731 1729
1732 // Try hoisting out to an outer loop. 1730 // Try hoisting out to an outer loop.
1733 loop_header = GetContainingLoop(code(), loop_header); 1731 loop_header = GetContainingLoop(code(), loop_header);
1734 } 1732 }
1735 1733
1736 return pos; 1734 return pos;
1737 } 1735 }
1738 1736
1739 1737
1740 void RegisterAllocator::Spill(LiveRange* range) { 1738 void RegisterAllocator::Spill(LiveRange* range) {
1741 DCHECK(!range->IsSpilled()); 1739 DCHECK(!range->spilled());
1742 TRACE("Spilling live range %d\n", range->id()); 1740 TRACE("Spilling live range %d\n", range->id());
1743 auto first = range->TopLevel(); 1741 auto first = range->TopLevel();
1744 if (first->HasNoSpillType()) { 1742 if (first->HasNoSpillType()) {
1745 data()->AssignSpillRangeToLiveRange(first); 1743 data()->AssignSpillRangeToLiveRange(first);
1746 } 1744 }
1747 range->MakeSpilled(); 1745 range->Spill();
1748 } 1746 }
1749 1747
1750 1748
1751 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data, 1749 LinearScanAllocator::LinearScanAllocator(RegisterAllocationData* data,
1752 RegisterKind kind, Zone* local_zone) 1750 RegisterKind kind, Zone* local_zone)
1753 : RegisterAllocator(data, kind), 1751 : RegisterAllocator(data, kind),
1754 unhandled_live_ranges_(local_zone), 1752 unhandled_live_ranges_(local_zone),
1755 active_live_ranges_(local_zone), 1753 active_live_ranges_(local_zone),
1756 inactive_live_ranges_(local_zone) { 1754 inactive_live_ranges_(local_zone) {
1757 unhandled_live_ranges().reserve( 1755 unhandled_live_ranges().reserve(
1758 static_cast<size_t>(code()->VirtualRegisterCount() * 2)); 1756 static_cast<size_t>(code()->VirtualRegisterCount() * 2));
1759 active_live_ranges().reserve(8); 1757 active_live_ranges().reserve(8);
1760 inactive_live_ranges().reserve(8); 1758 inactive_live_ranges().reserve(8);
1761 // TryAllocateFreeReg and AllocateBlockedReg assume this 1759 // TryAllocateFreeReg and AllocateBlockedReg assume this
1762 // when allocating local arrays. 1760 // when allocating local arrays.
1763 DCHECK(RegisterConfiguration::kMaxDoubleRegisters >= 1761 DCHECK(RegisterConfiguration::kMaxDoubleRegisters >=
1764 this->data()->config()->num_general_registers()); 1762 this->data()->config()->num_general_registers());
1765 } 1763 }
1766 1764
1767 1765
1768 void LinearScanAllocator::AllocateRegisters() { 1766 void LinearScanAllocator::AllocateRegisters() {
1769 DCHECK(unhandled_live_ranges().empty()); 1767 DCHECK(unhandled_live_ranges().empty());
1770 DCHECK(active_live_ranges().empty()); 1768 DCHECK(active_live_ranges().empty());
1771 DCHECK(inactive_live_ranges().empty()); 1769 DCHECK(inactive_live_ranges().empty());
1772 1770
1773 for (auto range : data()->live_ranges()) { 1771 for (auto range : data()->live_ranges()) {
1774 if (range == nullptr) continue; 1772 if (range == nullptr) continue;
1775 if (range->Kind() == mode()) { 1773 if (range->kind() == mode()) {
1776 AddToUnhandledUnsorted(range); 1774 AddToUnhandledUnsorted(range);
1777 } 1775 }
1778 } 1776 }
1779 SortUnhandled(); 1777 SortUnhandled();
1780 DCHECK(UnhandledIsSorted()); 1778 DCHECK(UnhandledIsSorted());
1781 1779
1782 auto& fixed_ranges = GetFixedRegisters(data(), mode()); 1780 auto& fixed_ranges = GetFixedRegisters(data(), mode());
1783 for (auto current : fixed_ranges) { 1781 for (auto current : fixed_ranges) {
1784 if (current != nullptr) { 1782 if (current != nullptr) {
1785 DCHECK_EQ(mode(), current->Kind()); 1783 DCHECK_EQ(mode(), current->kind());
1786 AddToInactive(current); 1784 AddToInactive(current);
1787 } 1785 }
1788 } 1786 }
1789 1787
1790 while (!unhandled_live_ranges().empty()) { 1788 while (!unhandled_live_ranges().empty()) {
1791 DCHECK(UnhandledIsSorted()); 1789 DCHECK(UnhandledIsSorted());
1792 auto current = unhandled_live_ranges().back(); 1790 auto current = unhandled_live_ranges().back();
1793 unhandled_live_ranges().pop_back(); 1791 unhandled_live_ranges().pop_back();
1794 DCHECK(UnhandledIsSorted()); 1792 DCHECK(UnhandledIsSorted());
1795 auto position = current->Start(); 1793 auto position = current->Start();
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after
1836 auto cur_inactive = inactive_live_ranges()[i]; 1834 auto cur_inactive = inactive_live_ranges()[i];
1837 if (cur_inactive->End() <= position) { 1835 if (cur_inactive->End() <= position) {
1838 InactiveToHandled(cur_inactive); 1836 InactiveToHandled(cur_inactive);
1839 --i; // Live range was removed from the list of inactive live ranges. 1837 --i; // Live range was removed from the list of inactive live ranges.
1840 } else if (cur_inactive->Covers(position)) { 1838 } else if (cur_inactive->Covers(position)) {
1841 InactiveToActive(cur_inactive); 1839 InactiveToActive(cur_inactive);
1842 --i; // Live range was removed from the list of inactive live ranges. 1840 --i; // Live range was removed from the list of inactive live ranges.
1843 } 1841 }
1844 } 1842 }
1845 1843
1846 DCHECK(!current->HasRegisterAssigned() && !current->IsSpilled()); 1844 DCHECK(!current->HasRegisterAssigned() && !current->spilled());
1847 1845
1848 bool result = TryAllocateFreeReg(current); 1846 bool result = TryAllocateFreeReg(current);
1849 if (!result) AllocateBlockedReg(current); 1847 if (!result) AllocateBlockedReg(current);
1850 if (current->HasRegisterAssigned()) { 1848 if (current->HasRegisterAssigned()) {
1851 AddToActive(current); 1849 AddToActive(current);
1852 } 1850 }
1853 } 1851 }
1854 } 1852 }
1855 1853
1856 1854
1857 const char* LinearScanAllocator::RegisterName(int allocation_index) const { 1855 const char* LinearScanAllocator::RegisterName(int allocation_index) const {
1858 if (mode() == GENERAL_REGISTERS) { 1856 if (mode() == GENERAL_REGISTERS) {
1859 return data()->config()->general_register_name(allocation_index); 1857 return data()->config()->general_register_name(allocation_index);
1860 } else { 1858 } else {
1861 return data()->config()->double_register_name(allocation_index); 1859 return data()->config()->double_register_name(allocation_index);
1862 } 1860 }
1863 } 1861 }
1864 1862
1865 1863
1866 void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range, 1864 void LinearScanAllocator::SetLiveRangeAssignedRegister(LiveRange* range,
1867 int reg) { 1865 int reg) {
1868 data()->MarkAllocated(range->Kind(), reg); 1866 data()->MarkAllocated(range->kind(), reg);
1869 range->set_assigned_register(reg); 1867 range->set_assigned_register(reg);
1870 range->SetUseHints(reg); 1868 range->SetUseHints(reg);
1871 if (range->is_phi()) { 1869 if (range->is_phi()) {
1872 data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg); 1870 data()->GetPhiMapValueFor(range->id())->set_assigned_register(reg);
1873 } 1871 }
1874 } 1872 }
1875 1873
1876 1874
1877 void LinearScanAllocator::AddToActive(LiveRange* range) { 1875 void LinearScanAllocator::AddToActive(LiveRange* range) {
1878 TRACE("Add live range %d to active\n", range->id()); 1876 TRACE("Add live range %d to active\n", range->id());
1879 active_live_ranges().push_back(range); 1877 active_live_ranges().push_back(range);
1880 } 1878 }
1881 1879
1882 1880
1883 void LinearScanAllocator::AddToInactive(LiveRange* range) { 1881 void LinearScanAllocator::AddToInactive(LiveRange* range) {
1884 TRACE("Add live range %d to inactive\n", range->id()); 1882 TRACE("Add live range %d to inactive\n", range->id());
1885 inactive_live_ranges().push_back(range); 1883 inactive_live_ranges().push_back(range);
1886 } 1884 }
1887 1885
1888 1886
1889 void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) { 1887 void LinearScanAllocator::AddToUnhandledSorted(LiveRange* range) {
1890 if (range == nullptr || range->IsEmpty()) return; 1888 if (range == nullptr || range->IsEmpty()) return;
1891 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1889 DCHECK(!range->HasRegisterAssigned() && !range->spilled());
1892 DCHECK(allocation_finger_ <= range->Start()); 1890 DCHECK(allocation_finger_ <= range->Start());
1893 for (int i = static_cast<int>(unhandled_live_ranges().size() - 1); i >= 0; 1891 for (int i = static_cast<int>(unhandled_live_ranges().size() - 1); i >= 0;
1894 --i) { 1892 --i) {
1895 auto cur_range = unhandled_live_ranges().at(i); 1893 auto cur_range = unhandled_live_ranges().at(i);
1896 if (!range->ShouldBeAllocatedBefore(cur_range)) continue; 1894 if (!range->ShouldBeAllocatedBefore(cur_range)) continue;
1897 TRACE("Add live range %d to unhandled at %d\n", range->id(), i + 1); 1895 TRACE("Add live range %d to unhandled at %d\n", range->id(), i + 1);
1898 auto it = unhandled_live_ranges().begin() + (i + 1); 1896 auto it = unhandled_live_ranges().begin() + (i + 1);
1899 unhandled_live_ranges().insert(it, range); 1897 unhandled_live_ranges().insert(it, range);
1900 DCHECK(UnhandledIsSorted()); 1898 DCHECK(UnhandledIsSorted());
1901 return; 1899 return;
1902 } 1900 }
1903 TRACE("Add live range %d to unhandled at start\n", range->id()); 1901 TRACE("Add live range %d to unhandled at start\n", range->id());
1904 unhandled_live_ranges().insert(unhandled_live_ranges().begin(), range); 1902 unhandled_live_ranges().insert(unhandled_live_ranges().begin(), range);
1905 DCHECK(UnhandledIsSorted()); 1903 DCHECK(UnhandledIsSorted());
1906 } 1904 }
1907 1905
1908 1906
1909 void LinearScanAllocator::AddToUnhandledUnsorted(LiveRange* range) { 1907 void LinearScanAllocator::AddToUnhandledUnsorted(LiveRange* range) {
1910 if (range == nullptr || range->IsEmpty()) return; 1908 if (range == nullptr || range->IsEmpty()) return;
1911 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 1909 DCHECK(!range->HasRegisterAssigned() && !range->spilled());
1912 TRACE("Add live range %d to unhandled unsorted at end\n", range->id()); 1910 TRACE("Add live range %d to unhandled unsorted at end\n", range->id());
1913 unhandled_live_ranges().push_back(range); 1911 unhandled_live_ranges().push_back(range);
1914 } 1912 }
1915 1913
1916 1914
1917 static bool UnhandledSortHelper(LiveRange* a, LiveRange* b) { 1915 static bool UnhandledSortHelper(LiveRange* a, LiveRange* b) {
1918 DCHECK(!a->ShouldBeAllocatedBefore(b) || !b->ShouldBeAllocatedBefore(a)); 1916 DCHECK(!a->ShouldBeAllocatedBefore(b) || !b->ShouldBeAllocatedBefore(a));
1919 if (a->ShouldBeAllocatedBefore(b)) return false; 1917 if (a->ShouldBeAllocatedBefore(b)) return false;
1920 if (b->ShouldBeAllocatedBefore(a)) return true; 1918 if (b->ShouldBeAllocatedBefore(a)) return true;
1921 return a->id() < b->id(); 1919 return a->id() < b->id();
(...skipping 257 matching lines...) Expand 10 before | Expand all | Expand 10 after
2179 for (size_t i = 0; i < phi->operands().size(); i++) { 2177 for (size_t i = 0; i < phi->operands().size(); i++) {
2180 int op = phi->operands()[i]; 2178 int op = phi->operands()[i];
2181 LiveRange* op_range = LiveRangeFor(op); 2179 LiveRange* op_range = LiveRangeFor(op);
2182 if (!op_range->HasSpillRange()) continue; 2180 if (!op_range->HasSpillRange()) continue;
2183 auto pred = code()->InstructionBlockAt(block->predecessors()[i]); 2181 auto pred = code()->InstructionBlockAt(block->predecessors()[i]);
2184 auto pred_end = LifetimePosition::InstructionFromInstructionIndex( 2182 auto pred_end = LifetimePosition::InstructionFromInstructionIndex(
2185 pred->last_instruction_index()); 2183 pred->last_instruction_index());
2186 while (op_range != nullptr && !op_range->CanCover(pred_end)) { 2184 while (op_range != nullptr && !op_range->CanCover(pred_end)) {
2187 op_range = op_range->next(); 2185 op_range = op_range->next();
2188 } 2186 }
2189 if (op_range != nullptr && op_range->IsSpilled()) { 2187 if (op_range != nullptr && op_range->spilled()) {
2190 spilled_count++; 2188 spilled_count++;
2191 if (first_op == nullptr) { 2189 if (first_op == nullptr) {
2192 first_op = op_range->TopLevel(); 2190 first_op = op_range->TopLevel();
2193 } 2191 }
2194 } 2192 }
2195 } 2193 }
2196 2194
2197 // Only continue if more than half of the operands are spilled. 2195 // Only continue if more than half of the operands are spilled.
2198 if (spilled_count * 2 <= phi->operands().size()) { 2196 if (spilled_count * 2 <= phi->operands().size()) {
2199 return false; 2197 return false;
(...skipping 353 matching lines...) Expand 10 before | Expand all | Expand 10 after
2553 } 2551 }
2554 return false; 2552 return false;
2555 // TODO(mtrofin): Do we need this? 2553 // TODO(mtrofin): Do we need this?
2556 // return (TryReuseSpillForPhi(range)); 2554 // return (TryReuseSpillForPhi(range));
2557 } 2555 }
2558 2556
2559 2557
2560 void GreedyAllocator::AllocateRegisters() { 2558 void GreedyAllocator::AllocateRegisters() {
2561 for (auto range : data()->live_ranges()) { 2559 for (auto range : data()->live_ranges()) {
2562 if (range == nullptr) continue; 2560 if (range == nullptr) continue;
2563 if (range->Kind() == mode()) { 2561 if (range->kind() == mode()) {
2564 DCHECK(!range->HasRegisterAssigned() && !range->IsSpilled()); 2562 DCHECK(!range->HasRegisterAssigned() && !range->spilled());
2565 TRACE("Enqueueing live range %d to priority queue \n", range->id()); 2563 TRACE("Enqueueing live range %d to priority queue \n", range->id());
2566 Enqueue(range); 2564 Enqueue(range);
2567 } 2565 }
2568 } 2566 }
2569 2567
2570 allocations_.resize(num_registers()); 2568 allocations_.resize(num_registers());
2571 auto* zone = data()->allocation_zone(); 2569 auto* zone = data()->allocation_zone();
2572 for (int i = 0; i < num_registers(); i++) { 2570 for (int i = 0; i < num_registers(); i++) {
2573 allocations_[i] = new (zone) CoallescedLiveRanges(zone); 2571 allocations_[i] = new (zone) CoallescedLiveRanges(zone);
2574 } 2572 }
2575 2573
2576 for (auto* current : GetFixedRegisters(data(), mode())) { 2574 for (auto* current : GetFixedRegisters(data(), mode())) {
2577 if (current != nullptr) { 2575 if (current != nullptr) {
2578 DCHECK_EQ(mode(), current->Kind()); 2576 DCHECK_EQ(mode(), current->kind());
2579 int reg_nr = current->assigned_register(); 2577 int reg_nr = current->assigned_register();
2580 bool inserted = allocations_[reg_nr]->Insert(current); 2578 bool inserted = allocations_[reg_nr]->Insert(current);
2581 CHECK(inserted); 2579 CHECK(inserted);
2582 } 2580 }
2583 } 2581 }
2584 2582
2585 while (!queue_.empty()) { 2583 while (!queue_.empty()) {
2586 auto current_pair = queue_.top(); 2584 auto current_pair = queue_.top();
2587 queue_.pop(); 2585 queue_.pop();
2588 auto current = current_pair.second; 2586 auto current = current_pair.second;
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after
2647 auto other = spill_ranges[j]; 2645 auto other = spill_ranges[j];
2648 if (!other->IsEmpty()) { 2646 if (!other->IsEmpty()) {
2649 range->TryMerge(other); 2647 range->TryMerge(other);
2650 } 2648 }
2651 } 2649 }
2652 } 2650 }
2653 // Allocate slots for the merged spill ranges. 2651 // Allocate slots for the merged spill ranges.
2654 for (auto range : spill_ranges) { 2652 for (auto range : spill_ranges) {
2655 if (range->IsEmpty()) continue; 2653 if (range->IsEmpty()) continue;
2656 // Allocate a new operand referring to the spill slot. 2654 // Allocate a new operand referring to the spill slot.
2657 auto kind = range->Kind(); 2655 auto kind = range->kind();
2658 int index = data()->frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS); 2656 int index = data()->frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS);
2659 auto op_kind = kind == DOUBLE_REGISTERS 2657 auto op_kind = kind == DOUBLE_REGISTERS
2660 ? AllocatedOperand::DOUBLE_STACK_SLOT 2658 ? AllocatedOperand::DOUBLE_STACK_SLOT
2661 : AllocatedOperand::STACK_SLOT; 2659 : AllocatedOperand::STACK_SLOT;
2662 auto op = AllocatedOperand::New(data()->code_zone(), op_kind, index); 2660 auto op = AllocatedOperand::New(data()->code_zone(), op_kind, index);
2663 range->SetOperand(op); 2661 range->SetOperand(op);
2664 } 2662 }
2665 } 2663 }
2666 2664
2667 2665
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after
2759 // Check if the live range is spilled and the safe point is after 2757 // Check if the live range is spilled and the safe point is after
2760 // the spill position. 2758 // the spill position.
2761 if (range->HasSpillOperand() && 2759 if (range->HasSpillOperand() &&
2762 safe_point >= range->spill_start_index() && 2760 safe_point >= range->spill_start_index() &&
2763 !range->GetSpillOperand()->IsConstant()) { 2761 !range->GetSpillOperand()->IsConstant()) {
2764 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n", 2762 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
2765 range->id(), range->spill_start_index(), safe_point); 2763 range->id(), range->spill_start_index(), safe_point);
2766 map->RecordReference(*range->GetSpillOperand()); 2764 map->RecordReference(*range->GetSpillOperand());
2767 } 2765 }
2768 2766
2769 if (!cur->IsSpilled()) { 2767 if (!cur->spilled()) {
2770 TRACE( 2768 TRACE(
2771 "Pointer in register for range %d (start at %d) " 2769 "Pointer in register for range %d (start at %d) "
2772 "at safe point %d\n", 2770 "at safe point %d\n",
2773 cur->id(), cur->Start().value(), safe_point); 2771 cur->id(), cur->Start().value(), safe_point);
2774 auto operand = cur->GetAssignedOperand(); 2772 auto operand = cur->GetAssignedOperand();
2775 DCHECK(!operand.IsStackSlot()); 2773 DCHECK(!operand.IsStackSlot());
2776 map->RecordReference(operand); 2774 map->RecordReference(operand);
2777 } 2775 }
2778 } 2776 }
2779 } 2777 }
(...skipping 153 matching lines...) Expand 10 before | Expand all | Expand 10 after
2933 if (CanEagerlyResolveControlFlow(block)) continue; 2931 if (CanEagerlyResolveControlFlow(block)) continue;
2934 auto live = live_in_sets[block->rpo_number().ToInt()]; 2932 auto live = live_in_sets[block->rpo_number().ToInt()];
2935 BitVector::Iterator iterator(live); 2933 BitVector::Iterator iterator(live);
2936 while (!iterator.Done()) { 2934 while (!iterator.Done()) {
2937 auto* array = finder.ArrayFor(iterator.Current()); 2935 auto* array = finder.ArrayFor(iterator.Current());
2938 for (auto pred : block->predecessors()) { 2936 for (auto pred : block->predecessors()) {
2939 FindResult result; 2937 FindResult result;
2940 const auto* pred_block = code()->InstructionBlockAt(pred); 2938 const auto* pred_block = code()->InstructionBlockAt(pred);
2941 array->Find(block, pred_block, &result); 2939 array->Find(block, pred_block, &result);
2942 if (result.cur_cover_ == result.pred_cover_ || 2940 if (result.cur_cover_ == result.pred_cover_ ||
2943 result.cur_cover_->IsSpilled()) 2941 result.cur_cover_->spilled())
2944 continue; 2942 continue;
2945 auto pred_op = result.pred_cover_->GetAssignedOperand(); 2943 auto pred_op = result.pred_cover_->GetAssignedOperand();
2946 auto cur_op = result.cur_cover_->GetAssignedOperand(); 2944 auto cur_op = result.cur_cover_->GetAssignedOperand();
2947 if (pred_op == cur_op) continue; 2945 if (pred_op == cur_op) continue;
2948 ResolveControlFlow(block, cur_op, pred_block, pred_op); 2946 ResolveControlFlow(block, cur_op, pred_block, pred_op);
2949 } 2947 }
2950 iterator.Advance(); 2948 iterator.Advance();
2951 } 2949 }
2952 } 2950 }
2953 } 2951 }
(...skipping 24 matching lines...) Expand all
2978 void LiveRangeConnector::ConnectRanges(Zone* local_zone) { 2976 void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
2979 ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand> 2977 ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand>
2980 delayed_insertion_map(local_zone); 2978 delayed_insertion_map(local_zone);
2981 for (auto first_range : data()->live_ranges()) { 2979 for (auto first_range : data()->live_ranges()) {
2982 if (first_range == nullptr || first_range->IsChild()) continue; 2980 if (first_range == nullptr || first_range->IsChild()) continue;
2983 for (auto second_range = first_range->next(); second_range != nullptr; 2981 for (auto second_range = first_range->next(); second_range != nullptr;
2984 first_range = second_range, second_range = second_range->next()) { 2982 first_range = second_range, second_range = second_range->next()) {
2985 auto pos = second_range->Start(); 2983 auto pos = second_range->Start();
2986 // Add gap move if the two live ranges touch and there is no block 2984 // Add gap move if the two live ranges touch and there is no block
2987 // boundary. 2985 // boundary.
2988 if (second_range->IsSpilled()) continue; 2986 if (second_range->spilled()) continue;
2989 if (first_range->End() != pos) continue; 2987 if (first_range->End() != pos) continue;
2990 if (IsBlockBoundary(code(), pos) && 2988 if (IsBlockBoundary(code(), pos) &&
2991 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) { 2989 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) {
2992 continue; 2990 continue;
2993 } 2991 }
2994 auto prev_operand = first_range->GetAssignedOperand(); 2992 auto prev_operand = first_range->GetAssignedOperand();
2995 auto cur_operand = second_range->GetAssignedOperand(); 2993 auto cur_operand = second_range->GetAssignedOperand();
2996 if (prev_operand == cur_operand) continue; 2994 if (prev_operand == cur_operand) continue;
2997 bool delay_insertion = false; 2995 bool delay_insertion = false;
2998 Instruction::GapPosition gap_pos; 2996 Instruction::GapPosition gap_pos;
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
3045 auto eliminate = moves->PrepareInsertAfter(move); 3043 auto eliminate = moves->PrepareInsertAfter(move);
3046 to_insert.push_back(move); 3044 to_insert.push_back(move);
3047 if (eliminate != nullptr) to_eliminate.push_back(eliminate); 3045 if (eliminate != nullptr) to_eliminate.push_back(eliminate);
3048 } 3046 }
3049 } 3047 }
3050 3048
3051 3049
3052 } // namespace compiler 3050 } // namespace compiler
3053 } // namespace internal 3051 } // namespace internal
3054 } // namespace v8 3052 } // namespace v8
OLDNEW
« no previous file with comments | « src/compiler/register-allocator.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698