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

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

Issue 1087793002: [turbofan] add MachineType to AllocatedOperand (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: no flag Created 5 years, 7 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') | src/compiler/register-allocator-verifier.cc » ('j') | 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 71 matching lines...) Expand 10 before | Expand all | Expand 10 after
82 for (size_t i = 0; i < instr->OutputCount(); i++) { 82 for (size_t i = 0; i < instr->OutputCount(); i++) {
83 auto output = instr->OutputAt(i); 83 auto output = instr->OutputAt(i);
84 if (output->IsDoubleRegister() && 84 if (output->IsDoubleRegister() &&
85 DoubleRegisterOperand::cast(output)->index() == index) { 85 DoubleRegisterOperand::cast(output)->index() == index) {
86 return true; 86 return true;
87 } 87 }
88 } 88 }
89 return false; 89 return false;
90 } 90 }
91 91
92
93 // TODO(dcarney): fix frame to allow frame accesses to half size location.
94 int GetByteWidth(MachineType machine_type) {
95 DCHECK_EQ(RepresentationOf(machine_type), machine_type);
96 switch (machine_type) {
97 case kRepBit:
98 case kRepWord8:
99 case kRepWord16:
100 case kRepWord32:
101 case kRepTagged:
102 return kPointerSize;
103 case kRepFloat32:
104 case kRepWord64:
105 case kRepFloat64:
106 return 8;
107 default:
108 UNREACHABLE();
109 return 0;
110 }
111 }
112
92 } // namespace 113 } // namespace
93 114
94 115
95 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand, 116 UsePosition::UsePosition(LifetimePosition pos, InstructionOperand* operand,
96 void* hint, UsePositionHintType hint_type) 117 void* hint, UsePositionHintType hint_type)
97 : operand_(operand), hint_(hint), next_(nullptr), pos_(pos), flags_(0) { 118 : operand_(operand), hint_(hint), next_(nullptr), pos_(pos), flags_(0) {
98 DCHECK_IMPLIES(hint == nullptr, hint_type == UsePositionHintType::kNone); 119 DCHECK_IMPLIES(hint == nullptr, hint_type == UsePositionHintType::kNone);
99 bool register_beneficial = true; 120 bool register_beneficial = true;
100 UsePositionType type = UsePositionType::kAny; 121 UsePositionType type = UsePositionType::kAny;
101 if (operand_ != nullptr && operand_->IsUnallocated()) { 122 if (operand_ != nullptr && operand_->IsUnallocated()) {
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after
207 struct LiveRange::SpillAtDefinitionList : ZoneObject { 228 struct LiveRange::SpillAtDefinitionList : ZoneObject {
208 SpillAtDefinitionList(int gap_index, InstructionOperand* operand, 229 SpillAtDefinitionList(int gap_index, InstructionOperand* operand,
209 SpillAtDefinitionList* next) 230 SpillAtDefinitionList* next)
210 : gap_index(gap_index), operand(operand), next(next) {} 231 : gap_index(gap_index), operand(operand), next(next) {}
211 const int gap_index; 232 const int gap_index;
212 InstructionOperand* const operand; 233 InstructionOperand* const operand;
213 SpillAtDefinitionList* const next; 234 SpillAtDefinitionList* const next;
214 }; 235 };
215 236
216 237
217 LiveRange::LiveRange(int id) 238 LiveRange::LiveRange(int id, MachineType machine_type)
218 : id_(id), 239 : id_(id),
219 spill_start_index_(kMaxInt), 240 spill_start_index_(kMaxInt),
220 bits_(0), 241 bits_(0),
221 last_interval_(nullptr), 242 last_interval_(nullptr),
222 first_interval_(nullptr), 243 first_interval_(nullptr),
223 first_pos_(nullptr), 244 first_pos_(nullptr),
224 parent_(nullptr), 245 parent_(nullptr),
225 next_(nullptr), 246 next_(nullptr),
226 spill_operand_(nullptr), 247 spill_operand_(nullptr),
227 spills_at_definition_(nullptr), 248 spills_at_definition_(nullptr),
228 current_interval_(nullptr), 249 current_interval_(nullptr),
229 last_processed_use_(nullptr), 250 last_processed_use_(nullptr),
230 current_hint_position_(nullptr) { 251 current_hint_position_(nullptr) {
252 DCHECK(AllocatedOperand::IsSupportedMachineType(machine_type));
231 bits_ = SpillTypeField::encode(SpillType::kNoSpillType) | 253 bits_ = SpillTypeField::encode(SpillType::kNoSpillType) |
232 AssignedRegisterField::encode(kUnassignedRegister); 254 AssignedRegisterField::encode(kUnassignedRegister) |
255 MachineTypeField::encode(machine_type);
233 } 256 }
234 257
235 258
236 void LiveRange::Verify() const { 259 void LiveRange::Verify() const {
237 // Walk the positions, verifying that each is in an interval. 260 // Walk the positions, verifying that each is in an interval.
238 auto interval = first_interval_; 261 auto interval = first_interval_;
239 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { 262 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
240 CHECK(Start() <= pos->pos()); 263 CHECK(Start() <= pos->pos());
241 CHECK(pos->pos() <= End()); 264 CHECK(pos->pos() <= End());
242 CHECK(interval != nullptr); 265 CHECK(interval != nullptr);
(...skipping 18 matching lines...) Expand all
261 284
262 285
263 void LiveRange::Spill() { 286 void LiveRange::Spill() {
264 DCHECK(!spilled()); 287 DCHECK(!spilled());
265 DCHECK(!TopLevel()->HasNoSpillType()); 288 DCHECK(!TopLevel()->HasNoSpillType());
266 set_spilled(true); 289 set_spilled(true);
267 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister); 290 bits_ = AssignedRegisterField::update(bits_, kUnassignedRegister);
268 } 291 }
269 292
270 293
294 RegisterKind LiveRange::kind() const {
295 switch (RepresentationOf(machine_type())) {
296 case kRepFloat32:
297 case kRepFloat64:
298 return DOUBLE_REGISTERS;
299 default:
300 break;
301 }
302 return GENERAL_REGISTERS;
303 }
304
305
271 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index, 306 void LiveRange::SpillAtDefinition(Zone* zone, int gap_index,
272 InstructionOperand* operand) { 307 InstructionOperand* operand) {
273 DCHECK(HasNoSpillType()); 308 DCHECK(HasNoSpillType());
274 spills_at_definition_ = new (zone) 309 spills_at_definition_ = new (zone)
275 SpillAtDefinitionList(gap_index, operand, spills_at_definition_); 310 SpillAtDefinitionList(gap_index, operand, spills_at_definition_);
276 } 311 }
277 312
278 313
279 void LiveRange::CommitSpillsAtDefinition(InstructionSequence* sequence, 314 void LiveRange::CommitSpillsAtDefinition(InstructionSequence* sequence,
280 InstructionOperand* op, 315 const InstructionOperand& op,
281 bool might_be_duplicated) { 316 bool might_be_duplicated) {
282 DCHECK_IMPLIES(op->IsConstant(), spills_at_definition_ == nullptr); 317 DCHECK_IMPLIES(op.IsConstant(), spills_at_definition_ == nullptr);
283 DCHECK(!IsChild()); 318 DCHECK(!IsChild());
284 auto zone = sequence->zone(); 319 auto zone = sequence->zone();
285 for (auto to_spill = spills_at_definition_; to_spill != nullptr; 320 for (auto to_spill = spills_at_definition_; to_spill != nullptr;
286 to_spill = to_spill->next) { 321 to_spill = to_spill->next) {
287 auto instr = sequence->InstructionAt(to_spill->gap_index); 322 auto instr = sequence->InstructionAt(to_spill->gap_index);
288 auto move = instr->GetOrCreateParallelMove(Instruction::START, zone); 323 auto move = instr->GetOrCreateParallelMove(Instruction::START, zone);
289 // Skip insertion if it's possible that the move exists already as a 324 // Skip insertion if it's possible that the move exists already as a
290 // constraint move from a fixed output register to a slot. 325 // constraint move from a fixed output register to a slot.
291 if (might_be_duplicated) { 326 if (might_be_duplicated) {
292 bool found = false; 327 bool found = false;
293 for (auto move_op : *move) { 328 for (auto move_op : *move) {
294 if (move_op->IsEliminated()) continue; 329 if (move_op->IsEliminated()) continue;
295 if (move_op->source() == *to_spill->operand && 330 if (move_op->source().Equals(*to_spill->operand) &&
296 move_op->destination() == *op) { 331 move_op->destination().Equals(op)) {
297 found = true; 332 found = true;
298 break; 333 break;
299 } 334 }
300 } 335 }
301 if (found) continue; 336 if (found) continue;
302 } 337 }
303 move->AddMove(*to_spill->operand, *op); 338 move->AddMove(*to_spill->operand, op);
304 } 339 }
305 } 340 }
306 341
307 342
308 UsePosition* LiveRange::FirstHintPosition(int* register_index) const { 343 UsePosition* LiveRange::FirstHintPosition(int* register_index) const {
309 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) { 344 for (auto pos = first_pos_; pos != nullptr; pos = pos->next()) {
310 if (pos->HintRegister(register_index)) return pos; 345 if (pos->HintRegister(register_index)) return pos;
311 } 346 }
312 return nullptr; 347 return nullptr;
313 } 348 }
314 349
315 350
316 void LiveRange::SetSpillOperand(InstructionOperand* operand) { 351 void LiveRange::SetSpillOperand(InstructionOperand* operand) {
317 DCHECK(HasNoSpillType()); 352 DCHECK(HasNoSpillType());
318 DCHECK(!operand->IsUnallocated() && !operand->IsImmediate()); 353 DCHECK(!operand->IsUnallocated() && !operand->IsImmediate());
319 set_spill_type(SpillType::kSpillOperand); 354 set_spill_type(SpillType::kSpillOperand);
320 spill_operand_ = operand; 355 spill_operand_ = operand;
321 } 356 }
322 357
323 358
324 void LiveRange::SetSpillRange(SpillRange* spill_range) { 359 void LiveRange::SetSpillRange(SpillRange* spill_range) {
325 DCHECK(HasNoSpillType() || HasSpillRange()); 360 DCHECK(HasNoSpillType() || HasSpillRange());
326 DCHECK(spill_range); 361 DCHECK(spill_range);
327 set_spill_type(SpillType::kSpillRange); 362 set_spill_type(SpillType::kSpillRange);
328 spill_range_ = spill_range; 363 spill_range_ = spill_range;
329 } 364 }
330 365
331 366
332 void LiveRange::CommitSpillOperand(AllocatedOperand* operand) {
333 DCHECK(HasSpillRange());
334 DCHECK(!IsChild());
335 set_spill_type(SpillType::kSpillOperand);
336 spill_operand_ = operand;
337 }
338
339
340 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const { 367 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) const {
341 UsePosition* use_pos = last_processed_use_; 368 UsePosition* use_pos = last_processed_use_;
342 if (use_pos == nullptr || use_pos->pos() > start) { 369 if (use_pos == nullptr || use_pos->pos() > start) {
343 use_pos = first_pos(); 370 use_pos = first_pos();
344 } 371 }
345 while (use_pos != nullptr && use_pos->pos() < start) { 372 while (use_pos != nullptr && use_pos->pos() < start) {
346 use_pos = use_pos->next(); 373 use_pos = use_pos->next();
347 } 374 }
348 last_processed_use_ = use_pos; 375 last_processed_use_ = use_pos;
349 return use_pos; 376 return use_pos;
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
388 if (use_pos == nullptr) return true; 415 if (use_pos == nullptr) return true;
389 return use_pos->pos() > pos.NextStart().End(); 416 return use_pos->pos() > pos.NextStart().End();
390 } 417 }
391 418
392 419
393 InstructionOperand LiveRange::GetAssignedOperand() const { 420 InstructionOperand LiveRange::GetAssignedOperand() const {
394 if (HasRegisterAssigned()) { 421 if (HasRegisterAssigned()) {
395 DCHECK(!spilled()); 422 DCHECK(!spilled());
396 switch (kind()) { 423 switch (kind()) {
397 case GENERAL_REGISTERS: 424 case GENERAL_REGISTERS:
398 return RegisterOperand(assigned_register()); 425 return RegisterOperand(machine_type(), assigned_register());
399 case DOUBLE_REGISTERS: 426 case DOUBLE_REGISTERS:
400 return DoubleRegisterOperand(assigned_register()); 427 return DoubleRegisterOperand(machine_type(), assigned_register());
401 default:
402 UNREACHABLE();
403 } 428 }
404 } 429 }
405 DCHECK(spilled()); 430 DCHECK(spilled());
406 DCHECK(!HasRegisterAssigned()); 431 DCHECK(!HasRegisterAssigned());
407 auto op = TopLevel()->GetSpillOperand(); 432 if (TopLevel()->HasSpillOperand()) {
408 DCHECK(!op->IsUnallocated()); 433 auto op = TopLevel()->GetSpillOperand();
409 return *op; 434 DCHECK(!op->IsUnallocated());
435 return *op;
436 }
437 return TopLevel()->GetSpillRangeOperand();
410 } 438 }
411 439
412 440
441 AllocatedOperand LiveRange::GetSpillRangeOperand() const {
442 auto spill_range = GetSpillRange();
443 int index = spill_range->assigned_slot();
444 switch (kind()) {
445 case GENERAL_REGISTERS:
446 return StackSlotOperand(machine_type(), index);
447 case DOUBLE_REGISTERS:
448 return DoubleStackSlotOperand(machine_type(), index);
449 }
450 UNREACHABLE();
451 return StackSlotOperand(kMachNone, 0);
452 }
453
454
413 UseInterval* LiveRange::FirstSearchIntervalForPosition( 455 UseInterval* LiveRange::FirstSearchIntervalForPosition(
414 LifetimePosition position) const { 456 LifetimePosition position) const {
415 if (current_interval_ == nullptr) return first_interval_; 457 if (current_interval_ == nullptr) return first_interval_;
416 if (current_interval_->start() > position) { 458 if (current_interval_->start() > position) {
417 current_interval_ = nullptr; 459 current_interval_ = nullptr;
418 return first_interval_; 460 return first_interval_;
419 } 461 }
420 return current_interval_; 462 return current_interval_;
421 } 463 }
422 464
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after
505 result->first_pos_ = use_after; 547 result->first_pos_ = use_after;
506 548
507 // Discard cached iteration state. It might be pointing 549 // Discard cached iteration state. It might be pointing
508 // to the use that no longer belongs to this live range. 550 // to the use that no longer belongs to this live range.
509 last_processed_use_ = nullptr; 551 last_processed_use_ = nullptr;
510 current_interval_ = nullptr; 552 current_interval_ = nullptr;
511 553
512 // Link the new live range in the chain before any of the other 554 // Link the new live range in the chain before any of the other
513 // ranges linked from the range before the split. 555 // ranges linked from the range before the split.
514 result->parent_ = (parent_ == nullptr) ? this : parent_; 556 result->parent_ = (parent_ == nullptr) ? this : parent_;
515 result->set_kind(result->parent_->kind());
516 result->next_ = next_; 557 result->next_ = next_;
517 next_ = result; 558 next_ = result;
518 559
519 #ifdef DEBUG 560 #ifdef DEBUG
520 Verify(); 561 Verify();
521 result->Verify(); 562 result->Verify();
522 #endif 563 #endif
523 } 564 }
524 565
525 566
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after
619 prev->set_next(use_pos); 660 prev->set_next(use_pos);
620 } 661 }
621 662
622 if (prev_hint == nullptr && use_pos->HasHint()) { 663 if (prev_hint == nullptr && use_pos->HasHint()) {
623 current_hint_position_ = use_pos; 664 current_hint_position_ = use_pos;
624 } 665 }
625 } 666 }
626 667
627 668
628 void LiveRange::ConvertUsesToOperand(const InstructionOperand& op, 669 void LiveRange::ConvertUsesToOperand(const InstructionOperand& op,
629 InstructionOperand* spill_op) { 670 const InstructionOperand& spill_op) {
630 for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) { 671 for (auto pos = first_pos(); pos != nullptr; pos = pos->next()) {
631 DCHECK(Start() <= pos->pos() && pos->pos() <= End()); 672 DCHECK(Start() <= pos->pos() && pos->pos() <= End());
632 if (!pos->HasOperand()) continue; 673 if (!pos->HasOperand()) continue;
633 switch (pos->type()) { 674 switch (pos->type()) {
634 case UsePositionType::kRequiresSlot: 675 case UsePositionType::kRequiresSlot:
635 if (spill_op != nullptr) { 676 DCHECK(spill_op.IsStackSlot() || spill_op.IsDoubleStackSlot());
636 InstructionOperand::ReplaceWith(pos->operand(), spill_op); 677 InstructionOperand::ReplaceWith(pos->operand(), &spill_op);
637 }
638 break; 678 break;
639 case UsePositionType::kRequiresRegister: 679 case UsePositionType::kRequiresRegister:
640 DCHECK(op.IsRegister() || op.IsDoubleRegister()); 680 DCHECK(op.IsRegister() || op.IsDoubleRegister());
641 // Fall through. 681 // Fall through.
642 case UsePositionType::kAny: 682 case UsePositionType::kAny:
643 InstructionOperand::ReplaceWith(pos->operand(), &op); 683 InstructionOperand::ReplaceWith(pos->operand(), &op);
644 break; 684 break;
645 } 685 }
646 } 686 }
647 } 687 }
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after
719 if (interval2->end() > interval1->start()) { 759 if (interval2->end() > interval1->start()) {
720 return true; 760 return true;
721 } 761 }
722 interval2 = interval2->next(); 762 interval2 = interval2->next();
723 } 763 }
724 } 764 }
725 return false; 765 return false;
726 } 766 }
727 767
728 768
729 SpillRange::SpillRange(LiveRange* parent, Zone* zone) : live_ranges_(zone) { 769 SpillRange::SpillRange(LiveRange* parent, Zone* zone)
770 : live_ranges_(zone), assigned_slot_(kUnassignedSlot) {
730 DCHECK(!parent->IsChild()); 771 DCHECK(!parent->IsChild());
731 UseInterval* result = nullptr; 772 UseInterval* result = nullptr;
732 UseInterval* node = nullptr; 773 UseInterval* node = nullptr;
733 // Copy the intervals for all ranges. 774 // Copy the intervals for all ranges.
734 for (auto range = parent; range != nullptr; range = range->next()) { 775 for (auto range = parent; range != nullptr; range = range->next()) {
735 auto src = range->first_interval(); 776 auto src = range->first_interval();
736 while (src != nullptr) { 777 while (src != nullptr) {
737 auto new_node = new (zone) UseInterval(src->start(), src->end()); 778 auto new_node = new (zone) UseInterval(src->start(), src->end());
738 if (result == nullptr) { 779 if (result == nullptr) {
739 result = new_node; 780 result = new_node;
740 } else { 781 } else {
741 node->set_next(new_node); 782 node->set_next(new_node);
742 } 783 }
743 node = new_node; 784 node = new_node;
744 src = src->next(); 785 src = src->next();
745 } 786 }
746 } 787 }
747 use_interval_ = result; 788 use_interval_ = result;
748 live_ranges().push_back(parent); 789 live_ranges().push_back(parent);
749 end_position_ = node->end(); 790 end_position_ = node->end();
750 DCHECK(!parent->HasSpillRange()); 791 DCHECK(!parent->HasSpillRange());
751 parent->SetSpillRange(this); 792 parent->SetSpillRange(this);
752 } 793 }
753 794
754 795
796 int SpillRange::ByteWidth() const {
797 return GetByteWidth(live_ranges_[0]->machine_type());
798 }
799
800
755 bool SpillRange::IsIntersectingWith(SpillRange* other) const { 801 bool SpillRange::IsIntersectingWith(SpillRange* other) const {
756 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr || 802 if (this->use_interval_ == nullptr || other->use_interval_ == nullptr ||
757 this->End() <= other->use_interval_->start() || 803 this->End() <= other->use_interval_->start() ||
758 other->End() <= this->use_interval_->start()) { 804 other->End() <= this->use_interval_->start()) {
759 return false; 805 return false;
760 } 806 }
761 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_); 807 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_);
762 } 808 }
763 809
764 810
765 bool SpillRange::TryMerge(SpillRange* other) { 811 bool SpillRange::TryMerge(SpillRange* other) {
766 if (kind() != other->kind() || IsIntersectingWith(other)) return false; 812 // TODO(dcarney): byte widths should be compared here not kinds.
813 if (live_ranges_[0]->kind() != other->live_ranges_[0]->kind() ||
814 IsIntersectingWith(other)) {
815 return false;
816 }
767 817
768 auto max = LifetimePosition::MaxPosition(); 818 auto max = LifetimePosition::MaxPosition();
769 if (End() < other->End() && other->End() != max) { 819 if (End() < other->End() && other->End() != max) {
770 end_position_ = other->End(); 820 end_position_ = other->End();
771 } 821 }
772 other->end_position_ = max; 822 other->end_position_ = max;
773 823
774 MergeDisjointIntervals(other->use_interval_); 824 MergeDisjointIntervals(other->use_interval_);
775 other->use_interval_ = nullptr; 825 other->use_interval_ = nullptr;
776 826
777 for (auto range : other->live_ranges()) { 827 for (auto range : other->live_ranges()) {
778 DCHECK(range->GetSpillRange() == other); 828 DCHECK(range->GetSpillRange() == other);
779 range->SetSpillRange(this); 829 range->SetSpillRange(this);
780 } 830 }
781 831
782 live_ranges().insert(live_ranges().end(), other->live_ranges().begin(), 832 live_ranges().insert(live_ranges().end(), other->live_ranges().begin(),
783 other->live_ranges().end()); 833 other->live_ranges().end());
784 other->live_ranges().clear(); 834 other->live_ranges().clear();
785 835
786 return true; 836 return true;
787 } 837 }
788 838
789 839
790 void SpillRange::SetOperand(AllocatedOperand* op) {
791 for (auto range : live_ranges()) {
792 DCHECK(range->GetSpillRange() == this);
793 range->CommitSpillOperand(op);
794 }
795 }
796
797
798 void SpillRange::MergeDisjointIntervals(UseInterval* other) { 840 void SpillRange::MergeDisjointIntervals(UseInterval* other) {
799 UseInterval* tail = nullptr; 841 UseInterval* tail = nullptr;
800 auto current = use_interval_; 842 auto current = use_interval_;
801 while (other != nullptr) { 843 while (other != nullptr) {
802 // Make sure the 'current' list starts first 844 // Make sure the 'current' list starts first
803 if (current == nullptr || current->start() > other->start()) { 845 if (current == nullptr || current->start() > other->start()) {
804 std::swap(current, other); 846 std::swap(current, other);
805 } 847 }
806 // Check disjointness 848 // Check disjointness
807 DCHECK(other == nullptr || current->end() <= other->start()); 849 DCHECK(other == nullptr || current->end() <= other->start());
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
854 phi_map_(allocation_zone()), 896 phi_map_(allocation_zone()),
855 live_in_sets_(code->InstructionBlockCount(), nullptr, allocation_zone()), 897 live_in_sets_(code->InstructionBlockCount(), nullptr, allocation_zone()),
856 live_ranges_(code->VirtualRegisterCount() * 2, nullptr, 898 live_ranges_(code->VirtualRegisterCount() * 2, nullptr,
857 allocation_zone()), 899 allocation_zone()),
858 fixed_live_ranges_(this->config()->num_general_registers(), nullptr, 900 fixed_live_ranges_(this->config()->num_general_registers(), nullptr,
859 allocation_zone()), 901 allocation_zone()),
860 fixed_double_live_ranges_(this->config()->num_double_registers(), nullptr, 902 fixed_double_live_ranges_(this->config()->num_double_registers(), nullptr,
861 allocation_zone()), 903 allocation_zone()),
862 spill_ranges_(allocation_zone()), 904 spill_ranges_(allocation_zone()),
863 assigned_registers_(nullptr), 905 assigned_registers_(nullptr),
864 assigned_double_registers_(nullptr) { 906 assigned_double_registers_(nullptr),
907 virtual_register_count_(code->VirtualRegisterCount()) {
865 DCHECK(this->config()->num_general_registers() <= 908 DCHECK(this->config()->num_general_registers() <=
866 RegisterConfiguration::kMaxGeneralRegisters); 909 RegisterConfiguration::kMaxGeneralRegisters);
867 DCHECK(this->config()->num_double_registers() <= 910 DCHECK(this->config()->num_double_registers() <=
868 RegisterConfiguration::kMaxDoubleRegisters); 911 RegisterConfiguration::kMaxDoubleRegisters);
869 spill_ranges().reserve(8); 912 spill_ranges().reserve(8);
870 assigned_registers_ = new (code_zone()) 913 assigned_registers_ = new (code_zone())
871 BitVector(this->config()->num_general_registers(), code_zone()); 914 BitVector(this->config()->num_general_registers(), code_zone());
872 assigned_double_registers_ = new (code_zone()) 915 assigned_double_registers_ = new (code_zone())
873 BitVector(this->config()->num_aliased_double_registers(), code_zone()); 916 BitVector(this->config()->num_aliased_double_registers(), code_zone());
874 this->frame()->SetAllocatedRegisters(assigned_registers_); 917 this->frame()->SetAllocatedRegisters(assigned_registers_);
875 this->frame()->SetAllocatedDoubleRegisters(assigned_double_registers_); 918 this->frame()->SetAllocatedDoubleRegisters(assigned_double_registers_);
876 } 919 }
877 920
878 921
879 LiveRange* RegisterAllocationData::LiveRangeFor(int index) {
880 if (index >= static_cast<int>(live_ranges().size())) {
881 live_ranges().resize(index + 1, nullptr);
882 }
883 auto result = live_ranges()[index];
884 if (result == nullptr) {
885 result = NewLiveRange(index);
886 live_ranges()[index] = result;
887 }
888 return result;
889 }
890
891
892 MoveOperands* RegisterAllocationData::AddGapMove( 922 MoveOperands* RegisterAllocationData::AddGapMove(
893 int index, Instruction::GapPosition position, 923 int index, Instruction::GapPosition position,
894 const InstructionOperand& from, const InstructionOperand& to) { 924 const InstructionOperand& from, const InstructionOperand& to) {
895 auto instr = code()->InstructionAt(index); 925 auto instr = code()->InstructionAt(index);
896 auto moves = instr->GetOrCreateParallelMove(position, code_zone()); 926 auto moves = instr->GetOrCreateParallelMove(position, code_zone());
897 return moves->AddMove(from, to); 927 return moves->AddMove(from, to);
898 } 928 }
899 929
900 930
901 LiveRange* RegisterAllocationData::NewLiveRange(int index) { 931 MachineType RegisterAllocationData::MachineTypeFor(int virtual_register) {
902 return new (allocation_zone()) LiveRange(index); 932 DCHECK_LT(virtual_register, code()->VirtualRegisterCount());
933 return code()->GetRepresentation(virtual_register);
903 } 934 }
904 935
905 936
937 LiveRange* RegisterAllocationData::LiveRangeFor(int index) {
938 if (index >= static_cast<int>(live_ranges().size())) {
939 live_ranges().resize(index + 1, nullptr);
940 }
941 auto result = live_ranges()[index];
942 if (result == nullptr) {
943 result = NewLiveRange(index, MachineTypeFor(index));
944 live_ranges()[index] = result;
945 }
946 return result;
947 }
948
949
950 LiveRange* RegisterAllocationData::NewLiveRange(int index,
951 MachineType machine_type) {
952 return new (allocation_zone()) LiveRange(index, machine_type);
953 }
954
955
956 LiveRange* RegisterAllocationData::NewChildRangeFor(LiveRange* range) {
957 int vreg = virtual_register_count_++;
958 if (vreg >= static_cast<int>(live_ranges().size())) {
959 live_ranges().resize(vreg + 1, nullptr);
960 }
961 auto child = new (allocation_zone()) LiveRange(vreg, range->machine_type());
962 DCHECK_NULL(live_ranges()[vreg]);
963 live_ranges()[vreg] = child;
964 return child;
965 }
966
967
906 RegisterAllocationData::PhiMapValue* RegisterAllocationData::InitializePhiMap( 968 RegisterAllocationData::PhiMapValue* RegisterAllocationData::InitializePhiMap(
907 const InstructionBlock* block, PhiInstruction* phi) { 969 const InstructionBlock* block, PhiInstruction* phi) {
908 auto map_value = new (allocation_zone()) 970 auto map_value = new (allocation_zone())
909 RegisterAllocationData::PhiMapValue(phi, block, allocation_zone()); 971 RegisterAllocationData::PhiMapValue(phi, block, allocation_zone());
910 auto res = 972 auto res =
911 phi_map_.insert(std::make_pair(phi->virtual_register(), map_value)); 973 phi_map_.insert(std::make_pair(phi->virtual_register(), map_value));
912 DCHECK(res.second); 974 DCHECK(res.second);
913 USE(res); 975 USE(res);
914 return map_value; 976 return map_value;
915 } 977 }
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after
965 1027
966 ConstraintBuilder::ConstraintBuilder(RegisterAllocationData* data) 1028 ConstraintBuilder::ConstraintBuilder(RegisterAllocationData* data)
967 : data_(data) {} 1029 : data_(data) {}
968 1030
969 1031
970 InstructionOperand* ConstraintBuilder::AllocateFixed( 1032 InstructionOperand* ConstraintBuilder::AllocateFixed(
971 UnallocatedOperand* operand, int pos, bool is_tagged) { 1033 UnallocatedOperand* operand, int pos, bool is_tagged) {
972 TRACE("Allocating fixed reg for op %d\n", operand->virtual_register()); 1034 TRACE("Allocating fixed reg for op %d\n", operand->virtual_register());
973 DCHECK(operand->HasFixedPolicy()); 1035 DCHECK(operand->HasFixedPolicy());
974 InstructionOperand allocated; 1036 InstructionOperand allocated;
1037 MachineType machine_type = InstructionSequence::DefaultRepresentation();
1038 int virtual_register = operand->virtual_register();
1039 if (virtual_register != InstructionOperand::kInvalidVirtualRegister) {
1040 machine_type = data()->MachineTypeFor(virtual_register);
1041 }
975 if (operand->HasFixedSlotPolicy()) { 1042 if (operand->HasFixedSlotPolicy()) {
976 allocated = AllocatedOperand(AllocatedOperand::STACK_SLOT, 1043 allocated = AllocatedOperand(AllocatedOperand::STACK_SLOT, machine_type,
977 operand->fixed_slot_index()); 1044 operand->fixed_slot_index());
978 } else if (operand->HasFixedRegisterPolicy()) { 1045 } else if (operand->HasFixedRegisterPolicy()) {
979 allocated = AllocatedOperand(AllocatedOperand::REGISTER, 1046 allocated = AllocatedOperand(AllocatedOperand::REGISTER, machine_type,
980 operand->fixed_register_index()); 1047 operand->fixed_register_index());
981 } else if (operand->HasFixedDoubleRegisterPolicy()) { 1048 } else if (operand->HasFixedDoubleRegisterPolicy()) {
1049 DCHECK_NE(InstructionOperand::kInvalidVirtualRegister, virtual_register);
982 allocated = AllocatedOperand(AllocatedOperand::DOUBLE_REGISTER, 1050 allocated = AllocatedOperand(AllocatedOperand::DOUBLE_REGISTER,
983 operand->fixed_register_index()); 1051 machine_type, operand->fixed_register_index());
984 } else { 1052 } else {
985 UNREACHABLE(); 1053 UNREACHABLE();
986 } 1054 }
987 InstructionOperand::ReplaceWith(operand, &allocated); 1055 InstructionOperand::ReplaceWith(operand, &allocated);
988 if (is_tagged) { 1056 if (is_tagged) {
989 TRACE("Fixed reg is tagged at %d\n", pos); 1057 TRACE("Fixed reg is tagged at %d\n", pos);
990 auto instr = InstructionAt(pos); 1058 auto instr = InstructionAt(pos);
991 if (instr->HasReferenceMap()) { 1059 if (instr->HasReferenceMap()) {
992 instr->reference_map()->RecordReference(*operand); 1060 instr->reference_map()->RecordReference(*operand);
993 } 1061 }
(...skipping 247 matching lines...) Expand 10 before | Expand all | Expand 10 after
1241 1309
1242 int LiveRangeBuilder::FixedDoubleLiveRangeID(int index) { 1310 int LiveRangeBuilder::FixedDoubleLiveRangeID(int index) {
1243 return -index - 1 - config()->num_general_registers(); 1311 return -index - 1 - config()->num_general_registers();
1244 } 1312 }
1245 1313
1246 1314
1247 LiveRange* LiveRangeBuilder::FixedLiveRangeFor(int index) { 1315 LiveRange* LiveRangeBuilder::FixedLiveRangeFor(int index) {
1248 DCHECK(index < config()->num_general_registers()); 1316 DCHECK(index < config()->num_general_registers());
1249 auto result = data()->fixed_live_ranges()[index]; 1317 auto result = data()->fixed_live_ranges()[index];
1250 if (result == nullptr) { 1318 if (result == nullptr) {
1251 result = data()->NewLiveRange(FixedLiveRangeID(index)); 1319 result = data()->NewLiveRange(FixedLiveRangeID(index),
1320 InstructionSequence::DefaultRepresentation());
1252 DCHECK(result->IsFixed()); 1321 DCHECK(result->IsFixed());
1253 result->set_kind(GENERAL_REGISTERS);
1254 result->set_assigned_register(index); 1322 result->set_assigned_register(index);
1255 data()->MarkAllocated(GENERAL_REGISTERS, index); 1323 data()->MarkAllocated(GENERAL_REGISTERS, index);
1256 data()->fixed_live_ranges()[index] = result; 1324 data()->fixed_live_ranges()[index] = result;
1257 } 1325 }
1258 return result; 1326 return result;
1259 } 1327 }
1260 1328
1261 1329
1262 LiveRange* LiveRangeBuilder::FixedDoubleLiveRangeFor(int index) { 1330 LiveRange* LiveRangeBuilder::FixedDoubleLiveRangeFor(int index) {
1263 DCHECK(index < config()->num_aliased_double_registers()); 1331 DCHECK(index < config()->num_aliased_double_registers());
1264 auto result = data()->fixed_double_live_ranges()[index]; 1332 auto result = data()->fixed_double_live_ranges()[index];
1265 if (result == nullptr) { 1333 if (result == nullptr) {
1266 result = data()->NewLiveRange(FixedDoubleLiveRangeID(index)); 1334 result = data()->NewLiveRange(FixedDoubleLiveRangeID(index), kRepFloat64);
1267 DCHECK(result->IsFixed()); 1335 DCHECK(result->IsFixed());
1268 result->set_kind(DOUBLE_REGISTERS);
1269 result->set_assigned_register(index); 1336 result->set_assigned_register(index);
1270 data()->MarkAllocated(DOUBLE_REGISTERS, index); 1337 data()->MarkAllocated(DOUBLE_REGISTERS, index);
1271 data()->fixed_double_live_ranges()[index] = result; 1338 data()->fixed_double_live_ranges()[index] = result;
1272 } 1339 }
1273 return result; 1340 return result;
1274 } 1341 }
1275 1342
1276 1343
1277 LiveRange* LiveRangeBuilder::LiveRangeFor(InstructionOperand* operand) { 1344 LiveRange* LiveRangeBuilder::LiveRangeFor(InstructionOperand* operand) {
1278 if (operand->IsUnallocated()) { 1345 if (operand->IsUnallocated()) {
(...skipping 279 matching lines...) Expand 10 before | Expand all | Expand 10 after
1558 // All phi output operands are killed by this block. 1625 // All phi output operands are killed by this block.
1559 ProcessPhis(block, live); 1626 ProcessPhis(block, live);
1560 // Now live is live_in for this block except not including values live 1627 // Now live is live_in for this block except not including values live
1561 // out on backward successor edges. 1628 // out on backward successor edges.
1562 if (block->IsLoopHeader()) ProcessLoopHeader(block, live); 1629 if (block->IsLoopHeader()) ProcessLoopHeader(block, live);
1563 live_in_sets()[block_id] = live; 1630 live_in_sets()[block_id] = live;
1564 } 1631 }
1565 // Postprocess the ranges. 1632 // Postprocess the ranges.
1566 for (auto range : data()->live_ranges()) { 1633 for (auto range : data()->live_ranges()) {
1567 if (range == nullptr) continue; 1634 if (range == nullptr) continue;
1568 range->set_kind(RequiredRegisterKind(range->id()));
1569 // Give slots to all ranges with a non fixed slot use. 1635 // Give slots to all ranges with a non fixed slot use.
1570 if (range->has_slot_use() && range->HasNoSpillType()) { 1636 if (range->has_slot_use() && range->HasNoSpillType()) {
1571 data()->AssignSpillRangeToLiveRange(range); 1637 data()->AssignSpillRangeToLiveRange(range);
1572 } 1638 }
1573 // TODO(bmeurer): This is a horrible hack to make sure that for constant 1639 // TODO(bmeurer): This is a horrible hack to make sure that for constant
1574 // live ranges, every use requires the constant to be in a register. 1640 // live ranges, every use requires the constant to be in a register.
1575 // Without this hack, all uses with "any" policy would get the constant 1641 // Without this hack, all uses with "any" policy would get the constant
1576 // operand assigned. 1642 // operand assigned.
1577 if (range->HasSpillOperand() && range->GetSpillOperand()->IsConstant()) { 1643 if (range->HasSpillOperand() && range->GetSpillOperand()->IsConstant()) {
1578 for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) { 1644 for (auto pos = range->first_pos(); pos != nullptr; pos = pos->next()) {
(...skipping 24 matching lines...) Expand all
1603 1669
1604 void LiveRangeBuilder::ResolvePhiHint(InstructionOperand* operand, 1670 void LiveRangeBuilder::ResolvePhiHint(InstructionOperand* operand,
1605 UsePosition* use_pos) { 1671 UsePosition* use_pos) {
1606 auto it = phi_hints_.find(operand); 1672 auto it = phi_hints_.find(operand);
1607 if (it == phi_hints_.end()) return; 1673 if (it == phi_hints_.end()) return;
1608 DCHECK(!it->second->IsResolved()); 1674 DCHECK(!it->second->IsResolved());
1609 it->second->ResolveHint(use_pos); 1675 it->second->ResolveHint(use_pos);
1610 } 1676 }
1611 1677
1612 1678
1613 RegisterKind LiveRangeBuilder::RequiredRegisterKind(
1614 int virtual_register) const {
1615 return (code()->IsDouble(virtual_register)) ? DOUBLE_REGISTERS
1616 : GENERAL_REGISTERS;
1617 }
1618
1619
1620 void LiveRangeBuilder::Verify() const { 1679 void LiveRangeBuilder::Verify() const {
1621 for (auto& hint : phi_hints_) { 1680 for (auto& hint : phi_hints_) {
1622 CHECK(hint.second->IsResolved()); 1681 CHECK(hint.second->IsResolved());
1623 } 1682 }
1624 for (auto current : data()->live_ranges()) { 1683 for (auto current : data()->live_ranges()) {
1625 if (current != nullptr) current->Verify(); 1684 if (current != nullptr) current->Verify();
1626 } 1685 }
1627 } 1686 }
1628 1687
1629 1688
(...skipping 10 matching lines...) Expand all
1640 TRACE("Splitting live range %d at %d\n", range->id(), pos.value()); 1699 TRACE("Splitting live range %d at %d\n", range->id(), pos.value());
1641 1700
1642 if (pos <= range->Start()) return range; 1701 if (pos <= range->Start()) return range;
1643 1702
1644 // We can't properly connect liveranges if splitting occurred at the end 1703 // We can't properly connect liveranges if splitting occurred at the end
1645 // a block. 1704 // a block.
1646 DCHECK(pos.IsStart() || pos.IsGapPosition() || 1705 DCHECK(pos.IsStart() || pos.IsGapPosition() ||
1647 (GetInstructionBlock(code(), pos)->last_instruction_index() != 1706 (GetInstructionBlock(code(), pos)->last_instruction_index() !=
1648 pos.ToInstructionIndex())); 1707 pos.ToInstructionIndex()));
1649 1708
1650 int vreg = code()->NextVirtualRegister(); 1709 auto result = data()->NewChildRangeFor(range);
1651 auto result = LiveRangeFor(vreg);
1652 range->SplitAt(pos, result, allocation_zone()); 1710 range->SplitAt(pos, result, allocation_zone());
1653 return result; 1711 return result;
1654 } 1712 }
1655 1713
1656 1714
1657 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range, 1715 LiveRange* RegisterAllocator::SplitBetween(LiveRange* range,
1658 LifetimePosition start, 1716 LifetimePosition start,
1659 LifetimePosition end) { 1717 LifetimePosition end) {
1660 DCHECK(!range->IsFixed()); 1718 DCHECK(!range->IsFixed());
1661 TRACE("Splitting live range %d in position between [%d, %d]\n", range->id(), 1719 TRACE("Splitting live range %d in position between [%d, %d]\n", range->id(),
(...skipping 983 matching lines...) Expand 10 before | Expand all | Expand 10 after
2645 auto other = spill_ranges[j]; 2703 auto other = spill_ranges[j];
2646 if (!other->IsEmpty()) { 2704 if (!other->IsEmpty()) {
2647 range->TryMerge(other); 2705 range->TryMerge(other);
2648 } 2706 }
2649 } 2707 }
2650 } 2708 }
2651 // Allocate slots for the merged spill ranges. 2709 // Allocate slots for the merged spill ranges.
2652 for (auto range : spill_ranges) { 2710 for (auto range : spill_ranges) {
2653 if (range->IsEmpty()) continue; 2711 if (range->IsEmpty()) continue;
2654 // Allocate a new operand referring to the spill slot. 2712 // Allocate a new operand referring to the spill slot.
2655 auto kind = range->kind(); 2713 int byte_width = range->ByteWidth();
2656 int index = data()->frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS); 2714 int index = data()->frame()->AllocateSpillSlot(byte_width);
2657 auto op_kind = kind == DOUBLE_REGISTERS 2715 range->set_assigned_slot(index);
2658 ? AllocatedOperand::DOUBLE_STACK_SLOT
2659 : AllocatedOperand::STACK_SLOT;
2660 auto op = AllocatedOperand::New(data()->code_zone(), op_kind, index);
2661 range->SetOperand(op);
2662 } 2716 }
2663 } 2717 }
2664 2718
2665 2719
2666 void OperandAssigner::CommitAssignment() { 2720 void OperandAssigner::CommitAssignment() {
2667 for (auto range : data()->live_ranges()) { 2721 for (auto range : data()->live_ranges()) {
2668 if (range == nullptr || range->IsEmpty()) continue; 2722 if (range == nullptr || range->IsEmpty()) continue;
2669 InstructionOperand* spill_operand = nullptr; 2723 InstructionOperand spill_operand;
2670 if (!range->TopLevel()->HasNoSpillType()) { 2724 if (range->TopLevel()->HasSpillOperand()) {
2671 spill_operand = range->TopLevel()->GetSpillOperand(); 2725 spill_operand = *range->TopLevel()->GetSpillOperand();
2726 } else if (range->TopLevel()->HasSpillRange()) {
2727 spill_operand = range->TopLevel()->GetSpillRangeOperand();
2672 } 2728 }
2673 auto assigned = range->GetAssignedOperand(); 2729 auto assigned = range->GetAssignedOperand();
2674 range->ConvertUsesToOperand(assigned, spill_operand); 2730 range->ConvertUsesToOperand(assigned, spill_operand);
2675 if (range->is_phi()) { 2731 if (range->is_phi()) {
2676 data()->GetPhiMapValueFor(range->id())->CommitAssignment(assigned); 2732 data()->GetPhiMapValueFor(range->id())->CommitAssignment(assigned);
2677 } 2733 }
2678 if (!range->IsChild() && spill_operand != nullptr) { 2734 if (!range->IsChild() && !spill_operand.IsInvalid()) {
2679 range->CommitSpillsAtDefinition(data()->code(), spill_operand, 2735 range->CommitSpillsAtDefinition(data()->code(), spill_operand,
2680 range->has_slot_use()); 2736 range->has_slot_use());
2681 } 2737 }
2682 } 2738 }
2683 } 2739 }
2684 2740
2685 2741
2686 ReferenceMapPopulator::ReferenceMapPopulator(RegisterAllocationData* data) 2742 ReferenceMapPopulator::ReferenceMapPopulator(RegisterAllocationData* data)
2687 : data_(data) {} 2743 : data_(data) {}
2688 2744
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after
2749 auto safe_point_pos = 2805 auto safe_point_pos =
2750 LifetimePosition::InstructionFromInstructionIndex(safe_point); 2806 LifetimePosition::InstructionFromInstructionIndex(safe_point);
2751 auto cur = range; 2807 auto cur = range;
2752 while (cur != nullptr && !cur->Covers(safe_point_pos)) { 2808 while (cur != nullptr && !cur->Covers(safe_point_pos)) {
2753 cur = cur->next(); 2809 cur = cur->next();
2754 } 2810 }
2755 if (cur == nullptr) continue; 2811 if (cur == nullptr) continue;
2756 2812
2757 // Check if the live range is spilled and the safe point is after 2813 // Check if the live range is spilled and the safe point is after
2758 // the spill position. 2814 // the spill position.
2759 if (range->HasSpillOperand() && 2815 if (((range->HasSpillOperand() &&
2760 safe_point >= range->spill_start_index() && 2816 !range->GetSpillOperand()->IsConstant()) ||
2761 !range->GetSpillOperand()->IsConstant()) { 2817 range->HasSpillRange()) &&
2818 safe_point >= range->spill_start_index()) {
2762 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n", 2819 TRACE("Pointer for range %d (spilled at %d) at safe point %d\n",
2763 range->id(), range->spill_start_index(), safe_point); 2820 range->id(), range->spill_start_index(), safe_point);
2764 map->RecordReference(*range->GetSpillOperand()); 2821 InstructionOperand operand;
2822 if (range->HasSpillOperand()) {
2823 operand = *range->GetSpillOperand();
2824 } else {
2825 operand = range->GetSpillRangeOperand();
2826 }
2827 DCHECK(operand.IsStackSlot());
2828 DCHECK_EQ(kRepTagged, AllocatedOperand::cast(operand).machine_type());
2829 map->RecordReference(operand);
2765 } 2830 }
2766 2831
2767 if (!cur->spilled()) { 2832 if (!cur->spilled()) {
2768 TRACE( 2833 TRACE(
2769 "Pointer in register for range %d (start at %d) " 2834 "Pointer in register for range %d (start at %d) "
2770 "at safe point %d\n", 2835 "at safe point %d\n",
2771 cur->id(), cur->Start().value(), safe_point); 2836 cur->id(), cur->Start().value(), safe_point);
2772 auto operand = cur->GetAssignedOperand(); 2837 auto operand = cur->GetAssignedOperand();
2773 DCHECK(!operand.IsStackSlot()); 2838 DCHECK(!operand.IsStackSlot());
2839 DCHECK_EQ(kRepTagged, AllocatedOperand::cast(operand).machine_type());
2774 map->RecordReference(operand); 2840 map->RecordReference(operand);
2775 } 2841 }
2776 } 2842 }
2777 } 2843 }
2778 } 2844 }
2779 2845
2780 2846
2781 namespace { 2847 namespace {
2782 2848
2783 class LiveRangeBound { 2849 class LiveRangeBound {
(...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after
2902 2968
2903 private: 2969 private:
2904 const RegisterAllocationData* const data_; 2970 const RegisterAllocationData* const data_;
2905 const int bounds_length_; 2971 const int bounds_length_;
2906 LiveRangeBoundArray* const bounds_; 2972 LiveRangeBoundArray* const bounds_;
2907 Zone* const zone_; 2973 Zone* const zone_;
2908 2974
2909 DISALLOW_COPY_AND_ASSIGN(LiveRangeFinder); 2975 DISALLOW_COPY_AND_ASSIGN(LiveRangeFinder);
2910 }; 2976 };
2911 2977
2978
2979 typedef std::pair<ParallelMove*, InstructionOperand> DelayedInsertionMapKey;
2980
2981
2982 struct DelayedInsertionMapCompare {
2983 bool operator()(const DelayedInsertionMapKey& a,
2984 const DelayedInsertionMapKey& b) {
2985 if (a.first == b.first) {
2986 return a.second.Compare(b.second);
2987 }
2988 return a.first < b.first;
2989 }
2990 };
2991
2992
2993 typedef ZoneMap<DelayedInsertionMapKey, InstructionOperand,
2994 DelayedInsertionMapCompare> DelayedInsertionMap;
2995
2912 } // namespace 2996 } // namespace
2913 2997
2914 2998
2915 LiveRangeConnector::LiveRangeConnector(RegisterAllocationData* data) 2999 LiveRangeConnector::LiveRangeConnector(RegisterAllocationData* data)
2916 : data_(data) {} 3000 : data_(data) {}
2917 3001
2918 3002
2919 bool LiveRangeConnector::CanEagerlyResolveControlFlow( 3003 bool LiveRangeConnector::CanEagerlyResolveControlFlow(
2920 const InstructionBlock* block) const { 3004 const InstructionBlock* block) const {
2921 if (block->PredecessorCount() != 1) return false; 3005 if (block->PredecessorCount() != 1) return false;
(...skipping 13 matching lines...) Expand all
2935 auto* array = finder.ArrayFor(iterator.Current()); 3019 auto* array = finder.ArrayFor(iterator.Current());
2936 for (auto pred : block->predecessors()) { 3020 for (auto pred : block->predecessors()) {
2937 FindResult result; 3021 FindResult result;
2938 const auto* pred_block = code()->InstructionBlockAt(pred); 3022 const auto* pred_block = code()->InstructionBlockAt(pred);
2939 array->Find(block, pred_block, &result); 3023 array->Find(block, pred_block, &result);
2940 if (result.cur_cover_ == result.pred_cover_ || 3024 if (result.cur_cover_ == result.pred_cover_ ||
2941 result.cur_cover_->spilled()) 3025 result.cur_cover_->spilled())
2942 continue; 3026 continue;
2943 auto pred_op = result.pred_cover_->GetAssignedOperand(); 3027 auto pred_op = result.pred_cover_->GetAssignedOperand();
2944 auto cur_op = result.cur_cover_->GetAssignedOperand(); 3028 auto cur_op = result.cur_cover_->GetAssignedOperand();
2945 if (pred_op == cur_op) continue; 3029 if (pred_op.Equals(cur_op)) continue;
2946 ResolveControlFlow(block, cur_op, pred_block, pred_op); 3030 ResolveControlFlow(block, cur_op, pred_block, pred_op);
2947 } 3031 }
2948 iterator.Advance(); 3032 iterator.Advance();
2949 } 3033 }
2950 } 3034 }
2951 } 3035 }
2952 3036
2953 3037
2954 void LiveRangeConnector::ResolveControlFlow(const InstructionBlock* block, 3038 void LiveRangeConnector::ResolveControlFlow(const InstructionBlock* block,
2955 const InstructionOperand& cur_op, 3039 const InstructionOperand& cur_op,
2956 const InstructionBlock* pred, 3040 const InstructionBlock* pred,
2957 const InstructionOperand& pred_op) { 3041 const InstructionOperand& pred_op) {
2958 DCHECK(pred_op != cur_op); 3042 DCHECK(!pred_op.Equals(cur_op));
2959 int gap_index; 3043 int gap_index;
2960 Instruction::GapPosition position; 3044 Instruction::GapPosition position;
2961 if (block->PredecessorCount() == 1) { 3045 if (block->PredecessorCount() == 1) {
2962 gap_index = block->first_instruction_index(); 3046 gap_index = block->first_instruction_index();
2963 position = Instruction::START; 3047 position = Instruction::START;
2964 } else { 3048 } else {
2965 DCHECK(pred->SuccessorCount() == 1); 3049 DCHECK(pred->SuccessorCount() == 1);
2966 DCHECK(!code() 3050 DCHECK(!code()
2967 ->InstructionAt(pred->last_instruction_index()) 3051 ->InstructionAt(pred->last_instruction_index())
2968 ->HasReferenceMap()); 3052 ->HasReferenceMap());
2969 gap_index = pred->last_instruction_index(); 3053 gap_index = pred->last_instruction_index();
2970 position = Instruction::END; 3054 position = Instruction::END;
2971 } 3055 }
2972 data()->AddGapMove(gap_index, position, pred_op, cur_op); 3056 data()->AddGapMove(gap_index, position, pred_op, cur_op);
2973 } 3057 }
2974 3058
2975 3059
2976 void LiveRangeConnector::ConnectRanges(Zone* local_zone) { 3060 void LiveRangeConnector::ConnectRanges(Zone* local_zone) {
2977 ZoneMap<std::pair<ParallelMove*, InstructionOperand>, InstructionOperand> 3061 DelayedInsertionMap delayed_insertion_map(local_zone);
2978 delayed_insertion_map(local_zone);
2979 for (auto first_range : data()->live_ranges()) { 3062 for (auto first_range : data()->live_ranges()) {
2980 if (first_range == nullptr || first_range->IsChild()) continue; 3063 if (first_range == nullptr || first_range->IsChild()) continue;
2981 for (auto second_range = first_range->next(); second_range != nullptr; 3064 for (auto second_range = first_range->next(); second_range != nullptr;
2982 first_range = second_range, second_range = second_range->next()) { 3065 first_range = second_range, second_range = second_range->next()) {
2983 auto pos = second_range->Start(); 3066 auto pos = second_range->Start();
2984 // Add gap move if the two live ranges touch and there is no block 3067 // Add gap move if the two live ranges touch and there is no block
2985 // boundary. 3068 // boundary.
2986 if (second_range->spilled()) continue; 3069 if (second_range->spilled()) continue;
2987 if (first_range->End() != pos) continue; 3070 if (first_range->End() != pos) continue;
2988 if (IsBlockBoundary(code(), pos) && 3071 if (IsBlockBoundary(code(), pos) &&
2989 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) { 3072 !CanEagerlyResolveControlFlow(GetInstructionBlock(code(), pos))) {
2990 continue; 3073 continue;
2991 } 3074 }
2992 auto prev_operand = first_range->GetAssignedOperand(); 3075 auto prev_operand = first_range->GetAssignedOperand();
2993 auto cur_operand = second_range->GetAssignedOperand(); 3076 auto cur_operand = second_range->GetAssignedOperand();
2994 if (prev_operand == cur_operand) continue; 3077 if (prev_operand.Equals(cur_operand)) continue;
2995 bool delay_insertion = false; 3078 bool delay_insertion = false;
2996 Instruction::GapPosition gap_pos; 3079 Instruction::GapPosition gap_pos;
2997 int gap_index = pos.ToInstructionIndex(); 3080 int gap_index = pos.ToInstructionIndex();
2998 if (pos.IsGapPosition()) { 3081 if (pos.IsGapPosition()) {
2999 gap_pos = pos.IsStart() ? Instruction::START : Instruction::END; 3082 gap_pos = pos.IsStart() ? Instruction::START : Instruction::END;
3000 } else { 3083 } else {
3001 if (pos.IsStart()) { 3084 if (pos.IsStart()) {
3002 delay_insertion = true; 3085 delay_insertion = true;
3003 } else { 3086 } else {
3004 gap_index++; 3087 gap_index++;
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
3043 auto eliminate = moves->PrepareInsertAfter(move); 3126 auto eliminate = moves->PrepareInsertAfter(move);
3044 to_insert.push_back(move); 3127 to_insert.push_back(move);
3045 if (eliminate != nullptr) to_eliminate.push_back(eliminate); 3128 if (eliminate != nullptr) to_eliminate.push_back(eliminate);
3046 } 3129 }
3047 } 3130 }
3048 3131
3049 3132
3050 } // namespace compiler 3133 } // namespace compiler
3051 } // namespace internal 3134 } // namespace internal
3052 } // namespace v8 3135 } // namespace v8
OLDNEW
« no previous file with comments | « src/compiler/register-allocator.h ('k') | src/compiler/register-allocator-verifier.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698