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 | 6 |
7 #include "src/hydrogen.h" | 7 #include "src/hydrogen.h" |
8 #include "src/lithium-inl.h" | 8 #include "src/lithium-inl.h" |
9 #include "src/lithium-allocator-inl.h" | 9 #include "src/lithium-allocator-inl.h" |
10 #include "src/string-stream.h" | 10 #include "src/string-stream.h" |
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
102 assigned_register_(kInvalidAssignment), | 102 assigned_register_(kInvalidAssignment), |
103 last_interval_(NULL), | 103 last_interval_(NULL), |
104 first_interval_(NULL), | 104 first_interval_(NULL), |
105 first_pos_(NULL), | 105 first_pos_(NULL), |
106 parent_(NULL), | 106 parent_(NULL), |
107 next_(NULL), | 107 next_(NULL), |
108 current_interval_(NULL), | 108 current_interval_(NULL), |
109 last_processed_use_(NULL), | 109 last_processed_use_(NULL), |
110 current_hint_operand_(NULL), | 110 current_hint_operand_(NULL), |
111 spill_operand_(new (zone) LOperand()), | 111 spill_operand_(new (zone) LOperand()), |
112 spill_start_index_(kMaxInt) {} | 112 spill_start_index_(kMaxInt), |
| 113 spill_range_(NULL) {} |
113 | 114 |
114 | 115 |
115 void LiveRange::set_assigned_register(int reg, Zone* zone) { | 116 void LiveRange::set_assigned_register(int reg, Zone* zone) { |
116 DCHECK(!HasRegisterAssigned() && !IsSpilled()); | 117 DCHECK(!HasRegisterAssigned() && !IsSpilled()); |
117 assigned_register_ = reg; | 118 assigned_register_ = reg; |
118 ConvertOperands(zone); | 119 ConvertOperands(zone); |
119 } | 120 } |
120 | 121 |
121 | 122 |
122 void LiveRange::MakeSpilled(Zone* zone) { | 123 void LiveRange::MakeSpilled(Zone* zone) { |
123 DCHECK(!IsSpilled()); | 124 DCHECK(!IsSpilled()); |
124 DCHECK(TopLevel()->HasAllocatedSpillOperand()); | 125 DCHECK(TopLevel()->HasAllocatedSpillOperand()); |
125 spilled_ = true; | 126 spilled_ = true; |
126 assigned_register_ = kInvalidAssignment; | 127 assigned_register_ = kInvalidAssignment; |
127 ConvertOperands(zone); | 128 if (spill_range_ == NULL) { |
| 129 ConvertOperands(zone); |
| 130 } |
128 } | 131 } |
129 | 132 |
130 | 133 |
131 bool LiveRange::HasAllocatedSpillOperand() const { | 134 bool LiveRange::HasAllocatedSpillOperand() const { |
132 DCHECK(spill_operand_ != NULL); | 135 DCHECK(spill_operand_ != NULL); |
133 return !spill_operand_->IsIgnored(); | 136 return !spill_operand_->IsIgnored() || spill_range_ != NULL; |
134 } | 137 } |
135 | 138 |
136 | 139 |
137 void LiveRange::SetSpillOperand(LOperand* operand) { | 140 void LiveRange::SetSpillOperand(LOperand* operand) { |
138 DCHECK(!operand->IsUnallocated()); | 141 DCHECK(!operand->IsUnallocated()); |
139 DCHECK(spill_operand_ != NULL); | 142 DCHECK(spill_operand_ != NULL); |
140 DCHECK(spill_operand_->IsIgnored()); | 143 DCHECK(spill_operand_->IsIgnored()); |
141 spill_operand_->ConvertTo(operand->kind(), operand->index()); | 144 spill_operand_->ConvertTo(operand->kind(), operand->index()); |
142 } | 145 } |
143 | 146 |
144 | 147 |
| 148 void LiveRange::CommitSpillOperand(LOperand* operand) { |
| 149 DCHECK(spill_range_ != NULL); |
| 150 DCHECK(!IsChild()); |
| 151 spill_range_ = NULL; |
| 152 SetSpillOperand(operand); |
| 153 for (LiveRange* range = this; range != NULL; range = range->next()) { |
| 154 if (range->IsSpilled()) { |
| 155 range->ConvertUsesToOperand(operand); |
| 156 } |
| 157 } |
| 158 } |
| 159 |
| 160 |
145 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) { | 161 UsePosition* LiveRange::NextUsePosition(LifetimePosition start) { |
146 UsePosition* use_pos = last_processed_use_; | 162 UsePosition* use_pos = last_processed_use_; |
147 if (use_pos == NULL) use_pos = first_pos(); | 163 if (use_pos == NULL) use_pos = first_pos(); |
148 while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { | 164 while (use_pos != NULL && use_pos->pos().Value() < start.Value()) { |
149 use_pos = use_pos->next(); | 165 use_pos = use_pos->next(); |
150 } | 166 } |
151 last_processed_use_ = use_pos; | 167 last_processed_use_ = use_pos; |
152 return use_pos; | 168 return use_pos; |
153 } | 169 } |
154 | 170 |
(...skipping 284 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
439 use_pos->next_ = prev->next_; | 455 use_pos->next_ = prev->next_; |
440 prev->next_ = use_pos; | 456 prev->next_ = use_pos; |
441 } | 457 } |
442 | 458 |
443 if (prev_hint == NULL && use_pos->HasHint()) { | 459 if (prev_hint == NULL && use_pos->HasHint()) { |
444 current_hint_operand_ = hint; | 460 current_hint_operand_ = hint; |
445 } | 461 } |
446 } | 462 } |
447 | 463 |
448 | 464 |
449 void LiveRange::ConvertOperands(Zone* zone) { | 465 void LiveRange::ConvertUsesToOperand(LOperand* op) { |
450 LOperand* op = CreateAssignedOperand(zone); | |
451 UsePosition* use_pos = first_pos(); | 466 UsePosition* use_pos = first_pos(); |
452 while (use_pos != NULL) { | 467 while (use_pos != NULL) { |
453 DCHECK(Start().Value() <= use_pos->pos().Value() && | 468 DCHECK(Start().Value() <= use_pos->pos().Value() && |
454 use_pos->pos().Value() <= End().Value()); | 469 use_pos->pos().Value() <= End().Value()); |
455 | 470 |
456 if (use_pos->HasOperand()) { | 471 if (use_pos->HasOperand()) { |
457 DCHECK(op->IsRegister() || op->IsDoubleRegister() || | 472 DCHECK(op->IsRegister() || op->IsDoubleRegister() || |
458 !use_pos->RequiresRegister()); | 473 !use_pos->RequiresRegister()); |
459 use_pos->operand()->ConvertTo(op->kind(), op->index()); | 474 use_pos->operand()->ConvertTo(op->kind(), op->index()); |
460 } | 475 } |
461 use_pos = use_pos->next(); | 476 use_pos = use_pos->next(); |
462 } | 477 } |
463 } | 478 } |
464 | 479 |
465 | 480 |
| 481 void LiveRange::ConvertOperands(Zone* zone) { |
| 482 LOperand* op = CreateAssignedOperand(zone); |
| 483 ConvertUsesToOperand(op); |
| 484 } |
| 485 |
| 486 |
466 bool LiveRange::CanCover(LifetimePosition position) const { | 487 bool LiveRange::CanCover(LifetimePosition position) const { |
467 if (IsEmpty()) return false; | 488 if (IsEmpty()) return false; |
468 return Start().Value() <= position.Value() && | 489 return Start().Value() <= position.Value() && |
469 position.Value() < End().Value(); | 490 position.Value() < End().Value(); |
470 } | 491 } |
471 | 492 |
472 | 493 |
473 bool LiveRange::Covers(LifetimePosition position) { | 494 bool LiveRange::Covers(LifetimePosition position) { |
474 if (!CanCover(position)) return false; | 495 if (!CanCover(position)) return false; |
475 UseInterval* start_search = FirstSearchIntervalForPosition(position); | 496 UseInterval* start_search = FirstSearchIntervalForPosition(position); |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
514 : zone_(graph->isolate()), | 535 : zone_(graph->isolate()), |
515 chunk_(NULL), | 536 chunk_(NULL), |
516 live_in_sets_(graph->blocks()->length(), zone()), | 537 live_in_sets_(graph->blocks()->length(), zone()), |
517 live_ranges_(num_values * 2, zone()), | 538 live_ranges_(num_values * 2, zone()), |
518 fixed_live_ranges_(NULL), | 539 fixed_live_ranges_(NULL), |
519 fixed_double_live_ranges_(NULL), | 540 fixed_double_live_ranges_(NULL), |
520 unhandled_live_ranges_(num_values * 2, zone()), | 541 unhandled_live_ranges_(num_values * 2, zone()), |
521 active_live_ranges_(8, zone()), | 542 active_live_ranges_(8, zone()), |
522 inactive_live_ranges_(8, zone()), | 543 inactive_live_ranges_(8, zone()), |
523 reusable_slots_(8, zone()), | 544 reusable_slots_(8, zone()), |
| 545 spill_ranges_(8, zone()), |
524 next_virtual_register_(num_values), | 546 next_virtual_register_(num_values), |
525 first_artificial_register_(num_values), | 547 first_artificial_register_(num_values), |
526 mode_(UNALLOCATED_REGISTERS), | 548 mode_(UNALLOCATED_REGISTERS), |
527 num_registers_(-1), | 549 num_registers_(-1), |
528 graph_(graph), | 550 graph_(graph), |
529 has_osr_entry_(false), | 551 has_osr_entry_(false), |
530 allocation_ok_(true) {} | 552 allocation_ok_(true) {} |
531 | 553 |
532 | 554 |
533 void LAllocator::InitializeLivenessAnalysis() { | 555 void LAllocator::InitializeLivenessAnalysis() { |
(...skipping 475 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1009 index = index - 1; | 1031 index = index - 1; |
1010 } | 1032 } |
1011 } | 1033 } |
1012 | 1034 |
1013 | 1035 |
1014 void LAllocator::ResolvePhis(HBasicBlock* block) { | 1036 void LAllocator::ResolvePhis(HBasicBlock* block) { |
1015 const ZoneList<HPhi*>* phis = block->phis(); | 1037 const ZoneList<HPhi*>* phis = block->phis(); |
1016 for (int i = 0; i < phis->length(); ++i) { | 1038 for (int i = 0; i < phis->length(); ++i) { |
1017 HPhi* phi = phis->at(i); | 1039 HPhi* phi = phis->at(i); |
1018 LUnallocated* phi_operand = | 1040 LUnallocated* phi_operand = |
1019 new (chunk()->zone()) LUnallocated(LUnallocated::NONE); | 1041 new (chunk()->zone()) LUnallocated(LUnallocated::ANY); |
1020 phi_operand->set_virtual_register(phi->id()); | 1042 phi_operand->set_virtual_register(phi->id()); |
1021 for (int j = 0; j < phi->OperandCount(); ++j) { | 1043 for (int j = 0; j < phi->OperandCount(); ++j) { |
1022 HValue* op = phi->OperandAt(j); | 1044 HValue* op = phi->OperandAt(j); |
1023 LOperand* operand = NULL; | 1045 LOperand* operand = NULL; |
1024 if (op->IsConstant() && op->EmitAtUses()) { | 1046 if (op->IsConstant() && op->EmitAtUses()) { |
1025 HConstant* constant = HConstant::cast(op); | 1047 HConstant* constant = HConstant::cast(op); |
1026 operand = chunk_->DefineConstantOperand(constant); | 1048 operand = chunk_->DefineConstantOperand(constant); |
1027 } else { | 1049 } else { |
1028 DCHECK(!op->EmitAtUses()); | 1050 DCHECK(!op->EmitAtUses()); |
1029 LUnallocated* unalloc = | 1051 LUnallocated* unalloc = |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1076 new(chunk->zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), | 1098 new(chunk->zone()) BitVector(DoubleRegister::NumAllocatableRegisters(), |
1077 chunk->zone()); | 1099 chunk->zone()); |
1078 MeetRegisterConstraints(); | 1100 MeetRegisterConstraints(); |
1079 if (!AllocationOk()) return false; | 1101 if (!AllocationOk()) return false; |
1080 ResolvePhis(); | 1102 ResolvePhis(); |
1081 BuildLiveRanges(); | 1103 BuildLiveRanges(); |
1082 AllocateGeneralRegisters(); | 1104 AllocateGeneralRegisters(); |
1083 if (!AllocationOk()) return false; | 1105 if (!AllocationOk()) return false; |
1084 AllocateDoubleRegisters(); | 1106 AllocateDoubleRegisters(); |
1085 if (!AllocationOk()) return false; | 1107 if (!AllocationOk()) return false; |
| 1108 ReuseSpillSlots(); |
1086 PopulatePointerMaps(); | 1109 PopulatePointerMaps(); |
1087 ConnectRanges(); | 1110 ConnectRanges(); |
1088 ResolveControlFlow(); | 1111 ResolveControlFlow(); |
1089 return true; | 1112 return true; |
1090 } | 1113 } |
1091 | 1114 |
1092 | 1115 |
| 1116 static bool AreUseIntervalsIntersecting(UseInterval* interval1, |
| 1117 UseInterval* interval2) { |
| 1118 while (interval1 != NULL && interval2 != NULL) { |
| 1119 if (interval1->start().Value() < interval2->start().Value()) { |
| 1120 if (interval1->end().Value() > interval2->start().Value()) { |
| 1121 return true; |
| 1122 } |
| 1123 interval1 = interval1->next(); |
| 1124 } else { |
| 1125 if (interval2->end().Value() > interval1->start().Value()) { |
| 1126 return true; |
| 1127 } |
| 1128 interval2 = interval2->next(); |
| 1129 } |
| 1130 } |
| 1131 return false; |
| 1132 } |
| 1133 |
| 1134 |
| 1135 SpillRange::SpillRange(LiveRange* range, int id, Zone* zone) |
| 1136 : id_(id), live_ranges_(1, zone), end_position_(range->End()) { |
| 1137 UseInterval* src = range->first_interval(); |
| 1138 UseInterval* result = NULL; |
| 1139 UseInterval* node = NULL; |
| 1140 // Copy the nodes |
| 1141 while (src != NULL) { |
| 1142 UseInterval* new_node = new (zone) UseInterval(src->start(), src->end()); |
| 1143 if (result == NULL) { |
| 1144 result = new_node; |
| 1145 } else { |
| 1146 node->set_next(new_node); |
| 1147 } |
| 1148 node = new_node; |
| 1149 src = src->next(); |
| 1150 } |
| 1151 use_interval_ = result; |
| 1152 live_ranges_.Add(range, zone); |
| 1153 DCHECK(range->GetSpillRange() == NULL); |
| 1154 range->SetSpillRange(this); |
| 1155 } |
| 1156 |
| 1157 |
| 1158 bool SpillRange::IsIntersectingWith(SpillRange* other) { |
| 1159 if (End().Value() <= other->use_interval_->start().Value() || |
| 1160 other->End().Value() <= use_interval_->start().Value()) { |
| 1161 return false; |
| 1162 } |
| 1163 return AreUseIntervalsIntersecting(use_interval_, other->use_interval_); |
| 1164 } |
| 1165 |
| 1166 |
| 1167 bool SpillRange::TryMerge(SpillRange* other, Zone* zone) { |
| 1168 if (Kind() == other->Kind() && |
| 1169 !AreUseIntervalsIntersecting(use_interval_, other->use_interval_)) { |
| 1170 if (End().Value() < other->End().Value()) { |
| 1171 end_position_ = other->End(); |
| 1172 } |
| 1173 |
| 1174 MergeDisjointIntervals(other->use_interval_, zone); |
| 1175 other->use_interval_ = NULL; |
| 1176 |
| 1177 for (int i = 0; i < other->live_ranges_.length(); i++) { |
| 1178 DCHECK(other->live_ranges_.at(i)->GetSpillRange() == other); |
| 1179 other->live_ranges_.at(i)->SetSpillRange(this); |
| 1180 } |
| 1181 |
| 1182 live_ranges_.AddAll(other->live_ranges_, zone); |
| 1183 other->live_ranges_.Clear(); |
| 1184 |
| 1185 return true; |
| 1186 } |
| 1187 return false; |
| 1188 } |
| 1189 |
| 1190 |
| 1191 void SpillRange::SetOperand(LOperand* op) { |
| 1192 for (int i = 0; i < live_ranges_.length(); i++) { |
| 1193 DCHECK(live_ranges_.at(i)->GetSpillRange() == this); |
| 1194 live_ranges_.at(i)->CommitSpillOperand(op); |
| 1195 } |
| 1196 } |
| 1197 |
| 1198 |
| 1199 void SpillRange::MergeDisjointIntervals(UseInterval* other, Zone* zone) { |
| 1200 UseInterval* tail = NULL; |
| 1201 UseInterval* current = use_interval_; |
| 1202 while (other != NULL) { |
| 1203 // Make sure the 'current' list starts first |
| 1204 if (current == NULL || current->start().Value() > other->start().Value()) { |
| 1205 std::swap(current, other); |
| 1206 } |
| 1207 |
| 1208 // Check disjointness |
| 1209 DCHECK(other == NULL || current->end().Value() <= other->start().Value()); |
| 1210 |
| 1211 // Append the 'current' node to the result accumulator and move forward |
| 1212 if (tail == NULL) { |
| 1213 use_interval_ = current; |
| 1214 } else { |
| 1215 tail->set_next(current); |
| 1216 } |
| 1217 tail = current; |
| 1218 current = current->next(); |
| 1219 } |
| 1220 // Other list is empty => we are done |
| 1221 } |
| 1222 |
| 1223 |
| 1224 void LAllocator::ReuseSpillSlots() { |
| 1225 // Merge disjoint spill ranges |
| 1226 for (int i = 0; i < spill_ranges_.length(); i++) { |
| 1227 SpillRange* range = spill_ranges_.at(i); |
| 1228 if (!range->IsEmpty()) { |
| 1229 for (int j = i + 1; j < spill_ranges_.length(); j++) { |
| 1230 SpillRange* other = spill_ranges_.at(j); |
| 1231 if (!other->IsEmpty()) { |
| 1232 range->TryMerge(spill_ranges_.at(j), zone()); |
| 1233 } |
| 1234 } |
| 1235 } |
| 1236 } |
| 1237 |
| 1238 // Allocate slots for the merged spill ranges. |
| 1239 for (int i = 0; i < spill_ranges_.length(); i++) { |
| 1240 SpillRange* range = spill_ranges_.at(i); |
| 1241 if (!range->IsEmpty()) { |
| 1242 LOperand* op = chunk_->GetNextSpillSlot(range->Kind()); |
| 1243 range->SetOperand(op); |
| 1244 } |
| 1245 } |
| 1246 } |
| 1247 |
| 1248 |
1093 void LAllocator::MeetRegisterConstraints() { | 1249 void LAllocator::MeetRegisterConstraints() { |
1094 LAllocatorPhase phase("L_Register constraints", this); | 1250 LAllocatorPhase phase("L_Register constraints", this); |
1095 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1251 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1096 for (int i = 0; i < blocks->length(); ++i) { | 1252 for (int i = 0; i < blocks->length(); ++i) { |
1097 HBasicBlock* block = blocks->at(i); | 1253 HBasicBlock* block = blocks->at(i); |
1098 MeetRegisterConstraints(block); | 1254 MeetRegisterConstraints(block); |
1099 if (!AllocationOk()) return; | 1255 if (!AllocationOk()) return; |
1100 } | 1256 } |
1101 } | 1257 } |
1102 | 1258 |
(...skipping 370 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1473 | 1629 |
1474 | 1630 |
1475 void LAllocator::AllocateDoubleRegisters() { | 1631 void LAllocator::AllocateDoubleRegisters() { |
1476 LAllocatorPhase phase("L_Allocate double registers", this); | 1632 LAllocatorPhase phase("L_Allocate double registers", this); |
1477 num_registers_ = DoubleRegister::NumAllocatableRegisters(); | 1633 num_registers_ = DoubleRegister::NumAllocatableRegisters(); |
1478 mode_ = DOUBLE_REGISTERS; | 1634 mode_ = DOUBLE_REGISTERS; |
1479 AllocateRegisters(); | 1635 AllocateRegisters(); |
1480 } | 1636 } |
1481 | 1637 |
1482 | 1638 |
| 1639 bool LAllocator::TryReuseSpillForPhi(LiveRange* range) { |
| 1640 DCHECK(!range->HasAllocatedSpillOperand()); |
| 1641 if (range->IsChild()) { |
| 1642 return false; |
| 1643 } |
| 1644 HValue* instr = graph_->LookupValue(range->id()); |
| 1645 if (instr == NULL || !instr->IsPhi()) { |
| 1646 return false; |
| 1647 } |
| 1648 |
| 1649 // Count the number of spilled operands. |
| 1650 HPhi* phi = HPhi::cast(instr); |
| 1651 int spilled_count = 0; |
| 1652 LiveRange* first_op = NULL; |
| 1653 for (int i = 0; i < phi->OperandCount(); i++) { |
| 1654 HValue* op = phi->OperandAt(i); |
| 1655 LiveRange* op_range = LiveRangeFor(op->id()); |
| 1656 if (op_range->GetSpillRange() != NULL) { |
| 1657 HBasicBlock* pred = instr->block()->predecessors()->at(i); |
| 1658 LifetimePosition pred_end = LifetimePosition::FromInstructionIndex( |
| 1659 pred->last_instruction_index()); |
| 1660 while (op_range != NULL && !op_range->CanCover(pred_end)) { |
| 1661 op_range = op_range->next(); |
| 1662 } |
| 1663 if (op_range != NULL && op_range->IsSpilled()) { |
| 1664 spilled_count++; |
| 1665 if (first_op == NULL) { |
| 1666 first_op = op_range->TopLevel(); |
| 1667 } |
| 1668 } |
| 1669 } |
| 1670 } |
| 1671 |
| 1672 // Only continue if more than half of the operands are spilled. |
| 1673 if (spilled_count * 2 <= phi->OperandCount()) { |
| 1674 return false; |
| 1675 } |
| 1676 |
| 1677 // Try to merge the spilled operands and count the number of merged spilled |
| 1678 // operands. |
| 1679 DCHECK(first_op != NULL); |
| 1680 SpillRange* first_op_spill = first_op->GetSpillRange(); |
| 1681 int num_merged = 1; |
| 1682 for (int i = 1; i < phi->OperandCount(); i++) { |
| 1683 HValue* op = phi->OperandAt(i); |
| 1684 LiveRange* op_range = LiveRangeFor(op->id()); |
| 1685 SpillRange* op_spill = op_range->GetSpillRange(); |
| 1686 if (op_spill != NULL) { |
| 1687 if (op_spill->id() == first_op_spill->id() || |
| 1688 first_op_spill->TryMerge(op_spill, zone())) { |
| 1689 num_merged++; |
| 1690 } |
| 1691 } |
| 1692 } |
| 1693 |
| 1694 // Only continue if enough operands could be merged to the |
| 1695 // same spill slot. |
| 1696 if (num_merged * 2 <= phi->OperandCount() || |
| 1697 AreUseIntervalsIntersecting(first_op_spill->interval(), |
| 1698 range->first_interval())) { |
| 1699 return false; |
| 1700 } |
| 1701 |
| 1702 // If the range does not need register soon, spill it to the merged |
| 1703 // spill range. |
| 1704 LifetimePosition next_pos = range->Start(); |
| 1705 if (IsGapAt(next_pos.InstructionIndex())) { |
| 1706 next_pos = next_pos.NextInstruction(); |
| 1707 } |
| 1708 UsePosition* pos = range->NextUsePositionRegisterIsBeneficial(next_pos); |
| 1709 if (pos == NULL) { |
| 1710 SpillRange* spill_range = AssignSpillRangeToLiveRange(range->TopLevel()); |
| 1711 CHECK(first_op_spill->TryMerge(spill_range, zone())); |
| 1712 Spill(range); |
| 1713 return true; |
| 1714 } else if (pos->pos().Value() > range->Start().NextInstruction().Value()) { |
| 1715 SpillRange* spill_range = AssignSpillRangeToLiveRange(range->TopLevel()); |
| 1716 CHECK(first_op_spill->TryMerge(spill_range, zone())); |
| 1717 SpillBetween(range, range->Start(), pos->pos()); |
| 1718 if (!AllocationOk()) return false; |
| 1719 DCHECK(UnhandledIsSorted()); |
| 1720 return true; |
| 1721 } |
| 1722 |
| 1723 return false; |
| 1724 } |
| 1725 |
| 1726 |
| 1727 SpillRange* LAllocator::AssignSpillRangeToLiveRange(LiveRange* range) { |
| 1728 int spill_id = spill_ranges_.length(); |
| 1729 SpillRange* spill_range = new (zone()) SpillRange(range, spill_id, zone()); |
| 1730 spill_ranges_.Add(spill_range, zone()); |
| 1731 return spill_range; |
| 1732 } |
| 1733 |
| 1734 |
1483 void LAllocator::AllocateRegisters() { | 1735 void LAllocator::AllocateRegisters() { |
1484 DCHECK(unhandled_live_ranges_.is_empty()); | 1736 DCHECK(unhandled_live_ranges_.is_empty()); |
1485 | 1737 |
1486 for (int i = 0; i < live_ranges_.length(); ++i) { | 1738 for (int i = 0; i < live_ranges_.length(); ++i) { |
1487 if (live_ranges_[i] != NULL) { | 1739 if (live_ranges_[i] != NULL) { |
1488 if (live_ranges_[i]->Kind() == mode_) { | 1740 if (live_ranges_[i]->Kind() == mode_) { |
1489 AddToUnhandledUnsorted(live_ranges_[i]); | 1741 AddToUnhandledUnsorted(live_ranges_[i]); |
1490 } | 1742 } |
1491 } | 1743 } |
1492 } | 1744 } |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1542 current->Start().NextInstruction().Value()) { | 1794 current->Start().NextInstruction().Value()) { |
1543 // Do not spill live range eagerly if use position that can benefit from | 1795 // Do not spill live range eagerly if use position that can benefit from |
1544 // the register is too close to the start of live range. | 1796 // the register is too close to the start of live range. |
1545 SpillBetween(current, current->Start(), pos->pos()); | 1797 SpillBetween(current, current->Start(), pos->pos()); |
1546 if (!AllocationOk()) return; | 1798 if (!AllocationOk()) return; |
1547 DCHECK(UnhandledIsSorted()); | 1799 DCHECK(UnhandledIsSorted()); |
1548 continue; | 1800 continue; |
1549 } | 1801 } |
1550 } | 1802 } |
1551 | 1803 |
| 1804 if (TryReuseSpillForPhi(current)) { |
| 1805 continue; |
| 1806 } |
| 1807 if (!AllocationOk()) return; |
| 1808 |
1552 for (int i = 0; i < active_live_ranges_.length(); ++i) { | 1809 for (int i = 0; i < active_live_ranges_.length(); ++i) { |
1553 LiveRange* cur_active = active_live_ranges_.at(i); | 1810 LiveRange* cur_active = active_live_ranges_.at(i); |
1554 if (cur_active->End().Value() <= position.Value()) { | 1811 if (cur_active->End().Value() <= position.Value()) { |
1555 ActiveToHandled(cur_active); | 1812 ActiveToHandled(cur_active); |
1556 --i; // The live range was removed from the list of active live ranges. | 1813 --i; // The live range was removed from the list of active live ranges. |
1557 } else if (!cur_active->Covers(position)) { | 1814 } else if (!cur_active->Covers(position)) { |
1558 ActiveToInactive(cur_active); | 1815 ActiveToInactive(cur_active); |
1559 --i; // The live range was removed from the list of active live ranges. | 1816 --i; // The live range was removed from the list of active live ranges. |
1560 } | 1817 } |
1561 } | 1818 } |
(...skipping 130 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1692 int len = unhandled_live_ranges_.length(); | 1949 int len = unhandled_live_ranges_.length(); |
1693 for (int i = 1; i < len; i++) { | 1950 for (int i = 1; i < len; i++) { |
1694 LiveRange* a = unhandled_live_ranges_.at(i - 1); | 1951 LiveRange* a = unhandled_live_ranges_.at(i - 1); |
1695 LiveRange* b = unhandled_live_ranges_.at(i); | 1952 LiveRange* b = unhandled_live_ranges_.at(i); |
1696 if (a->Start().Value() < b->Start().Value()) return false; | 1953 if (a->Start().Value() < b->Start().Value()) return false; |
1697 } | 1954 } |
1698 return true; | 1955 return true; |
1699 } | 1956 } |
1700 | 1957 |
1701 | 1958 |
1702 void LAllocator::FreeSpillSlot(LiveRange* range) { | |
1703 // Check that we are the last range. | |
1704 if (range->next() != NULL) return; | |
1705 | |
1706 if (!range->TopLevel()->HasAllocatedSpillOperand()) return; | |
1707 | |
1708 int index = range->TopLevel()->GetSpillOperand()->index(); | |
1709 if (index >= 0) { | |
1710 reusable_slots_.Add(range, zone()); | |
1711 } | |
1712 } | |
1713 | |
1714 | |
1715 LOperand* LAllocator::TryReuseSpillSlot(LiveRange* range) { | |
1716 if (reusable_slots_.is_empty()) return NULL; | |
1717 if (reusable_slots_.first()->End().Value() > | |
1718 range->TopLevel()->Start().Value()) { | |
1719 return NULL; | |
1720 } | |
1721 LOperand* result = reusable_slots_.first()->TopLevel()->GetSpillOperand(); | |
1722 reusable_slots_.Remove(0); | |
1723 return result; | |
1724 } | |
1725 | |
1726 | |
1727 void LAllocator::ActiveToHandled(LiveRange* range) { | 1959 void LAllocator::ActiveToHandled(LiveRange* range) { |
1728 DCHECK(active_live_ranges_.Contains(range)); | 1960 DCHECK(active_live_ranges_.Contains(range)); |
1729 active_live_ranges_.RemoveElement(range); | 1961 active_live_ranges_.RemoveElement(range); |
1730 TraceAlloc("Moving live range %d from active to handled\n", range->id()); | 1962 TraceAlloc("Moving live range %d from active to handled\n", range->id()); |
1731 FreeSpillSlot(range); | |
1732 } | 1963 } |
1733 | 1964 |
1734 | 1965 |
1735 void LAllocator::ActiveToInactive(LiveRange* range) { | 1966 void LAllocator::ActiveToInactive(LiveRange* range) { |
1736 DCHECK(active_live_ranges_.Contains(range)); | 1967 DCHECK(active_live_ranges_.Contains(range)); |
1737 active_live_ranges_.RemoveElement(range); | 1968 active_live_ranges_.RemoveElement(range); |
1738 inactive_live_ranges_.Add(range, zone()); | 1969 inactive_live_ranges_.Add(range, zone()); |
1739 TraceAlloc("Moving live range %d from active to inactive\n", range->id()); | 1970 TraceAlloc("Moving live range %d from active to inactive\n", range->id()); |
1740 } | 1971 } |
1741 | 1972 |
1742 | 1973 |
1743 void LAllocator::InactiveToHandled(LiveRange* range) { | 1974 void LAllocator::InactiveToHandled(LiveRange* range) { |
1744 DCHECK(inactive_live_ranges_.Contains(range)); | 1975 DCHECK(inactive_live_ranges_.Contains(range)); |
1745 inactive_live_ranges_.RemoveElement(range); | 1976 inactive_live_ranges_.RemoveElement(range); |
1746 TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); | 1977 TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); |
1747 FreeSpillSlot(range); | |
1748 } | 1978 } |
1749 | 1979 |
1750 | 1980 |
1751 void LAllocator::InactiveToActive(LiveRange* range) { | 1981 void LAllocator::InactiveToActive(LiveRange* range) { |
1752 DCHECK(inactive_live_ranges_.Contains(range)); | 1982 DCHECK(inactive_live_ranges_.Contains(range)); |
1753 inactive_live_ranges_.RemoveElement(range); | 1983 inactive_live_ranges_.RemoveElement(range); |
1754 active_live_ranges_.Add(range, zone()); | 1984 active_live_ranges_.Add(range, zone()); |
1755 TraceAlloc("Moving live range %d from inactive to active\n", range->id()); | 1985 TraceAlloc("Moving live range %d from inactive to active\n", range->id()); |
1756 } | 1986 } |
1757 | 1987 |
(...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1821 } | 2051 } |
1822 | 2052 |
1823 if (pos.Value() < current->End().Value()) { | 2053 if (pos.Value() < current->End().Value()) { |
1824 // Register reg is available at the range start but becomes blocked before | 2054 // Register reg is available at the range start but becomes blocked before |
1825 // the range end. Split current at position where it becomes blocked. | 2055 // the range end. Split current at position where it becomes blocked. |
1826 LiveRange* tail = SplitRangeAt(current, pos); | 2056 LiveRange* tail = SplitRangeAt(current, pos); |
1827 if (!AllocationOk()) return false; | 2057 if (!AllocationOk()) return false; |
1828 AddToUnhandledSorted(tail); | 2058 AddToUnhandledSorted(tail); |
1829 } | 2059 } |
1830 | 2060 |
1831 | |
1832 // Register reg is available at the range start and is free until | 2061 // Register reg is available at the range start and is free until |
1833 // the range end. | 2062 // the range end. |
1834 DCHECK(pos.Value() >= current->End().Value()); | 2063 DCHECK(pos.Value() >= current->End().Value()); |
1835 TraceAlloc("Assigning free reg %s to live range %d\n", | 2064 TraceAlloc("Assigning free reg %s to live range %d\n", |
1836 RegisterName(reg), | 2065 RegisterName(reg), |
1837 current->id()); | 2066 current->id()); |
1838 SetLiveRangeAssignedRegister(current, reg); | 2067 SetLiveRangeAssignedRegister(current, reg); |
1839 | 2068 |
1840 return true; | 2069 return true; |
1841 } | 2070 } |
(...skipping 287 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2129 } | 2358 } |
2130 } | 2359 } |
2131 | 2360 |
2132 | 2361 |
2133 void LAllocator::Spill(LiveRange* range) { | 2362 void LAllocator::Spill(LiveRange* range) { |
2134 DCHECK(!range->IsSpilled()); | 2363 DCHECK(!range->IsSpilled()); |
2135 TraceAlloc("Spilling live range %d\n", range->id()); | 2364 TraceAlloc("Spilling live range %d\n", range->id()); |
2136 LiveRange* first = range->TopLevel(); | 2365 LiveRange* first = range->TopLevel(); |
2137 | 2366 |
2138 if (!first->HasAllocatedSpillOperand()) { | 2367 if (!first->HasAllocatedSpillOperand()) { |
2139 LOperand* op = TryReuseSpillSlot(range); | 2368 AssignSpillRangeToLiveRange(first); |
2140 if (op == NULL) op = chunk_->GetNextSpillSlot(range->Kind()); | |
2141 first->SetSpillOperand(op); | |
2142 } | 2369 } |
2143 range->MakeSpilled(chunk()->zone()); | 2370 range->MakeSpilled(chunk()->zone()); |
2144 } | 2371 } |
2145 | 2372 |
2146 | 2373 |
2147 int LAllocator::RegisterCount() const { | 2374 int LAllocator::RegisterCount() const { |
2148 return num_registers_; | 2375 return num_registers_; |
2149 } | 2376 } |
2150 | 2377 |
2151 | 2378 |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2185 isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); | 2412 isolate()->GetHTracer()->TraceLiveRanges(name(), allocator_); |
2186 } | 2413 } |
2187 | 2414 |
2188 #ifdef DEBUG | 2415 #ifdef DEBUG |
2189 if (allocator_ != NULL) allocator_->Verify(); | 2416 if (allocator_ != NULL) allocator_->Verify(); |
2190 #endif | 2417 #endif |
2191 } | 2418 } |
2192 | 2419 |
2193 | 2420 |
2194 } } // namespace v8::internal | 2421 } } // namespace v8::internal |
OLD | NEW |