OLD | NEW |
---|---|
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 Loading... | |
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 |
OLD | NEW |