| 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" | 5 #include "src/compiler/linkage.h" |
| 6 #include "src/compiler/register-allocator.h" | 6 #include "src/compiler/register-allocator.h" |
| 7 #include "src/string-stream.h" | 7 #include "src/string-stream.h" |
| 8 | 8 |
| 9 namespace v8 { | 9 namespace v8 { |
| 10 namespace internal { | 10 namespace internal { |
| (...skipping 879 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 890 } else { | 890 } else { |
| 891 tail->set_next(current); | 891 tail->set_next(current); |
| 892 } | 892 } |
| 893 tail = current; | 893 tail = current; |
| 894 current = current->next(); | 894 current = current->next(); |
| 895 } | 895 } |
| 896 // Other list is empty => we are done | 896 // Other list is empty => we are done |
| 897 } | 897 } |
| 898 | 898 |
| 899 | 899 |
| 900 void RegisterAllocator::ReuseSpillSlots() { | 900 void RegisterAllocator::AssignSpillSlots() { |
| 901 DCHECK(FLAG_turbo_reuse_spill_slots); | |
| 902 | |
| 903 // Merge disjoint spill ranges | 901 // Merge disjoint spill ranges |
| 904 for (size_t i = 0; i < spill_ranges().size(); i++) { | 902 for (size_t i = 0; i < spill_ranges().size(); i++) { |
| 905 auto range = spill_ranges()[i]; | 903 auto range = spill_ranges()[i]; |
| 906 if (range->IsEmpty()) continue; | 904 if (range->IsEmpty()) continue; |
| 907 for (size_t j = i + 1; j < spill_ranges().size(); j++) { | 905 for (size_t j = i + 1; j < spill_ranges().size(); j++) { |
| 908 auto other = spill_ranges()[j]; | 906 auto other = spill_ranges()[j]; |
| 909 if (!other->IsEmpty()) { | 907 if (!other->IsEmpty()) { |
| 910 range->TryMerge(other); | 908 range->TryMerge(other); |
| 911 } | 909 } |
| 912 } | 910 } |
| (...skipping 22 matching lines...) Expand all Loading... |
| 935 auto assigned = range->CreateAssignedOperand(code_zone()); | 933 auto assigned = range->CreateAssignedOperand(code_zone()); |
| 936 range->ConvertUsesToOperand(assigned); | 934 range->ConvertUsesToOperand(assigned); |
| 937 if (range->IsSpilled()) { | 935 if (range->IsSpilled()) { |
| 938 range->CommitSpillsAtDefinition(code(), assigned); | 936 range->CommitSpillsAtDefinition(code(), assigned); |
| 939 } | 937 } |
| 940 } | 938 } |
| 941 } | 939 } |
| 942 | 940 |
| 943 | 941 |
| 944 SpillRange* RegisterAllocator::AssignSpillRangeToLiveRange(LiveRange* range) { | 942 SpillRange* RegisterAllocator::AssignSpillRangeToLiveRange(LiveRange* range) { |
| 945 DCHECK(FLAG_turbo_reuse_spill_slots); | |
| 946 auto spill_range = new (local_zone()) SpillRange(range, local_zone()); | 943 auto spill_range = new (local_zone()) SpillRange(range, local_zone()); |
| 947 spill_ranges().push_back(spill_range); | 944 spill_ranges().push_back(spill_range); |
| 948 return spill_range; | 945 return spill_range; |
| 949 } | 946 } |
| 950 | 947 |
| 951 | 948 |
| 952 bool RegisterAllocator::TryReuseSpillForPhi(LiveRange* range) { | 949 bool RegisterAllocator::TryReuseSpillForPhi(LiveRange* range) { |
| 953 DCHECK(FLAG_turbo_reuse_spill_slots); | |
| 954 if (range->IsChild() || !range->is_phi()) return false; | 950 if (range->IsChild() || !range->is_phi()) return false; |
| 955 DCHECK(range->HasNoSpillType()); | 951 DCHECK(range->HasNoSpillType()); |
| 956 | 952 |
| 957 auto lookup = phi_map_.find(range->id()); | 953 auto lookup = phi_map_.find(range->id()); |
| 958 DCHECK(lookup != phi_map_.end()); | 954 DCHECK(lookup != phi_map_.end()); |
| 959 auto phi = lookup->second.phi; | 955 auto phi = lookup->second.phi; |
| 960 auto block = lookup->second.block; | 956 auto block = lookup->second.block; |
| 961 // Count the number of spilled operands. | 957 // Count the number of spilled operands. |
| 962 size_t spilled_count = 0; | 958 size_t spilled_count = 0; |
| 963 LiveRange* first_op = nullptr; | 959 LiveRange* first_op = nullptr; |
| (...skipping 377 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1341 nullptr); | 1337 nullptr); |
| 1342 Define(curr_position, temp, nullptr); | 1338 Define(curr_position, temp, nullptr); |
| 1343 } | 1339 } |
| 1344 } | 1340 } |
| 1345 } | 1341 } |
| 1346 } | 1342 } |
| 1347 | 1343 |
| 1348 | 1344 |
| 1349 void RegisterAllocator::ResolvePhis(const InstructionBlock* block) { | 1345 void RegisterAllocator::ResolvePhis(const InstructionBlock* block) { |
| 1350 for (auto phi : block->phis()) { | 1346 for (auto phi : block->phis()) { |
| 1351 if (FLAG_turbo_reuse_spill_slots) { | 1347 auto res = phi_map_.insert( |
| 1352 auto res = phi_map_.insert( | 1348 std::make_pair(phi->virtual_register(), PhiMapValue(phi, block))); |
| 1353 std::make_pair(phi->virtual_register(), PhiMapValue(phi, block))); | 1349 DCHECK(res.second); |
| 1354 DCHECK(res.second); | 1350 USE(res); |
| 1355 USE(res); | |
| 1356 } | |
| 1357 auto output = phi->output(); | 1351 auto output = phi->output(); |
| 1358 int phi_vreg = phi->virtual_register(); | 1352 int phi_vreg = phi->virtual_register(); |
| 1359 if (!FLAG_turbo_delay_ssa_decon) { | 1353 if (!FLAG_turbo_delay_ssa_decon) { |
| 1360 for (size_t i = 0; i < phi->operands().size(); ++i) { | 1354 for (size_t i = 0; i < phi->operands().size(); ++i) { |
| 1361 InstructionBlock* cur_block = | 1355 InstructionBlock* cur_block = |
| 1362 code()->InstructionBlockAt(block->predecessors()[i]); | 1356 code()->InstructionBlockAt(block->predecessors()[i]); |
| 1363 AddGapMove(cur_block->last_instruction_index() - 1, GapInstruction::END, | 1357 AddGapMove(cur_block->last_instruction_index() - 1, GapInstruction::END, |
| 1364 phi->inputs()[i], output); | 1358 phi->inputs()[i], output); |
| 1365 DCHECK(!InstructionAt(cur_block->last_instruction_index()) | 1359 DCHECK(!InstructionAt(cur_block->last_instruction_index()) |
| 1366 ->HasPointerMap()); | 1360 ->HasPointerMap()); |
| (...skipping 560 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1927 } else if (pos->pos().Value() > | 1921 } else if (pos->pos().Value() > |
| 1928 current->Start().NextInstruction().Value()) { | 1922 current->Start().NextInstruction().Value()) { |
| 1929 // Do not spill live range eagerly if use position that can benefit from | 1923 // Do not spill live range eagerly if use position that can benefit from |
| 1930 // the register is too close to the start of live range. | 1924 // the register is too close to the start of live range. |
| 1931 SpillBetween(current, current->Start(), pos->pos()); | 1925 SpillBetween(current, current->Start(), pos->pos()); |
| 1932 DCHECK(UnhandledIsSorted()); | 1926 DCHECK(UnhandledIsSorted()); |
| 1933 continue; | 1927 continue; |
| 1934 } | 1928 } |
| 1935 } | 1929 } |
| 1936 | 1930 |
| 1937 if (FLAG_turbo_reuse_spill_slots) { | 1931 if (TryReuseSpillForPhi(current)) continue; |
| 1938 if (TryReuseSpillForPhi(current)) { | |
| 1939 continue; | |
| 1940 } | |
| 1941 } | |
| 1942 | 1932 |
| 1943 for (size_t i = 0; i < active_live_ranges().size(); ++i) { | 1933 for (size_t i = 0; i < active_live_ranges().size(); ++i) { |
| 1944 auto cur_active = active_live_ranges()[i]; | 1934 auto cur_active = active_live_ranges()[i]; |
| 1945 if (cur_active->End().Value() <= position.Value()) { | 1935 if (cur_active->End().Value() <= position.Value()) { |
| 1946 ActiveToHandled(cur_active); | 1936 ActiveToHandled(cur_active); |
| 1947 --i; // The live range was removed from the list of active live ranges. | 1937 --i; // The live range was removed from the list of active live ranges. |
| 1948 } else if (!cur_active->Covers(position)) { | 1938 } else if (!cur_active->Covers(position)) { |
| 1949 ActiveToInactive(cur_active); | 1939 ActiveToInactive(cur_active); |
| 1950 --i; // The live range was removed from the list of active live ranges. | 1940 --i; // The live range was removed from the list of active live ranges. |
| 1951 } | 1941 } |
| (...skipping 108 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2060 size_t len = unhandled_live_ranges().size(); | 2050 size_t len = unhandled_live_ranges().size(); |
| 2061 for (size_t i = 1; i < len; i++) { | 2051 for (size_t i = 1; i < len; i++) { |
| 2062 auto a = unhandled_live_ranges().at(i - 1); | 2052 auto a = unhandled_live_ranges().at(i - 1); |
| 2063 auto b = unhandled_live_ranges().at(i); | 2053 auto b = unhandled_live_ranges().at(i); |
| 2064 if (a->Start().Value() < b->Start().Value()) return false; | 2054 if (a->Start().Value() < b->Start().Value()) return false; |
| 2065 } | 2055 } |
| 2066 return true; | 2056 return true; |
| 2067 } | 2057 } |
| 2068 | 2058 |
| 2069 | 2059 |
| 2070 void RegisterAllocator::FreeSpillSlot(LiveRange* range) { | |
| 2071 DCHECK(!FLAG_turbo_reuse_spill_slots); | |
| 2072 // Check that we are the last range. | |
| 2073 if (range->next() != nullptr) return; | |
| 2074 if (!range->TopLevel()->HasSpillOperand()) return; | |
| 2075 auto spill_operand = range->TopLevel()->GetSpillOperand(); | |
| 2076 if (spill_operand->IsConstant()) return; | |
| 2077 if (spill_operand->index() >= 0) { | |
| 2078 reusable_slots().push_back(range); | |
| 2079 } | |
| 2080 } | |
| 2081 | |
| 2082 | |
| 2083 InstructionOperand* RegisterAllocator::TryReuseSpillSlot(LiveRange* range) { | |
| 2084 DCHECK(!FLAG_turbo_reuse_spill_slots); | |
| 2085 if (reusable_slots().empty()) return nullptr; | |
| 2086 if (reusable_slots().front()->End().Value() > | |
| 2087 range->TopLevel()->Start().Value()) { | |
| 2088 return nullptr; | |
| 2089 } | |
| 2090 auto result = reusable_slots().front()->TopLevel()->GetSpillOperand(); | |
| 2091 reusable_slots().erase(reusable_slots().begin()); | |
| 2092 return result; | |
| 2093 } | |
| 2094 | |
| 2095 | |
| 2096 void RegisterAllocator::ActiveToHandled(LiveRange* range) { | 2060 void RegisterAllocator::ActiveToHandled(LiveRange* range) { |
| 2097 RemoveElement(&active_live_ranges(), range); | 2061 RemoveElement(&active_live_ranges(), range); |
| 2098 TraceAlloc("Moving live range %d from active to handled\n", range->id()); | 2062 TraceAlloc("Moving live range %d from active to handled\n", range->id()); |
| 2099 if (!FLAG_turbo_reuse_spill_slots) FreeSpillSlot(range); | |
| 2100 } | 2063 } |
| 2101 | 2064 |
| 2102 | 2065 |
| 2103 void RegisterAllocator::ActiveToInactive(LiveRange* range) { | 2066 void RegisterAllocator::ActiveToInactive(LiveRange* range) { |
| 2104 RemoveElement(&active_live_ranges(), range); | 2067 RemoveElement(&active_live_ranges(), range); |
| 2105 inactive_live_ranges().push_back(range); | 2068 inactive_live_ranges().push_back(range); |
| 2106 TraceAlloc("Moving live range %d from active to inactive\n", range->id()); | 2069 TraceAlloc("Moving live range %d from active to inactive\n", range->id()); |
| 2107 } | 2070 } |
| 2108 | 2071 |
| 2109 | 2072 |
| 2110 void RegisterAllocator::InactiveToHandled(LiveRange* range) { | 2073 void RegisterAllocator::InactiveToHandled(LiveRange* range) { |
| 2111 RemoveElement(&inactive_live_ranges(), range); | 2074 RemoveElement(&inactive_live_ranges(), range); |
| 2112 TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); | 2075 TraceAlloc("Moving live range %d from inactive to handled\n", range->id()); |
| 2113 if (!FLAG_turbo_reuse_spill_slots) FreeSpillSlot(range); | |
| 2114 } | 2076 } |
| 2115 | 2077 |
| 2116 | 2078 |
| 2117 void RegisterAllocator::InactiveToActive(LiveRange* range) { | 2079 void RegisterAllocator::InactiveToActive(LiveRange* range) { |
| 2118 RemoveElement(&inactive_live_ranges(), range); | 2080 RemoveElement(&inactive_live_ranges(), range); |
| 2119 active_live_ranges().push_back(range); | 2081 active_live_ranges().push_back(range); |
| 2120 TraceAlloc("Moving live range %d from inactive to active\n", range->id()); | 2082 TraceAlloc("Moving live range %d from inactive to active\n", range->id()); |
| 2121 } | 2083 } |
| 2122 | 2084 |
| 2123 | 2085 |
| (...skipping 348 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2472 AddToUnhandledSorted(second_part); | 2434 AddToUnhandledSorted(second_part); |
| 2473 } | 2435 } |
| 2474 } | 2436 } |
| 2475 | 2437 |
| 2476 | 2438 |
| 2477 void RegisterAllocator::Spill(LiveRange* range) { | 2439 void RegisterAllocator::Spill(LiveRange* range) { |
| 2478 DCHECK(!range->IsSpilled()); | 2440 DCHECK(!range->IsSpilled()); |
| 2479 TraceAlloc("Spilling live range %d\n", range->id()); | 2441 TraceAlloc("Spilling live range %d\n", range->id()); |
| 2480 auto first = range->TopLevel(); | 2442 auto first = range->TopLevel(); |
| 2481 if (first->HasNoSpillType()) { | 2443 if (first->HasNoSpillType()) { |
| 2482 if (FLAG_turbo_reuse_spill_slots) { | 2444 AssignSpillRangeToLiveRange(first); |
| 2483 AssignSpillRangeToLiveRange(first); | |
| 2484 } else { | |
| 2485 auto op = TryReuseSpillSlot(range); | |
| 2486 if (op == nullptr) { | |
| 2487 // Allocate a new operand referring to the spill slot. | |
| 2488 RegisterKind kind = range->Kind(); | |
| 2489 int index = frame()->AllocateSpillSlot(kind == DOUBLE_REGISTERS); | |
| 2490 auto op_kind = kind == DOUBLE_REGISTERS | |
| 2491 ? InstructionOperand::DOUBLE_STACK_SLOT | |
| 2492 : InstructionOperand::STACK_SLOT; | |
| 2493 op = new (code_zone()) InstructionOperand(op_kind, index); | |
| 2494 } | |
| 2495 first->SetSpillOperand(op); | |
| 2496 } | |
| 2497 } | 2445 } |
| 2498 range->MakeSpilled(); | 2446 range->MakeSpilled(); |
| 2499 } | 2447 } |
| 2500 | 2448 |
| 2501 | 2449 |
| 2502 int RegisterAllocator::RegisterCount() const { return num_registers_; } | 2450 int RegisterAllocator::RegisterCount() const { return num_registers_; } |
| 2503 | 2451 |
| 2504 | 2452 |
| 2505 #ifdef DEBUG | 2453 #ifdef DEBUG |
| 2506 | 2454 |
| (...skipping 15 matching lines...) Expand all Loading... |
| 2522 } else { | 2470 } else { |
| 2523 DCHECK(range->Kind() == GENERAL_REGISTERS); | 2471 DCHECK(range->Kind() == GENERAL_REGISTERS); |
| 2524 assigned_registers_->Add(reg); | 2472 assigned_registers_->Add(reg); |
| 2525 } | 2473 } |
| 2526 range->set_assigned_register(reg, code_zone()); | 2474 range->set_assigned_register(reg, code_zone()); |
| 2527 } | 2475 } |
| 2528 | 2476 |
| 2529 } // namespace compiler | 2477 } // namespace compiler |
| 2530 } // namespace internal | 2478 } // namespace internal |
| 2531 } // namespace v8 | 2479 } // namespace v8 |
| OLD | NEW |