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

Side by Side Diff: src/compiler/register-allocator.cc

Issue 669053002: [turbofan] split compilation stats off from HStatistics and track high water marks (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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
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
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
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698