| OLD | NEW |
| 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/compiler/linkage.h" |
| 6 #include "src/compiler/pipeline-statistics.h" |
| 5 #include "src/compiler/register-allocator.h" | 7 #include "src/compiler/register-allocator.h" |
| 6 | |
| 7 #include "src/compiler/linkage.h" | |
| 8 #include "src/hydrogen.h" | |
| 9 #include "src/string-stream.h" | 8 #include "src/string-stream.h" |
| 10 | 9 |
| 11 namespace v8 { | 10 namespace v8 { |
| 12 namespace internal { | 11 namespace internal { |
| 13 namespace compiler { | 12 namespace compiler { |
| 14 | 13 |
| 15 static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { | 14 static inline LifetimePosition Min(LifetimePosition a, LifetimePosition b) { |
| 16 return a.Value() < b.Value() ? a : b; | 15 return a.Value() < b.Value() ? a : b; |
| 17 } | 16 } |
| 18 | 17 |
| (...skipping 477 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 496 } | 495 } |
| 497 } | 496 } |
| 498 return LifetimePosition::Invalid(); | 497 return LifetimePosition::Invalid(); |
| 499 } | 498 } |
| 500 | 499 |
| 501 | 500 |
| 502 RegisterAllocator::RegisterAllocator(Zone* local_zone, Frame* frame, | 501 RegisterAllocator::RegisterAllocator(Zone* local_zone, Frame* frame, |
| 503 CompilationInfo* info, | 502 CompilationInfo* info, |
| 504 InstructionSequence* code) | 503 InstructionSequence* code) |
| 505 : zone_(local_zone), | 504 : zone_(local_zone), |
| 506 zone_pool_(NULL), | |
| 507 frame_(frame), | 505 frame_(frame), |
| 508 info_(info), | 506 info_(info), |
| 509 code_(code), | 507 code_(code), |
| 510 live_in_sets_(code->InstructionBlockCount(), zone()), | 508 live_in_sets_(code->InstructionBlockCount(), zone()), |
| 511 live_ranges_(code->VirtualRegisterCount() * 2, zone()), | 509 live_ranges_(code->VirtualRegisterCount() * 2, zone()), |
| 512 fixed_live_ranges_(NULL), | 510 fixed_live_ranges_(NULL), |
| 513 fixed_double_live_ranges_(NULL), | 511 fixed_double_live_ranges_(NULL), |
| 514 unhandled_live_ranges_(code->VirtualRegisterCount() * 2, zone()), | 512 unhandled_live_ranges_(code->VirtualRegisterCount() * 2, zone()), |
| 515 active_live_ranges_(8, zone()), | 513 active_live_ranges_(8, zone()), |
| 516 inactive_live_ranges_(8, zone()), | 514 inactive_live_ranges_(8, zone()), |
| (...skipping 572 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1089 | 1087 |
| 1090 // We use the phi-ness of some nodes in some later heuristics. | 1088 // We use the phi-ness of some nodes in some later heuristics. |
| 1091 live_range->set_is_phi(true); | 1089 live_range->set_is_phi(true); |
| 1092 if (!block->IsLoopHeader()) { | 1090 if (!block->IsLoopHeader()) { |
| 1093 live_range->set_is_non_loop_phi(true); | 1091 live_range->set_is_non_loop_phi(true); |
| 1094 } | 1092 } |
| 1095 } | 1093 } |
| 1096 } | 1094 } |
| 1097 | 1095 |
| 1098 | 1096 |
| 1099 bool RegisterAllocator::Allocate(ZonePool* zone_pool) { | 1097 bool RegisterAllocator::Allocate(PipelineStatistics* stats) { |
| 1100 DCHECK_EQ(NULL, zone_pool_); | |
| 1101 zone_pool_ = zone_pool; | |
| 1102 assigned_registers_ = new (code_zone()) | 1098 assigned_registers_ = new (code_zone()) |
| 1103 BitVector(Register::NumAllocatableRegisters(), code_zone()); | 1099 BitVector(Register::NumAllocatableRegisters(), code_zone()); |
| 1104 assigned_double_registers_ = new (code_zone()) | 1100 assigned_double_registers_ = new (code_zone()) |
| 1105 BitVector(DoubleRegister::NumAllocatableAliasedRegisters(), code_zone()); | 1101 BitVector(DoubleRegister::NumAllocatableAliasedRegisters(), code_zone()); |
| 1106 MeetRegisterConstraints(); | 1102 { |
| 1103 PhaseScope phase_scope(stats, "meet register constraints"); |
| 1104 MeetRegisterConstraints(); |
| 1105 } |
| 1107 if (!AllocationOk()) return false; | 1106 if (!AllocationOk()) return false; |
| 1108 ResolvePhis(); | 1107 { |
| 1109 BuildLiveRanges(); | 1108 PhaseScope phase_scope(stats, "resolve phis"); |
| 1110 AllocateGeneralRegisters(); | 1109 ResolvePhis(); |
| 1110 } |
| 1111 { |
| 1112 PhaseScope phase_scope(stats, "build live ranges"); |
| 1113 BuildLiveRanges(); |
| 1114 } |
| 1115 { |
| 1116 PhaseScope phase_scope(stats, "allocate general registers"); |
| 1117 AllocateGeneralRegisters(); |
| 1118 } |
| 1111 if (!AllocationOk()) return false; | 1119 if (!AllocationOk()) return false; |
| 1112 AllocateDoubleRegisters(); | 1120 { |
| 1121 PhaseScope phase_scope(stats, "allocate double registers"); |
| 1122 AllocateDoubleRegisters(); |
| 1123 } |
| 1113 if (!AllocationOk()) return false; | 1124 if (!AllocationOk()) return false; |
| 1114 PopulatePointerMaps(); | 1125 { |
| 1115 ConnectRanges(); | 1126 PhaseScope phase_scope(stats, "populate pointer maps"); |
| 1116 ResolveControlFlow(); | 1127 PopulatePointerMaps(); |
| 1128 } |
| 1129 { |
| 1130 PhaseScope phase_scope(stats, "connect ranges"); |
| 1131 ConnectRanges(); |
| 1132 } |
| 1133 { |
| 1134 PhaseScope phase_scope(stats, "resolve control flow"); |
| 1135 ResolveControlFlow(); |
| 1136 } |
| 1117 frame()->SetAllocatedRegisters(assigned_registers_); | 1137 frame()->SetAllocatedRegisters(assigned_registers_); |
| 1118 frame()->SetAllocatedDoubleRegisters(assigned_double_registers_); | 1138 frame()->SetAllocatedDoubleRegisters(assigned_double_registers_); |
| 1119 return true; | 1139 return true; |
| 1120 } | 1140 } |
| 1121 | 1141 |
| 1122 | 1142 |
| 1123 class RegisterAllocatorPhase : public CompilationPhase { | |
| 1124 public: | |
| 1125 RegisterAllocatorPhase(const char* name, RegisterAllocator* allocator) | |
| 1126 : CompilationPhase(name, allocator->info()), | |
| 1127 allocator_(allocator), | |
| 1128 allocator_zone_start_allocation_size_(0), | |
| 1129 stats_(NULL) { | |
| 1130 if (FLAG_turbo_stats) { | |
| 1131 allocator_zone_start_allocation_size_ = | |
| 1132 allocator->info()->zone()->allocation_size(); | |
| 1133 if (allocator->zone_pool() != NULL) { | |
| 1134 stats_ = new ZonePool::StatsScope(allocator->zone_pool()); | |
| 1135 } | |
| 1136 } | |
| 1137 } | |
| 1138 | |
| 1139 ~RegisterAllocatorPhase() { | |
| 1140 if (FLAG_turbo_stats) { | |
| 1141 unsigned size = allocator_->info()->zone()->allocation_size() - | |
| 1142 allocator_zone_start_allocation_size_; | |
| 1143 if (stats_ != NULL) { | |
| 1144 size += static_cast<unsigned>(stats_->GetMaxAllocatedBytes()); | |
| 1145 } | |
| 1146 isolate()->GetTStatistics()->SaveTiming(name(), base::TimeDelta(), size); | |
| 1147 } | |
| 1148 delete stats_; | |
| 1149 #ifdef DEBUG | |
| 1150 if (allocator_ != NULL) allocator_->Verify(); | |
| 1151 #endif | |
| 1152 } | |
| 1153 | |
| 1154 private: | |
| 1155 RegisterAllocator* allocator_; | |
| 1156 unsigned allocator_zone_start_allocation_size_; | |
| 1157 ZonePool::StatsScope* stats_; | |
| 1158 | |
| 1159 DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorPhase); | |
| 1160 }; | |
| 1161 | |
| 1162 | |
| 1163 void RegisterAllocator::MeetRegisterConstraints() { | 1143 void RegisterAllocator::MeetRegisterConstraints() { |
| 1164 RegisterAllocatorPhase phase("L_Register constraints", this); | |
| 1165 for (int i = 0; i < code()->InstructionBlockCount(); ++i) { | 1144 for (int i = 0; i < code()->InstructionBlockCount(); ++i) { |
| 1166 MeetRegisterConstraints( | 1145 MeetRegisterConstraints( |
| 1167 code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(i))); | 1146 code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(i))); |
| 1168 if (!AllocationOk()) return; | 1147 if (!AllocationOk()) return; |
| 1169 } | 1148 } |
| 1170 } | 1149 } |
| 1171 | 1150 |
| 1172 | 1151 |
| 1173 void RegisterAllocator::ResolvePhis() { | 1152 void RegisterAllocator::ResolvePhis() { |
| 1174 RegisterAllocatorPhase phase("L_Resolve phis", this); | |
| 1175 | |
| 1176 // Process the blocks in reverse order. | 1153 // Process the blocks in reverse order. |
| 1177 for (int i = code()->InstructionBlockCount() - 1; i >= 0; --i) { | 1154 for (int i = code()->InstructionBlockCount() - 1; i >= 0; --i) { |
| 1178 ResolvePhis(code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(i))); | 1155 ResolvePhis(code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(i))); |
| 1179 } | 1156 } |
| 1180 } | 1157 } |
| 1181 | 1158 |
| 1182 | 1159 |
| 1183 void RegisterAllocator::ResolveControlFlow(LiveRange* range, | 1160 void RegisterAllocator::ResolveControlFlow(LiveRange* range, |
| 1184 const InstructionBlock* block, | 1161 const InstructionBlock* block, |
| 1185 const InstructionBlock* pred) { | 1162 const InstructionBlock* pred) { |
| (...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1243 } | 1220 } |
| 1244 | 1221 |
| 1245 | 1222 |
| 1246 const InstructionBlock* RegisterAllocator::GetInstructionBlock( | 1223 const InstructionBlock* RegisterAllocator::GetInstructionBlock( |
| 1247 LifetimePosition pos) { | 1224 LifetimePosition pos) { |
| 1248 return code()->GetInstructionBlock(pos.InstructionIndex()); | 1225 return code()->GetInstructionBlock(pos.InstructionIndex()); |
| 1249 } | 1226 } |
| 1250 | 1227 |
| 1251 | 1228 |
| 1252 void RegisterAllocator::ConnectRanges() { | 1229 void RegisterAllocator::ConnectRanges() { |
| 1253 RegisterAllocatorPhase phase("L_Connect ranges", this); | |
| 1254 for (int i = 0; i < live_ranges()->length(); ++i) { | 1230 for (int i = 0; i < live_ranges()->length(); ++i) { |
| 1255 LiveRange* first_range = live_ranges()->at(i); | 1231 LiveRange* first_range = live_ranges()->at(i); |
| 1256 if (first_range == NULL || first_range->parent() != NULL) continue; | 1232 if (first_range == NULL || first_range->parent() != NULL) continue; |
| 1257 | 1233 |
| 1258 LiveRange* second_range = first_range->next(); | 1234 LiveRange* second_range = first_range->next(); |
| 1259 while (second_range != NULL) { | 1235 while (second_range != NULL) { |
| 1260 LifetimePosition pos = second_range->Start(); | 1236 LifetimePosition pos = second_range->Start(); |
| 1261 | 1237 |
| 1262 if (!second_range->IsSpilled()) { | 1238 if (!second_range->IsSpilled()) { |
| 1263 // Add gap move if the two live ranges touch and there is no block | 1239 // Add gap move if the two live ranges touch and there is no block |
| (...skipping 23 matching lines...) Expand all Loading... |
| 1287 | 1263 |
| 1288 | 1264 |
| 1289 bool RegisterAllocator::CanEagerlyResolveControlFlow( | 1265 bool RegisterAllocator::CanEagerlyResolveControlFlow( |
| 1290 const InstructionBlock* block) const { | 1266 const InstructionBlock* block) const { |
| 1291 if (block->PredecessorCount() != 1) return false; | 1267 if (block->PredecessorCount() != 1) return false; |
| 1292 return block->predecessors()[0].IsNext(block->rpo_number()); | 1268 return block->predecessors()[0].IsNext(block->rpo_number()); |
| 1293 } | 1269 } |
| 1294 | 1270 |
| 1295 | 1271 |
| 1296 void RegisterAllocator::ResolveControlFlow() { | 1272 void RegisterAllocator::ResolveControlFlow() { |
| 1297 RegisterAllocatorPhase phase("L_Resolve control flow", this); | |
| 1298 for (int block_id = 1; block_id < code()->InstructionBlockCount(); | 1273 for (int block_id = 1; block_id < code()->InstructionBlockCount(); |
| 1299 ++block_id) { | 1274 ++block_id) { |
| 1300 const InstructionBlock* block = | 1275 const InstructionBlock* block = |
| 1301 code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(block_id)); | 1276 code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(block_id)); |
| 1302 if (CanEagerlyResolveControlFlow(block)) continue; | 1277 if (CanEagerlyResolveControlFlow(block)) continue; |
| 1303 BitVector* live = live_in_sets_[block->rpo_number().ToInt()]; | 1278 BitVector* live = live_in_sets_[block->rpo_number().ToInt()]; |
| 1304 BitVector::Iterator iterator(live); | 1279 BitVector::Iterator iterator(live); |
| 1305 while (!iterator.Done()) { | 1280 while (!iterator.Done()) { |
| 1306 int operand_index = iterator.Current(); | 1281 int operand_index = iterator.Current(); |
| 1307 for (auto pred : block->predecessors()) { | 1282 for (auto pred : block->predecessors()) { |
| 1308 const InstructionBlock* cur = code()->InstructionBlockAt(pred); | 1283 const InstructionBlock* cur = code()->InstructionBlockAt(pred); |
| 1309 LiveRange* cur_range = LiveRangeFor(operand_index); | 1284 LiveRange* cur_range = LiveRangeFor(operand_index); |
| 1310 ResolveControlFlow(cur_range, block, cur); | 1285 ResolveControlFlow(cur_range, block, cur); |
| 1311 } | 1286 } |
| 1312 iterator.Advance(); | 1287 iterator.Advance(); |
| 1313 } | 1288 } |
| 1314 } | 1289 } |
| 1315 } | 1290 } |
| 1316 | 1291 |
| 1317 | 1292 |
| 1318 void RegisterAllocator::BuildLiveRanges() { | 1293 void RegisterAllocator::BuildLiveRanges() { |
| 1319 RegisterAllocatorPhase phase("L_Build live ranges", this); | |
| 1320 InitializeLivenessAnalysis(); | 1294 InitializeLivenessAnalysis(); |
| 1321 // Process the blocks in reverse order. | 1295 // Process the blocks in reverse order. |
| 1322 for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0; | 1296 for (int block_id = code()->InstructionBlockCount() - 1; block_id >= 0; |
| 1323 --block_id) { | 1297 --block_id) { |
| 1324 const InstructionBlock* block = | 1298 const InstructionBlock* block = |
| 1325 code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(block_id)); | 1299 code()->InstructionBlockAt(BasicBlock::RpoNumber::FromInt(block_id)); |
| 1326 BitVector* live = ComputeLiveOut(block); | 1300 BitVector* live = ComputeLiveOut(block); |
| 1327 // Initially consider all live_out values live for the entire block. We | 1301 // Initially consider all live_out values live for the entire block. We |
| 1328 // will shorten these intervals if necessary. | 1302 // will shorten these intervals if necessary. |
| 1329 AddInitialIntervals(block, live); | 1303 AddInitialIntervals(block, live); |
| (...skipping 120 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1450 it != pointer_maps->end(); ++it) { | 1424 it != pointer_maps->end(); ++it) { |
| 1451 PointerMap* map = *it; | 1425 PointerMap* map = *it; |
| 1452 if (safe_point > map->instruction_position()) return false; | 1426 if (safe_point > map->instruction_position()) return false; |
| 1453 safe_point = map->instruction_position(); | 1427 safe_point = map->instruction_position(); |
| 1454 } | 1428 } |
| 1455 return true; | 1429 return true; |
| 1456 } | 1430 } |
| 1457 | 1431 |
| 1458 | 1432 |
| 1459 void RegisterAllocator::PopulatePointerMaps() { | 1433 void RegisterAllocator::PopulatePointerMaps() { |
| 1460 RegisterAllocatorPhase phase("L_Populate pointer maps", this); | |
| 1461 | |
| 1462 DCHECK(SafePointsAreInOrder()); | 1434 DCHECK(SafePointsAreInOrder()); |
| 1463 | 1435 |
| 1464 // Iterate over all safe point positions and record a pointer | 1436 // Iterate over all safe point positions and record a pointer |
| 1465 // for all spilled live ranges at this point. | 1437 // for all spilled live ranges at this point. |
| 1466 int last_range_start = 0; | 1438 int last_range_start = 0; |
| 1467 const PointerMapDeque* pointer_maps = code()->pointer_maps(); | 1439 const PointerMapDeque* pointer_maps = code()->pointer_maps(); |
| 1468 PointerMapDeque::const_iterator first_it = pointer_maps->begin(); | 1440 PointerMapDeque::const_iterator first_it = pointer_maps->begin(); |
| 1469 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { | 1441 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { |
| 1470 LiveRange* range = live_ranges()->at(range_idx); | 1442 LiveRange* range = live_ranges()->at(range_idx); |
| 1471 if (range == NULL) continue; | 1443 if (range == NULL) continue; |
| (...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1534 InstructionOperand* operand = cur->CreateAssignedOperand(code_zone()); | 1506 InstructionOperand* operand = cur->CreateAssignedOperand(code_zone()); |
| 1535 DCHECK(!operand->IsStackSlot()); | 1507 DCHECK(!operand->IsStackSlot()); |
| 1536 map->RecordPointer(operand, code_zone()); | 1508 map->RecordPointer(operand, code_zone()); |
| 1537 } | 1509 } |
| 1538 } | 1510 } |
| 1539 } | 1511 } |
| 1540 } | 1512 } |
| 1541 | 1513 |
| 1542 | 1514 |
| 1543 void RegisterAllocator::AllocateGeneralRegisters() { | 1515 void RegisterAllocator::AllocateGeneralRegisters() { |
| 1544 RegisterAllocatorPhase phase("L_Allocate general registers", this); | |
| 1545 num_registers_ = Register::NumAllocatableRegisters(); | 1516 num_registers_ = Register::NumAllocatableRegisters(); |
| 1546 mode_ = GENERAL_REGISTERS; | 1517 mode_ = GENERAL_REGISTERS; |
| 1547 AllocateRegisters(); | 1518 AllocateRegisters(); |
| 1548 } | 1519 } |
| 1549 | 1520 |
| 1550 | 1521 |
| 1551 void RegisterAllocator::AllocateDoubleRegisters() { | 1522 void RegisterAllocator::AllocateDoubleRegisters() { |
| 1552 RegisterAllocatorPhase phase("L_Allocate double registers", this); | |
| 1553 num_registers_ = DoubleRegister::NumAllocatableAliasedRegisters(); | 1523 num_registers_ = DoubleRegister::NumAllocatableAliasedRegisters(); |
| 1554 mode_ = DOUBLE_REGISTERS; | 1524 mode_ = DOUBLE_REGISTERS; |
| 1555 AllocateRegisters(); | 1525 AllocateRegisters(); |
| 1556 } | 1526 } |
| 1557 | 1527 |
| 1558 | 1528 |
| 1559 void RegisterAllocator::AllocateRegisters() { | 1529 void RegisterAllocator::AllocateRegisters() { |
| 1560 DCHECK(unhandled_live_ranges_.is_empty()); | 1530 DCHECK(unhandled_live_ranges_.is_empty()); |
| 1561 | 1531 |
| 1562 for (int i = 0; i < live_ranges_.length(); ++i) { | 1532 for (int i = 0; i < live_ranges_.length(); ++i) { |
| (...skipping 682 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2245 } else { | 2215 } else { |
| 2246 DCHECK(range->Kind() == GENERAL_REGISTERS); | 2216 DCHECK(range->Kind() == GENERAL_REGISTERS); |
| 2247 assigned_registers_->Add(reg); | 2217 assigned_registers_->Add(reg); |
| 2248 } | 2218 } |
| 2249 range->set_assigned_register(reg, code_zone()); | 2219 range->set_assigned_register(reg, code_zone()); |
| 2250 } | 2220 } |
| 2251 | 2221 |
| 2252 } | 2222 } |
| 2253 } | 2223 } |
| 2254 } // namespace v8::internal::compiler | 2224 } // namespace v8::internal::compiler |
| OLD | NEW |