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 |