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 |