| 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 |