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

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

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
« src/lithium-allocator.h ('K') | « src/lithium-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 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 #include "src/v8.h" 5 #include "src/v8.h"
6 #include "src/lithium-allocator-inl.h" 6 #include "src/lithium-allocator-inl.h"
7 7
8 #include "src/hydrogen.h" 8 #include "src/hydrogen.h"
9 #include "src/string-stream.h" 9 #include "src/string-stream.h"
10 10
(...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after
117 assigned_register_(kInvalidAssignment), 117 assigned_register_(kInvalidAssignment),
118 last_interval_(NULL), 118 last_interval_(NULL),
119 first_interval_(NULL), 119 first_interval_(NULL),
120 first_pos_(NULL), 120 first_pos_(NULL),
121 parent_(NULL), 121 parent_(NULL),
122 next_(NULL), 122 next_(NULL),
123 current_interval_(NULL), 123 current_interval_(NULL),
124 last_processed_use_(NULL), 124 last_processed_use_(NULL),
125 current_hint_operand_(NULL), 125 current_hint_operand_(NULL),
126 spill_operand_(new(zone) LOperand()), 126 spill_operand_(new(zone) LOperand()),
127 spill_start_index_(kMaxInt) { } 127 spill_start_index_(kMaxInt),
128 spill_range_id_(SpillRange::INVALID_ID) { }
128 129
129 130
130 void LiveRange::set_assigned_register(int reg, Zone* zone) { 131 void LiveRange::set_assigned_register(int reg, Zone* zone) {
131 ASSERT(!HasRegisterAssigned() && !IsSpilled()); 132 ASSERT(!HasRegisterAssigned() && !IsSpilled());
132 assigned_register_ = reg; 133 assigned_register_ = reg;
133 ConvertOperands(zone); 134 ConvertOperands(zone);
134 } 135 }
135 136
136 137
137 void LiveRange::MakeSpilled(Zone* zone) { 138 void LiveRange::MakeSpilled(Zone* zone) {
138 ASSERT(!IsSpilled()); 139 ASSERT(!IsSpilled());
139 ASSERT(TopLevel()->HasAllocatedSpillOperand()); 140 ASSERT(TopLevel()->HasAllocatedSpillOperand());
140 spilled_ = true; 141 spilled_ = true;
141 assigned_register_ = kInvalidAssignment; 142 assigned_register_ = kInvalidAssignment;
142 ConvertOperands(zone); 143 if (spill_range_id_ == SpillRange::INVALID_ID) {
144 ConvertOperands(zone);
145 }
143 } 146 }
144 147
145 148
146 bool LiveRange::HasAllocatedSpillOperand() const { 149 bool LiveRange::HasAllocatedSpillOperand() const {
147 ASSERT(spill_operand_ != NULL); 150 ASSERT(spill_operand_ != NULL);
148 return !spill_operand_->IsIgnored(); 151 return !spill_operand_->IsIgnored() ||
152 spill_range_id_ != SpillRange::INVALID_ID;
149 } 153 }
150 154
151 155
152 void LiveRange::SetSpillOperand(LOperand* operand) { 156 void LiveRange::SetSpillOperand(LOperand* operand) {
153 ASSERT(!operand->IsUnallocated()); 157 ASSERT(!operand->IsUnallocated());
154 ASSERT(spill_operand_ != NULL); 158 ASSERT(spill_operand_ != NULL);
155 ASSERT(spill_operand_->IsIgnored()); 159 ASSERT(spill_operand_->IsIgnored());
156 spill_operand_->ConvertTo(operand->kind(), operand->index()); 160 spill_operand_->ConvertTo(operand->kind(), operand->index());
157 } 161 }
158 162
159 163
164 void LiveRange::CommitSpillOperand(LOperand* operand) {
165 ASSERT(spill_range_id_ != SpillRange::INVALID_ID);
166 ASSERT(!IsChild());
167 spill_range_id_ = SpillRange::INVALID_ID;
168 SetSpillOperand(operand);
169 for (LiveRange* range = this; range != NULL; range = range->next()) {
170 if (range->IsSpilled()) {
171 range->ConvertUsesToOperand(operand);
172 }
173 }
174 }
175
176
160 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) { 177 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) {
161 UsePosition* use_pos = last_processed_use_; 178 UsePosition* use_pos = last_processed_use_;
162 if (use_pos == NULL) use_pos = first_pos(); 179 if (use_pos == NULL) use_pos = first_pos();
163 while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { 180 while (use_pos != NULL && use_pos->pos().Value() < start.Value()) {
164 use_pos = use_pos->next(); 181 use_pos = use_pos->next();
165 } 182 }
166 last_processed_use_ = use_pos; 183 last_processed_use_ = use_pos;
167 return use_pos; 184 return use_pos;
168 } 185 }
169 186
(...skipping 284 matching lines...) Expand 10 before | Expand all | Expand 10 after
454 use_pos->next_ = prev->next_; 471 use_pos->next_ = prev->next_;
455 prev->next_ = use_pos; 472 prev->next_ = use_pos;
456 } 473 }
457 474
458 if (prev_hint == NULL && use_pos->HasHint()) { 475 if (prev_hint == NULL && use_pos->HasHint()) {
459 current_hint_operand_ = hint; 476 current_hint_operand_ = hint;
460 } 477 }
461 } 478 }
462 479
463 480
464 void LiveRange::ConvertOperands(Zone* zone) { 481 void LiveRange::ConvertUsesToOperand(LOperand* op) {
465 LOperand* op = CreateAssignedOperand(zone);
466 UsePosition* use_pos = first_pos(); 482 UsePosition* use_pos = first_pos();
467 while (use_pos != NULL) { 483 while (use_pos != NULL) {
468 ASSERT(Start().Value() <= use_pos->pos().Value() && 484 ASSERT(Start().Value() <= use_pos->pos().Value() &&
469 use_pos->pos().Value() <= End().Value()); 485 use_pos->pos().Value() <= End().Value());
470 486
471 if (use_pos->HasOperand()) { 487 if (use_pos->HasOperand()) {
472 ASSERT(op->IsRegister() || op->IsDoubleRegister() || 488 ASSERT(op->IsRegister() || op->IsDoubleRegister() ||
473 !use_pos->RequiresRegister()); 489 !use_pos->RequiresRegister());
474 use_pos->operand()->ConvertTo(op->kind(), op->index()); 490 use_pos->operand()->ConvertTo(op->kind(), op->index());
475 } 491 }
476 use_pos = use_pos->next(); 492 use_pos = use_pos->next();
477 } 493 }
478 } 494 }
479 495
480 496
497 void LiveRange::ConvertOperands(Zone* zone) {
498 LOperand* op = CreateAssignedOperand(zone);
499 ConvertUsesToOperand(op);
500 }
501
502
481 bool LiveRange::CanCover(LifetimePosition position) const { 503 bool LiveRange::CanCover(LifetimePosition position) const {
482 if (IsEmpty()) return false; 504 if (IsEmpty()) return false;
483 return Start().Value() <= position.Value() && 505 return Start().Value() <= position.Value() &&
484 position.Value() < End().Value(); 506 position.Value() < End().Value();
485 } 507 }
486 508
487 509
488 bool LiveRange::Covers(LifetimePosition position) { 510 bool LiveRange::Covers(LifetimePosition position) {
489 if (!CanCover(position)) return false; 511 if (!CanCover(position)) return false;
490 UseInterval* start_search = FirstSearchIntervalForPosition(position); 512 UseInterval* start_search = FirstSearchIntervalForPosition(position);
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
529 : zone_(graph->isolate()), 551 : zone_(graph->isolate()),
530 chunk_(NULL), 552 chunk_(NULL),
531 live_in_sets_(graph->blocks()->length(), zone()), 553 live_in_sets_(graph->blocks()->length(), zone()),
532 live_ranges_(num_values * 2, zone()), 554 live_ranges_(num_values * 2, zone()),
533 fixed_live_ranges_(NULL), 555 fixed_live_ranges_(NULL),
534 fixed_double_live_ranges_(NULL), 556 fixed_double_live_ranges_(NULL),
535 unhandled_live_ranges_(num_values * 2, zone()), 557 unhandled_live_ranges_(num_values * 2, zone()),
536 active_live_ranges_(8, zone()), 558 active_live_ranges_(8, zone()),
537 inactive_live_ranges_(8, zone()), 559 inactive_live_ranges_(8, zone()),
538 reusable_slots_(8, zone()), 560 reusable_slots_(8, zone()),
561 spill_ranges_(8, zone()),
539 next_virtual_register_(num_values), 562 next_virtual_register_(num_values),
540 first_artificial_register_(num_values), 563 first_artificial_register_(num_values),
541 mode_(UNALLOCATED_REGISTERS), 564 mode_(UNALLOCATED_REGISTERS),
542 num_registers_(-1), 565 num_registers_(-1),
543 graph_(graph), 566 graph_(graph),
544 has_osr_entry_(false), 567 has_osr_entry_(false),
545 allocation_ok_(true) { } 568 allocation_ok_(true) { }
546 569
547 570
548 void LAllocator::InitializeLivenessAnalysis() { 571 void LAllocator::InitializeLivenessAnalysis() {
(...skipping 475 matching lines...) Expand 10 before | Expand all | Expand 10 after
1024 index = index - 1; 1047 index = index - 1;
1025 } 1048 }
1026 } 1049 }
1027 1050
1028 1051
1029 void LAllocator::ResolvePhis(HBasicBlock* block) { 1052 void LAllocator::ResolvePhis(HBasicBlock* block) {
1030 const ZoneList<HPhi*>* phis = block->phis(); 1053 const ZoneList<HPhi*>* phis = block->phis();
1031 for (int i = 0; i < phis->length(); ++i) { 1054 for (int i = 0; i < phis->length(); ++i) {
1032 HPhi* phi = phis->at(i); 1055 HPhi* phi = phis->at(i);
1033 LUnallocated* phi_operand = 1056 LUnallocated* phi_operand =
1034 new(chunk()->zone()) LUnallocated(LUnallocated::NONE); 1057 new(chunk()->zone()) LUnallocated(LUnallocated::ANY);
1035 phi_operand->set_virtual_register(phi->id()); 1058 phi_operand->set_virtual_register(phi->id());
1036 for (int j = 0; j < phi->OperandCount(); ++j) { 1059 for (int j = 0; j < phi->OperandCount(); ++j) {
1037 HValue* op = phi->OperandAt(j); 1060 HValue* op = phi->OperandAt(j);
1038 LOperand* operand = NULL; 1061 LOperand* operand = NULL;
1039 if (op->IsConstant() && op->EmitAtUses()) { 1062 if (op->IsConstant() && op->EmitAtUses()) {
1040 HConstant* constant = HConstant::cast(op); 1063 HConstant* constant = HConstant::cast(op);
1041 operand = chunk_->DefineConstantOperand(constant); 1064 operand = chunk_->DefineConstantOperand(constant);
1042 } else { 1065 } else {
1043 ASSERT(!op->EmitAtUses()); 1066 ASSERT(!op->EmitAtUses());
1044 LUnallocated* unalloc = 1067 LUnallocated* unalloc =
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
1091 new(chunk->zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), 1114 new(chunk->zone()) BitVector(DoubleRegister::NumAllocatableRegisters(),
1092 chunk->zone()); 1115 chunk->zone());
1093 MeetRegisterConstraints(); 1116 MeetRegisterConstraints();
1094 if (!AllocationOk()) return false; 1117 if (!AllocationOk()) return false;
1095 ResolvePhis(); 1118 ResolvePhis();
1096 BuildLiveRanges(); 1119 BuildLiveRanges();
1097 AllocateGeneralRegisters(); 1120 AllocateGeneralRegisters();
1098 if (!AllocationOk()) return false; 1121 if (!AllocationOk()) return false;
1099 AllocateDoubleRegisters(); 1122 AllocateDoubleRegisters();
1100 if (!AllocationOk()) return false; 1123 if (!AllocationOk()) return false;
1124 ReuseSpillSlots();
1101 PopulatePointerMaps(); 1125 PopulatePointerMaps();
1102 ConnectRanges(); 1126 ConnectRanges();
1103 ResolveControlFlow(); 1127 ResolveControlFlow();
1104 return true; 1128 return true;
1105 } 1129 }
1106 1130
1107 1131
1132 static bool AreUseIntervalsIntersecting(
1133 UseInterval* interval1, UseInterval* interval2) {
1134 while (interval1 != NULL && interval2 != NULL) {
titzer 2014/06/17 09:01:34 I suppose we could speed this interval check up wi
Jarin 2014/06/24 21:49:58 Yes, the asymptotic complexity is indeed bad, but
1135 if (interval1->start().Value() < interval2->start().Value()) {
1136 if (interval1->end().Value() > interval2->start().Value()) {
1137 return true;
1138 }
1139 interval1 = interval1->next();
1140 } else {
1141 if (interval2->end().Value() > interval1->start().Value()) {
1142 return true;
1143 }
1144 interval2 = interval2->next();
1145 }
1146 }
1147 return false;
1148 }
1149
1150
1151 SpillRange::SpillRange(LiveRange* range, int id, Zone* zone)
1152 : id_(id),
1153 live_ranges_(1, zone) {
1154 UseInterval* src = range->first_interval();
1155 UseInterval* result = NULL;
1156 UseInterval* node = NULL;
1157 // Copy the nodes
1158 while (src != NULL) {
1159 UseInterval* new_node = new(zone) UseInterval(src->start(), src->end());
1160 if (result == NULL) {
1161 result = new_node;
1162 } else {
1163 node->set_next(new_node);
1164 }
1165 node = new_node;
1166 src = src->next();
1167 }
1168 use_interval_ = result;
1169 live_ranges_.Add(range, zone);
1170 ASSERT(range->GetSpillRangeId() == SpillRange::INVALID_ID);
1171 range->SetSpillRangeId(id);
1172 }
1173
1174
1175 void SpillRange::Swap(UseInterval*& a, UseInterval*& b) {
titzer 2014/06/17 09:01:34 You can replace uses of this with std::swap
Jarin 2014/06/24 21:49:58 Done.
1176 UseInterval* temp = a;
1177 a = b;
1178 b = temp;
1179 }
1180
1181
1182 bool SpillRange::TryMerge(SpillRange* other, Zone* zone) {
1183 if (Kind() == other->Kind() &&
1184 !AreUseIntervalsIntersecting(use_interval_, other->use_interval_)) {
1185 MergeDisjointIntervals(other->use_interval_, zone);
1186 other->use_interval_ = NULL;
1187
1188 for (int i = 0; i < other->live_ranges_.length(); i++) {
1189 ASSERT(other->live_ranges_.at(i)->GetSpillRangeId() == other->id());
1190 other->live_ranges_.at(i)->SetSpillRangeId(id_);
1191 }
1192
1193 live_ranges_.AddAll(other->live_ranges_, zone);
1194 other->live_ranges_.Clear();
1195
1196 return true;
1197 }
1198 return false;
1199 }
1200
1201
1202 void SpillRange::SetOperand(LOperand* op) {
1203 for (int i = 0; i < live_ranges_.length(); i++) {
1204 ASSERT(live_ranges_.at(i)->GetSpillRangeId() == id());
1205 live_ranges_.at(i)->CommitSpillOperand(op);
1206 }
1207 }
1208
1209
1210 void SpillRange::MergeDisjointIntervals(UseInterval* other, Zone* zone) {
1211 UseInterval* tail = NULL;
1212 UseInterval* current = use_interval_;
1213 while (other != NULL) {
1214 // Make sure the 'current' list starts first
1215 if (current == NULL || current->start().Value() > other->start().Value()) {
1216 Swap(current, other);
1217 }
1218
1219 // Check disjointness
1220 ASSERT(other == NULL || current->end().Value() <= other->start().Value());
1221
1222 // Append the 'current' node to the result accumulator and move forward
1223 if (tail == NULL) {
1224 use_interval_ = current;
1225 } else {
1226 tail->set_next(current);
1227 }
1228 tail = current;
1229 current = current->next();
1230 }
1231 // Other list is empty => we are done
1232 }
1233
1234
1235 void LAllocator::ReuseSpillSlots() {
1236 // Merge disjoint spill ranges
1237 for (int i = 0; i < spill_ranges_.length(); i++) {
1238 SpillRange* range = spill_ranges_.at(i);
1239 if (!range->IsEmpty()) {
1240 for (int j = i + 1; j < spill_ranges_.length(); j++) {
1241 SpillRange* other = spill_ranges_.at(j);
1242 if (!other->IsEmpty()) {
1243 range->TryMerge(spill_ranges_.at(j), zone());
1244 }
1245 }
1246 }
1247 }
1248
1249 // Allocate slots for the merged spill ranges.
1250 for (int i = 0; i < spill_ranges_.length(); i++) {
1251 SpillRange* range = spill_ranges_.at(i);
1252 if (!range->IsEmpty()) {
1253 LOperand* op = chunk_->GetNextSpillSlot(range->Kind());
1254 range->SetOperand(op);
1255 }
1256 }
1257 }
1258
1259
1108 void LAllocator::MeetRegisterConstraints() { 1260 void LAllocator::MeetRegisterConstraints() {
1109 LAllocatorPhase phase("L_Register constraints", this); 1261 LAllocatorPhase phase("L_Register constraints", this);
1110 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); 1262 const ZoneList<HBasicBlock*>* blocks = graph_->blocks();
1111 for (int i = 0; i < blocks->length(); ++i) { 1263 for (int i = 0; i < blocks->length(); ++i) {
1112 HBasicBlock* block = blocks->at(i); 1264 HBasicBlock* block = blocks->at(i);
1113 MeetRegisterConstraints(block); 1265 MeetRegisterConstraints(block);
1114 if (!AllocationOk()) return; 1266 if (!AllocationOk()) return;
1115 } 1267 }
1116 } 1268 }
1117 1269
(...skipping 370 matching lines...) Expand 10 before | Expand all | Expand 10 after
1488 1640
1489 1641
1490 void LAllocator::AllocateDoubleRegisters() { 1642 void LAllocator::AllocateDoubleRegisters() {
1491 LAllocatorPhase phase("L_Allocate double registers", this); 1643 LAllocatorPhase phase("L_Allocate double registers", this);
1492 num_registers_ = DoubleRegister::NumAllocatableRegisters(); 1644 num_registers_ = DoubleRegister::NumAllocatableRegisters();
1493 mode_ = DOUBLE_REGISTERS; 1645 mode_ = DOUBLE_REGISTERS;
1494 AllocateRegisters(); 1646 AllocateRegisters();
1495 } 1647 }
1496 1648
1497 1649
1650 bool LAllocator::TryReuseSpillForPhi(LiveRange* range) {
1651 ASSERT(!range->HasAllocatedSpillOperand());
1652 if (range->IsChild()) {
1653 return false;
1654 }
1655 HValue* instr = graph_->LookupValue(range->id());
1656 if (instr == NULL || !instr->IsPhi()) {
1657 return false;
1658 }
1659
1660 // Count the number of spilled operands.
1661 HPhi* phi = HPhi::cast(instr);
1662 int spilled_count = 0;
1663 LiveRange* first_op = NULL;
1664 for (int i = 0; i < phi->OperandCount(); i++) {
1665 HValue* op = phi->OperandAt(i);
1666 LiveRange* op_range = LiveRangeFor(op->id());
1667 if (op_range->GetSpillRangeId() != SpillRange::INVALID_ID) {
1668 HBasicBlock* pred = instr->block()->predecessors()->at(i);
1669 LifetimePosition pred_end = LifetimePosition::FromInstructionIndex(
1670 pred->last_instruction_index());
1671 while (op_range != NULL && !op_range->CanCover(pred_end)) {
1672 op_range = op_range->next();
1673 }
1674 if (op_range != NULL && op_range->IsSpilled()) {
1675 spilled_count++;
1676 if (first_op == NULL) {
1677 first_op = op_range->TopLevel();
1678 }
1679 }
1680 }
1681 }
1682
1683 // Only continue if more than half of the operands are spilled.
1684 if (spilled_count * 2 <= phi->OperandCount()) {
1685 return false;
1686 }
1687
1688 // Try to merge the spilled operands and count the number of merged spilled
1689 // operands.
1690 ASSERT(first_op != NULL);
1691 SpillRange* first_op_spill = spill_ranges_.at(first_op->GetSpillRangeId());
1692 int num_merged = 1;
1693 for (int i = 1; i < phi->OperandCount(); i++) {
1694 HValue* op = phi->OperandAt(i);
1695 LiveRange* op_range = LiveRangeFor(op->id());
1696 int spill_range_id = op_range->GetSpillRangeId();
1697 if (spill_range_id != SpillRange::INVALID_ID) {
1698 SpillRange* op_spill = spill_ranges_.at(spill_range_id);
1699 if (op_spill->id() == first_op_spill->id() ||
1700 first_op_spill->TryMerge(op_spill, zone())) {
1701 num_merged++;
1702 }
1703 }
1704 }
1705
1706 // Only continue if enough operands could be merged to the
1707 // same spill slot.
1708 if (num_merged * 2 <= phi->OperandCount() ||
1709 AreUseIntervalsIntersecting(first_op_spill->interval(),
1710 range->first_interval())) {
1711 return false;
1712 }
1713
1714 // If the range does not need register soon, spill it to the merged
1715 // spill range.
1716 LifetimePosition next_pos = range->Start();
1717 if (IsGapAt(next_pos.InstructionIndex())) {
1718 next_pos = next_pos.NextInstruction();
1719 }
1720 UsePosition* pos = range->NextUsePositionRegisterIsBeneficial(next_pos);
1721 if (pos == NULL) {
1722 SpillRange* spill_range = AssignSpillRangeToLiveRange(range->TopLevel());
1723 CHECK(first_op_spill->TryMerge(spill_range, zone()));
1724 Spill(range);
1725 return true;
1726 } else if (pos->pos().Value() >
1727 range->Start().NextInstruction().Value()) {
1728 SpillRange* spill_range = AssignSpillRangeToLiveRange(range->TopLevel());
1729 CHECK(first_op_spill->TryMerge(spill_range, zone()));
1730 SpillBetween(range, range->Start(), pos->pos());
1731 if (!AllocationOk()) return false;
1732 ASSERT(UnhandledIsSorted());
1733 return true;
1734 }
1735
1736 return false;
1737 }
1738
1739
1740 SpillRange* LAllocator::AssignSpillRangeToLiveRange(LiveRange* range) {
1741 int spill_id = spill_ranges_.length();
1742 SpillRange* spill_range = new(zone()) SpillRange(range, spill_id, zone());
1743 spill_ranges_.Add(spill_range, zone());
1744 return spill_range;
1745 }
1746
1747
1498 void LAllocator::AllocateRegisters() { 1748 void LAllocator::AllocateRegisters() {
1499 ASSERT(unhandled_live_ranges_.is_empty()); 1749 ASSERT(unhandled_live_ranges_.is_empty());
1500 1750
1501 for (int i = 0; i < live_ranges_.length(); ++i) { 1751 for (int i = 0; i < live_ranges_.length(); ++i) {
1502 if (live_ranges_[i] != NULL) { 1752 if (live_ranges_[i] != NULL) {
1503 if (live_ranges_[i]->Kind() == mode_) { 1753 if (live_ranges_[i]->Kind() == mode_) {
1504 AddToUnhandledUnsorted(live_ranges_[i]); 1754 AddToUnhandledUnsorted(live_ranges_[i]);
1505 } 1755 }
1506 } 1756 }
1507 } 1757 }
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after
1557 current->Start().NextInstruction().Value()) { 1807 current->Start().NextInstruction().Value()) {
1558 // Do not spill live range eagerly if use position that can benefit from 1808 // Do not spill live range eagerly if use position that can benefit from
1559 // the register is too close to the start of live range. 1809 // the register is too close to the start of live range.
1560 SpillBetween(current, current->Start(), pos->pos()); 1810 SpillBetween(current, current->Start(), pos->pos());
1561 if (!AllocationOk()) return; 1811 if (!AllocationOk()) return;
1562 ASSERT(UnhandledIsSorted()); 1812 ASSERT(UnhandledIsSorted());
1563 continue; 1813 continue;
1564 } 1814 }
1565 } 1815 }
1566 1816
1817 if (TryReuseSpillForPhi(current)) {
1818 continue;
1819 }
1820 if (!AllocationOk()) return;
1821
1567 for (int i = 0; i < active_live_ranges_.length(); ++i) { 1822 for (int i = 0; i < active_live_ranges_.length(); ++i) {
1568 LiveRange* cur_active = active_live_ranges_.at(i); 1823 LiveRange* cur_active = active_live_ranges_.at(i);
1569 if (cur_active->End().Value() <= position.Value()) { 1824 if (cur_active->End().Value() <= position.Value()) {
1570 ActiveToHandled(cur_active); 1825 ActiveToHandled(cur_active);
1571 --i; // The live range was removed from the list of active live ranges. 1826 --i; // The live range was removed from the list of active live ranges.
1572 } else if (!cur_active->Covers(position)) { 1827 } else if (!cur_active->Covers(position)) {
1573 ActiveToInactive(cur_active); 1828 ActiveToInactive(cur_active);
1574 --i; // The live range was removed from the list of active live ranges. 1829 --i; // The live range was removed from the list of active live ranges.
1575 } 1830 }
1576 } 1831 }
(...skipping 130 matching lines...) Expand 10 before | Expand all | Expand 10 after
1707 int len = unhandled_live_ranges_.length(); 1962 int len = unhandled_live_ranges_.length();
1708 for (int i = 1; i < len; i++) { 1963 for (int i = 1; i < len; i++) {
1709 LiveRange* a = unhandled_live_ranges_.at(i - 1); 1964 LiveRange* a = unhandled_live_ranges_.at(i - 1);
1710 LiveRange* b = unhandled_live_ranges_.at(i); 1965 LiveRange* b = unhandled_live_ranges_.at(i);
1711 if (a->Start().Value() < b->Start().Value()) return false; 1966 if (a->Start().Value() < b->Start().Value()) return false;
1712 } 1967 }
1713 return true; 1968 return true;
1714 } 1969 }
1715 1970
1716 1971
1717 void LAllocator::FreeSpillSlot(LiveRange* range) {
1718 // Check that we are the last range.
1719 if (range->next() != NULL) return;
1720
1721 if (!range->TopLevel()->HasAllocatedSpillOperand()) return;
1722
1723 int index = range->TopLevel()->GetSpillOperand()->index();
1724 if (index >= 0) {
1725 reusable_slots_.Add(range, zone());
1726 }
1727 }
1728
1729
1730 LOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) {
1731 if (reusable_slots_.is_empty()) return NULL;
1732 if (reusable_slots_.first()->End().Value() >
1733 range->TopLevel()->Start().Value()) {
1734 return NULL;
1735 }
1736 LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand();
1737 reusable_slots_.Remove(0);
1738 return result;
1739 }
1740
1741
1742 void LAllocator::ActiveToHandled(LiveRange* range) { 1972 void LAllocator::ActiveToHandled(LiveRange* range) {
1743 ASSERT(active_live_ranges_.Contains(range)); 1973 ASSERT(active_live_ranges_.Contains(range));
1744 active_live_ranges_.RemoveElement(range); 1974 active_live_ranges_.RemoveElement(range);
1745 TraceAlloc("Moving live range %d from active to handled\n", range->id()); 1975 TraceAlloc("Moving live range %d from active to handled\n", range->id());
1746 FreeSpillSlot(range);
1747 } 1976 }
1748 1977
1749 1978
1750 void LAllocator::ActiveToInactive(LiveRange* range) { 1979 void LAllocator::ActiveToInactive(LiveRange* range) {
1751 ASSERT(active_live_ranges_.Contains(range)); 1980 ASSERT(active_live_ranges_.Contains(range));
1752 active_live_ranges_.RemoveElement(range); 1981 active_live_ranges_.RemoveElement(range);
1753 inactive_live_ranges_.Add(range, zone()); 1982 inactive_live_ranges_.Add(range, zone());
1754 TraceAlloc("Moving live range %d from active to inactive\n", range->id()); 1983 TraceAlloc("Moving live range %d from active to inactive\n", range->id());
1755 } 1984 }
1756 1985
1757 1986
1758 void LAllocator::InactiveToHandled(LiveRange* range) { 1987 void LAllocator::InactiveToHandled(LiveRange* range) {
1759 ASSERT(inactive_live_ranges_.Contains(range)); 1988 ASSERT(inactive_live_ranges_.Contains(range));
1760 inactive_live_ranges_.RemoveElement(range); 1989 inactive_live_ranges_.RemoveElement(range);
1761 TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); 1990 TraceAlloc("Moving live range %d from inactive to handled\n", range->id());
1762 FreeSpillSlot(range);
1763 } 1991 }
1764 1992
1765 1993
1766 void LAllocator::InactiveToActive(LiveRange* range) { 1994 void LAllocator::InactiveToActive(LiveRange* range) {
1767 ASSERT(inactive_live_ranges_.Contains(range)); 1995 ASSERT(inactive_live_ranges_.Contains(range));
1768 inactive_live_ranges_.RemoveElement(range); 1996 inactive_live_ranges_.RemoveElement(range);
1769 active_live_ranges_.Add(range, zone()); 1997 active_live_ranges_.Add(range, zone());
1770 TraceAlloc("Moving live range %d from inactive to active\n", range->id()); 1998 TraceAlloc("Moving live range %d from inactive to active\n", range->id());
1771 } 1999 }
1772 2000
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after
1836 } 2064 }
1837 2065
1838 if (pos.Value() < current->End().Value()) { 2066 if (pos.Value() < current->End().Value()) {
1839 // Register reg is available at the range start but becomes blocked before 2067 // Register reg is available at the range start but becomes blocked before
1840 // the range end. Split current at position where it becomes blocked. 2068 // the range end. Split current at position where it becomes blocked.
1841 LiveRange* tail = SplitRangeAt(current, pos); 2069 LiveRange* tail = SplitRangeAt(current, pos);
1842 if (!AllocationOk()) return false; 2070 if (!AllocationOk()) return false;
1843 AddToUnhandledSorted(tail); 2071 AddToUnhandledSorted(tail);
1844 } 2072 }
1845 2073
1846
1847 // Register reg is available at the range start and is free until 2074 // Register reg is available at the range start and is free until
1848 // the range end. 2075 // the range end.
1849 ASSERT(pos.Value() >= current->End().Value()); 2076 ASSERT(pos.Value() >= current->End().Value());
1850 TraceAlloc("Assigning free reg %s to live range %d\n", 2077 TraceAlloc("Assigning free reg %s to live range %d\n",
1851 RegisterName(reg), 2078 RegisterName(reg),
1852 current->id()); 2079 current->id());
1853 SetLiveRangeAssignedRegister(current, reg); 2080 SetLiveRangeAssignedRegister(current, reg);
1854 2081
1855 return true; 2082 return true;
1856 } 2083 }
(...skipping 287 matching lines...) Expand 10 before | Expand all | Expand 10 after
2144 } 2371 }
2145 } 2372 }
2146 2373
2147 2374
2148 void LAllocator::Spill(LiveRange* range) { 2375 void LAllocator::Spill(LiveRange* range) {
2149 ASSERT(!range->IsSpilled()); 2376 ASSERT(!range->IsSpilled());
2150 TraceAlloc("Spilling live range %d\n", range->id()); 2377 TraceAlloc("Spilling live range %d\n", range->id());
2151 LiveRange* first = range->TopLevel(); 2378 LiveRange* first = range->TopLevel();
2152 2379
2153 if (!first->HasAllocatedSpillOperand()) { 2380 if (!first->HasAllocatedSpillOperand()) {
2154 LOperand* op = TryReuseSpillSlot(range); 2381 AssignSpillRangeToLiveRange(first);
2155 if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind());
2156 first->SetSpillOperand(op);
2157 } 2382 }
2158 range->MakeSpilled(chunk()->zone()); 2383 range->MakeSpilled(chunk()->zone());
2159 } 2384 }
2160 2385
2161 2386
2162 int LAllocator::RegisterCount() const { 2387 int LAllocator::RegisterCount() const {
2163 return num_registers_; 2388 return num_registers_;
2164 } 2389 }
2165 2390
2166 2391
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after
2200 isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); 2425 isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_);
2201 } 2426 }
2202 2427
2203 #ifdef DEBUG 2428 #ifdef DEBUG
2204 if (allocator_ != NULL) allocator_->Verify(); 2429 if (allocator_ != NULL) allocator_->Verify();
2205 #endif 2430 #endif
2206 } 2431 }
2207 2432
2208 2433
2209 } } // namespace v8::internal 2434 } } // namespace v8::internal
OLDNEW
« src/lithium-allocator.h ('K') | « src/lithium-allocator.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698