Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include "register_allocator.h" |
| 18 | |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 19 | #include <iostream> |
Ian Rogers | c7dd295 | 2014-10-21 23:31:19 -0700 | [diff] [blame] | 20 | #include <sstream> |
| 21 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 22 | #include "base/bit_vector-inl.h" |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 23 | #include "code_generator.h" |
| 24 | #include "ssa_liveness_analysis.h" |
| 25 | |
| 26 | namespace art { |
| 27 | |
| 28 | static constexpr size_t kMaxLifetimePosition = -1; |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 29 | static constexpr size_t kDefaultNumberOfSpillSlots = 4; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 30 | |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 31 | // For simplicity, we implement register pairs as (reg, reg + 1). |
| 32 | // Note that this is a requirement for double registers on ARM, since we |
| 33 | // allocate SRegister. |
| 34 | static int GetHighForLowRegister(int reg) { return reg + 1; } |
| 35 | static bool IsLowRegister(int reg) { return (reg & 1) == 0; } |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 36 | static bool IsLowOfUnalignedPairInterval(LiveInterval* low) { |
| 37 | return GetHighForLowRegister(low->GetRegister()) != low->GetHighInterval()->GetRegister(); |
| 38 | } |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 39 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 40 | RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, |
| 41 | CodeGenerator* codegen, |
| 42 | const SsaLivenessAnalysis& liveness) |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 43 | : allocator_(allocator), |
| 44 | codegen_(codegen), |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 45 | liveness_(liveness), |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 46 | unhandled_core_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 47 | unhandled_fp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 48 | unhandled_(nullptr), |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 49 | handled_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 50 | active_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 51 | inactive_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 52 | physical_core_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 53 | physical_fp_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 54 | temp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 55 | int_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 56 | long_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 57 | float_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
| 58 | double_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 59 | catch_phi_spill_slots_(0), |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 60 | safepoints_(allocator->Adapter(kArenaAllocRegisterAllocator)), |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 61 | processing_core_registers_(false), |
| 62 | number_of_registers_(-1), |
| 63 | registers_array_(nullptr), |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 64 | blocked_core_registers_(codegen->GetBlockedCoreRegisters()), |
| 65 | blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), |
Nicolas Geoffray | 3bca0df | 2014-09-19 11:01:00 +0100 | [diff] [blame] | 66 | reserved_out_slots_(0), |
Mark Mendell | f85a9ca | 2015-01-13 09:20:58 -0500 | [diff] [blame] | 67 | maximum_number_of_live_core_registers_(0), |
| 68 | maximum_number_of_live_fp_registers_(0) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 69 | temp_intervals_.reserve(4); |
| 70 | int_spill_slots_.reserve(kDefaultNumberOfSpillSlots); |
| 71 | long_spill_slots_.reserve(kDefaultNumberOfSpillSlots); |
| 72 | float_spill_slots_.reserve(kDefaultNumberOfSpillSlots); |
| 73 | double_spill_slots_.reserve(kDefaultNumberOfSpillSlots); |
| 74 | |
David Brazdil | 58282f4 | 2016-01-14 12:45:10 +0000 | [diff] [blame] | 75 | codegen->SetupBlockedRegisters(); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 76 | physical_core_register_intervals_.resize(codegen->GetNumberOfCoreRegisters(), nullptr); |
| 77 | physical_fp_register_intervals_.resize(codegen->GetNumberOfFloatingPointRegisters(), nullptr); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 78 | // Always reserve for the current method and the graph's max out registers. |
| 79 | // TODO: compute it instead. |
Mathieu Chartier | e401d14 | 2015-04-22 13:56:20 -0700 | [diff] [blame] | 80 | // ArtMethod* takes 2 vregs for 64 bits. |
| 81 | reserved_out_slots_ = InstructionSetPointerSize(codegen->GetInstructionSet()) / kVRegSize + |
| 82 | codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 83 | } |
| 84 | |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 85 | bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph ATTRIBUTE_UNUSED, |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 86 | InstructionSet instruction_set) { |
Goran Jakovljevic | f652cec | 2015-08-25 16:11:42 +0200 | [diff] [blame] | 87 | return instruction_set == kArm |
| 88 | || instruction_set == kArm64 |
| 89 | || instruction_set == kMips |
Alexey Frunze | 4dda337 | 2015-06-01 18:31:49 -0700 | [diff] [blame] | 90 | || instruction_set == kMips64 |
Goran Jakovljevic | f652cec | 2015-08-25 16:11:42 +0200 | [diff] [blame] | 91 | || instruction_set == kThumb2 |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 92 | || instruction_set == kX86 |
Goran Jakovljevic | f652cec | 2015-08-25 16:11:42 +0200 | [diff] [blame] | 93 | || instruction_set == kX86_64; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | static bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 97 | if (interval == nullptr) return false; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 98 | bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) |
| 99 | && (interval->GetType() != Primitive::kPrimFloat); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 100 | return processing_core_registers == is_core_register; |
| 101 | } |
| 102 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 103 | void RegisterAllocator::AllocateRegisters() { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 104 | AllocateRegistersInternal(); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 105 | Resolve(); |
| 106 | |
| 107 | if (kIsDebugBuild) { |
| 108 | processing_core_registers_ = true; |
| 109 | ValidateInternal(true); |
| 110 | processing_core_registers_ = false; |
| 111 | ValidateInternal(true); |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 112 | // Check that the linear order is still correct with regards to lifetime positions. |
| 113 | // Since only parallel moves have been inserted during the register allocation, |
| 114 | // these checks are mostly for making sure these moves have been added correctly. |
| 115 | size_t current_liveness = 0; |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 116 | for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 117 | HBasicBlock* block = it.Current(); |
| 118 | for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
| 119 | HInstruction* instruction = inst_it.Current(); |
| 120 | DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); |
| 121 | current_liveness = instruction->GetLifetimePosition(); |
| 122 | } |
| 123 | for (HInstructionIterator inst_it(block->GetInstructions()); |
| 124 | !inst_it.Done(); |
| 125 | inst_it.Advance()) { |
| 126 | HInstruction* instruction = inst_it.Current(); |
| 127 | DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); |
| 128 | current_liveness = instruction->GetLifetimePosition(); |
| 129 | } |
| 130 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 131 | } |
| 132 | } |
| 133 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 134 | void RegisterAllocator::BlockRegister(Location location, size_t start, size_t end) { |
Nicolas Geoffray | 56b9ee6 | 2014-10-09 11:47:51 +0100 | [diff] [blame] | 135 | int reg = location.reg(); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 136 | DCHECK(location.IsRegister() || location.IsFpuRegister()); |
| 137 | LiveInterval* interval = location.IsRegister() |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 138 | ? physical_core_register_intervals_[reg] |
| 139 | : physical_fp_register_intervals_[reg]; |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 140 | Primitive::Type type = location.IsRegister() |
| 141 | ? Primitive::kPrimInt |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 142 | : Primitive::kPrimFloat; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 143 | if (interval == nullptr) { |
| 144 | interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 145 | if (location.IsRegister()) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 146 | physical_core_register_intervals_[reg] = interval; |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 147 | } else { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 148 | physical_fp_register_intervals_[reg] = interval; |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 149 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 150 | } |
| 151 | DCHECK(interval->GetRegister() == reg); |
| 152 | interval->AddRange(start, end); |
| 153 | } |
| 154 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 155 | void RegisterAllocator::BlockRegisters(size_t start, size_t end, bool caller_save_only) { |
| 156 | for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { |
| 157 | if (!caller_save_only || !codegen_->IsCoreCalleeSaveRegister(i)) { |
| 158 | BlockRegister(Location::RegisterLocation(i), start, end); |
| 159 | } |
| 160 | } |
| 161 | for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { |
| 162 | if (!caller_save_only || !codegen_->IsFloatingPointCalleeSaveRegister(i)) { |
| 163 | BlockRegister(Location::FpuRegisterLocation(i), start, end); |
| 164 | } |
| 165 | } |
| 166 | } |
| 167 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 168 | void RegisterAllocator::AllocateRegistersInternal() { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 169 | // Iterate post-order, to ensure the list is sorted, and the last added interval |
| 170 | // is the one with the lowest start position. |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 171 | for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 172 | HBasicBlock* block = it.Current(); |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 173 | for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); |
| 174 | back_it.Advance()) { |
| 175 | ProcessInstruction(back_it.Current()); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 176 | } |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 177 | for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
| 178 | ProcessInstruction(inst_it.Current()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 179 | } |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 180 | |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 181 | if (block->IsCatchBlock() || |
Nicolas Geoffray | ad4ed08 | 2016-01-27 14:15:23 +0000 | [diff] [blame] | 182 | (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 183 | // By blocking all registers at the top of each catch block or irreducible loop, we force |
| 184 | // intervals belonging to the live-in set of the catch/header block to be spilled. |
| 185 | // TODO(ngeoffray): Phis in this block could be allocated in register. |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 186 | size_t position = block->GetLifetimeStart(); |
| 187 | BlockRegisters(position, position + 1); |
| 188 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 189 | } |
| 190 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 191 | number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 192 | registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, |
| 193 | kArenaAllocRegisterAllocator); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 194 | processing_core_registers_ = true; |
| 195 | unhandled_ = &unhandled_core_intervals_; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 196 | for (LiveInterval* fixed : physical_core_register_intervals_) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 197 | if (fixed != nullptr) { |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 198 | // Fixed interval is added to inactive_ instead of unhandled_. |
| 199 | // It's also the only type of inactive interval whose start position |
| 200 | // can be after the current interval during linear scan. |
| 201 | // Fixed interval is never split and never moves to unhandled_. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 202 | inactive_.push_back(fixed); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 203 | } |
| 204 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 205 | LinearScan(); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 206 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 207 | inactive_.clear(); |
| 208 | active_.clear(); |
| 209 | handled_.clear(); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 210 | |
| 211 | number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 212 | registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, |
| 213 | kArenaAllocRegisterAllocator); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 214 | processing_core_registers_ = false; |
| 215 | unhandled_ = &unhandled_fp_intervals_; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 216 | for (LiveInterval* fixed : physical_fp_register_intervals_) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 217 | if (fixed != nullptr) { |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 218 | // Fixed interval is added to inactive_ instead of unhandled_. |
| 219 | // It's also the only type of inactive interval whose start position |
| 220 | // can be after the current interval during linear scan. |
| 221 | // Fixed interval is never split and never moves to unhandled_. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 222 | inactive_.push_back(fixed); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 223 | } |
| 224 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 225 | LinearScan(); |
| 226 | } |
| 227 | |
| 228 | void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { |
| 229 | LocationSummary* locations = instruction->GetLocations(); |
| 230 | size_t position = instruction->GetLifetimePosition(); |
| 231 | |
| 232 | if (locations == nullptr) return; |
| 233 | |
| 234 | // Create synthesized intervals for temporaries. |
| 235 | for (size_t i = 0; i < locations->GetTempCount(); ++i) { |
| 236 | Location temp = locations->GetTemp(i); |
Nicolas Geoffray | 52839d1 | 2014-11-07 17:47:25 +0000 | [diff] [blame] | 237 | if (temp.IsRegister() || temp.IsFpuRegister()) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 238 | BlockRegister(temp, position, position + 1); |
Nicolas Geoffray | 45b83af | 2015-07-06 15:12:53 +0000 | [diff] [blame] | 239 | // Ensure that an explicit temporary register is marked as being allocated. |
| 240 | codegen_->AddAllocatedRegister(temp); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 241 | } else { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 242 | DCHECK(temp.IsUnallocated()); |
Roland Levillain | 5368c21 | 2014-11-27 15:03:41 +0000 | [diff] [blame] | 243 | switch (temp.GetPolicy()) { |
| 244 | case Location::kRequiresRegister: { |
| 245 | LiveInterval* interval = |
| 246 | LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 247 | temp_intervals_.push_back(interval); |
Nicolas Geoffray | f01d344 | 2015-03-27 17:15:49 +0000 | [diff] [blame] | 248 | interval->AddTempUse(instruction, i); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 249 | unhandled_core_intervals_.push_back(interval); |
Roland Levillain | 5368c21 | 2014-11-27 15:03:41 +0000 | [diff] [blame] | 250 | break; |
| 251 | } |
| 252 | |
| 253 | case Location::kRequiresFpuRegister: { |
| 254 | LiveInterval* interval = |
| 255 | LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 256 | temp_intervals_.push_back(interval); |
Nicolas Geoffray | f01d344 | 2015-03-27 17:15:49 +0000 | [diff] [blame] | 257 | interval->AddTempUse(instruction, i); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 258 | if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { |
Nicolas Geoffray | 5588e58 | 2015-04-14 14:10:59 +0100 | [diff] [blame] | 259 | interval->AddHighInterval(/* is_temp */ true); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 260 | LiveInterval* high = interval->GetHighInterval(); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 261 | temp_intervals_.push_back(high); |
| 262 | unhandled_fp_intervals_.push_back(high); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 263 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 264 | unhandled_fp_intervals_.push_back(interval); |
Roland Levillain | 5368c21 | 2014-11-27 15:03:41 +0000 | [diff] [blame] | 265 | break; |
| 266 | } |
| 267 | |
| 268 | default: |
| 269 | LOG(FATAL) << "Unexpected policy for temporary location " |
| 270 | << temp.GetPolicy(); |
| 271 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 272 | } |
| 273 | } |
| 274 | |
Nicolas Geoffray | 3bca0df | 2014-09-19 11:01:00 +0100 | [diff] [blame] | 275 | bool core_register = (instruction->GetType() != Primitive::kPrimDouble) |
| 276 | && (instruction->GetType() != Primitive::kPrimFloat); |
| 277 | |
Alexandre Rames | 8158f28 | 2015-08-07 10:26:17 +0100 | [diff] [blame] | 278 | if (locations->NeedsSafepoint()) { |
Nicolas Geoffray | c0572a4 | 2015-02-06 14:35:25 +0000 | [diff] [blame] | 279 | if (codegen_->IsLeafMethod()) { |
| 280 | // TODO: We do this here because we do not want the suspend check to artificially |
| 281 | // create live registers. We should find another place, but this is currently the |
| 282 | // simplest. |
| 283 | DCHECK(instruction->IsSuspendCheckEntry()); |
| 284 | instruction->GetBlock()->RemoveInstruction(instruction); |
| 285 | return; |
Nicolas Geoffray | 3bca0df | 2014-09-19 11:01:00 +0100 | [diff] [blame] | 286 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 287 | safepoints_.push_back(instruction); |
Nicolas Geoffray | 3bca0df | 2014-09-19 11:01:00 +0100 | [diff] [blame] | 288 | if (locations->OnlyCallsOnSlowPath()) { |
| 289 | // We add a synthesized range at this position to record the live registers |
| 290 | // at this position. Ideally, we could just update the safepoints when locations |
| 291 | // are updated, but we currently need to know the full stack size before updating |
| 292 | // locations (because of parameters and the fact that we don't have a frame pointer). |
| 293 | // And knowing the full stack size requires to know the maximum number of live |
| 294 | // registers at calls in slow paths. |
| 295 | // By adding the following interval in the algorithm, we can compute this |
| 296 | // maximum before updating locations. |
| 297 | LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); |
Nicolas Geoffray | acd0339 | 2014-11-26 15:46:52 +0000 | [diff] [blame] | 298 | interval->AddRange(position, position + 1); |
Nicolas Geoffray | 87d0376 | 2014-11-19 15:17:56 +0000 | [diff] [blame] | 299 | AddSorted(&unhandled_core_intervals_, interval); |
| 300 | AddSorted(&unhandled_fp_intervals_, interval); |
Nicolas Geoffray | 3bca0df | 2014-09-19 11:01:00 +0100 | [diff] [blame] | 301 | } |
| 302 | } |
| 303 | |
| 304 | if (locations->WillCall()) { |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 305 | BlockRegisters(position, position + 1, /* caller_save_only */ true); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 306 | } |
| 307 | |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame^] | 308 | for (size_t i = 0; i < locations->GetInputCount(); ++i) { |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 309 | Location input = locations->InAt(i); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 310 | if (input.IsRegister() || input.IsFpuRegister()) { |
| 311 | BlockRegister(input, position, position + 1); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 312 | } else if (input.IsPair()) { |
| 313 | BlockRegister(input.ToLow(), position, position + 1); |
| 314 | BlockRegister(input.ToHigh(), position, position + 1); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 315 | } |
| 316 | } |
| 317 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 318 | LiveInterval* current = instruction->GetLiveInterval(); |
| 319 | if (current == nullptr) return; |
| 320 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 321 | ArenaVector<LiveInterval*>& unhandled = core_register |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 322 | ? unhandled_core_intervals_ |
| 323 | : unhandled_fp_intervals_; |
| 324 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 325 | DCHECK(unhandled.empty() || current->StartsBeforeOrAt(unhandled.back())); |
Nicolas Geoffray | 87d0376 | 2014-11-19 15:17:56 +0000 | [diff] [blame] | 326 | |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 327 | if (codegen_->NeedsTwoRegisters(current->GetType())) { |
| 328 | current->AddHighInterval(); |
| 329 | } |
| 330 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 331 | for (size_t safepoint_index = safepoints_.size(); safepoint_index > 0; --safepoint_index) { |
| 332 | HInstruction* safepoint = safepoints_[safepoint_index - 1u]; |
Nicolas Geoffray | 5588e58 | 2015-04-14 14:10:59 +0100 | [diff] [blame] | 333 | size_t safepoint_position = safepoint->GetLifetimePosition(); |
| 334 | |
| 335 | // Test that safepoints are ordered in the optimal way. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 336 | DCHECK(safepoint_index == safepoints_.size() || |
| 337 | safepoints_[safepoint_index]->GetLifetimePosition() < safepoint_position); |
Nicolas Geoffray | 5588e58 | 2015-04-14 14:10:59 +0100 | [diff] [blame] | 338 | |
| 339 | if (safepoint_position == current->GetStart()) { |
| 340 | // The safepoint is for this instruction, so the location of the instruction |
| 341 | // does not need to be saved. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 342 | DCHECK_EQ(safepoint_index, safepoints_.size()); |
Nicolas Geoffray | 5588e58 | 2015-04-14 14:10:59 +0100 | [diff] [blame] | 343 | DCHECK_EQ(safepoint, instruction); |
| 344 | continue; |
| 345 | } else if (current->IsDeadAt(safepoint_position)) { |
| 346 | break; |
| 347 | } else if (!current->Covers(safepoint_position)) { |
| 348 | // Hole in the interval. |
| 349 | continue; |
| 350 | } |
| 351 | current->AddSafepoint(safepoint); |
| 352 | } |
David Brazdil | 3fc992f | 2015-04-16 18:31:55 +0100 | [diff] [blame] | 353 | current->ResetSearchCache(); |
Nicolas Geoffray | 5588e58 | 2015-04-14 14:10:59 +0100 | [diff] [blame] | 354 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 355 | // Some instructions define their output in fixed register/stack slot. We need |
| 356 | // to ensure we know these locations before doing register allocation. For a |
| 357 | // given register, we create an interval that covers these locations. The register |
| 358 | // will be unavailable at these locations when trying to allocate one for an |
| 359 | // interval. |
| 360 | // |
| 361 | // The backwards walking ensures the ranges are ordered on increasing start positions. |
| 362 | Location output = locations->Out(); |
Calin Juravle | d0d4852 | 2014-11-04 16:40:20 +0000 | [diff] [blame] | 363 | if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { |
| 364 | Location first = locations->InAt(0); |
| 365 | if (first.IsRegister() || first.IsFpuRegister()) { |
| 366 | current->SetFrom(position + 1); |
| 367 | current->SetRegister(first.reg()); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 368 | } else if (first.IsPair()) { |
| 369 | current->SetFrom(position + 1); |
| 370 | current->SetRegister(first.low()); |
| 371 | LiveInterval* high = current->GetHighInterval(); |
| 372 | high->SetRegister(first.high()); |
| 373 | high->SetFrom(position + 1); |
Calin Juravle | d0d4852 | 2014-11-04 16:40:20 +0000 | [diff] [blame] | 374 | } |
| 375 | } else if (output.IsRegister() || output.IsFpuRegister()) { |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 376 | // Shift the interval's start by one to account for the blocked register. |
| 377 | current->SetFrom(position + 1); |
Nicolas Geoffray | 56b9ee6 | 2014-10-09 11:47:51 +0100 | [diff] [blame] | 378 | current->SetRegister(output.reg()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 379 | BlockRegister(output, position, position + 1); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 380 | } else if (output.IsPair()) { |
| 381 | current->SetFrom(position + 1); |
| 382 | current->SetRegister(output.low()); |
| 383 | LiveInterval* high = current->GetHighInterval(); |
| 384 | high->SetRegister(output.high()); |
| 385 | high->SetFrom(position + 1); |
| 386 | BlockRegister(output.ToLow(), position, position + 1); |
| 387 | BlockRegister(output.ToHigh(), position, position + 1); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 388 | } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { |
| 389 | current->SetSpillSlot(output.GetStackIndex()); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 390 | } else { |
| 391 | DCHECK(output.IsUnallocated() || output.IsConstant()); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 392 | } |
| 393 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 394 | if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { |
| 395 | AllocateSpillSlotForCatchPhi(instruction->AsPhi()); |
| 396 | } |
| 397 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 398 | // If needed, add interval to the list of unhandled intervals. |
| 399 | if (current->HasSpillSlot() || instruction->IsConstant()) { |
Nicolas Geoffray | c8147a7 | 2014-10-21 16:06:20 +0100 | [diff] [blame] | 400 | // Split just before first register use. |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 401 | size_t first_register_use = current->FirstRegisterUse(); |
| 402 | if (first_register_use != kNoLifetime) { |
Nicolas Geoffray | 8cbab3c | 2015-04-23 15:14:36 +0100 | [diff] [blame] | 403 | LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); |
Nicolas Geoffray | b5f62b3 | 2014-10-30 10:58:41 +0000 | [diff] [blame] | 404 | // Don't add directly to `unhandled`, it needs to be sorted and the start |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 405 | // of this new interval might be after intervals already in the list. |
| 406 | AddSorted(&unhandled, split); |
| 407 | } else { |
| 408 | // Nothing to do, we won't allocate a register for this value. |
| 409 | } |
| 410 | } else { |
Nicolas Geoffray | b5f62b3 | 2014-10-30 10:58:41 +0000 | [diff] [blame] | 411 | // Don't add directly to `unhandled`, temp or safepoint intervals |
| 412 | // for this instruction may have been added, and those can be |
| 413 | // processed first. |
| 414 | AddSorted(&unhandled, current); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 415 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 416 | } |
| 417 | |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 418 | class AllRangesIterator : public ValueObject { |
| 419 | public: |
| 420 | explicit AllRangesIterator(LiveInterval* interval) |
| 421 | : current_interval_(interval), |
| 422 | current_range_(interval->GetFirstRange()) {} |
| 423 | |
| 424 | bool Done() const { return current_interval_ == nullptr; } |
| 425 | LiveRange* CurrentRange() const { return current_range_; } |
| 426 | LiveInterval* CurrentInterval() const { return current_interval_; } |
| 427 | |
| 428 | void Advance() { |
| 429 | current_range_ = current_range_->GetNext(); |
| 430 | if (current_range_ == nullptr) { |
| 431 | current_interval_ = current_interval_->GetNextSibling(); |
| 432 | if (current_interval_ != nullptr) { |
| 433 | current_range_ = current_interval_->GetFirstRange(); |
| 434 | } |
| 435 | } |
| 436 | } |
| 437 | |
| 438 | private: |
| 439 | LiveInterval* current_interval_; |
| 440 | LiveRange* current_range_; |
| 441 | |
| 442 | DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); |
| 443 | }; |
| 444 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 445 | bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { |
| 446 | // To simplify unit testing, we eagerly create the array of intervals, and |
| 447 | // call the helper method. |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 448 | ArenaVector<LiveInterval*> intervals(allocator_->Adapter(kArenaAllocRegisterAllocatorValidate)); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 449 | for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { |
| 450 | HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); |
| 451 | if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 452 | intervals.push_back(instruction->GetLiveInterval()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 453 | } |
| 454 | } |
| 455 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 456 | const ArenaVector<LiveInterval*>* physical_register_intervals = processing_core_registers_ |
| 457 | ? &physical_core_register_intervals_ |
| 458 | : &physical_fp_register_intervals_; |
| 459 | for (LiveInterval* fixed : *physical_register_intervals) { |
| 460 | if (fixed != nullptr) { |
| 461 | intervals.push_back(fixed); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 462 | } |
| 463 | } |
| 464 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 465 | for (LiveInterval* temp : temp_intervals_) { |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 466 | if (ShouldProcess(processing_core_registers_, temp)) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 467 | intervals.push_back(temp); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 468 | } |
| 469 | } |
| 470 | |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 471 | return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_, |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 472 | allocator_, processing_core_registers_, log_fatal_on_failure); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 473 | } |
| 474 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 475 | bool RegisterAllocator::ValidateIntervals(const ArenaVector<LiveInterval*>& intervals, |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 476 | size_t number_of_spill_slots, |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 477 | size_t number_of_out_slots, |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 478 | const CodeGenerator& codegen, |
| 479 | ArenaAllocator* allocator, |
| 480 | bool processing_core_registers, |
| 481 | bool log_fatal_on_failure) { |
| 482 | size_t number_of_registers = processing_core_registers |
| 483 | ? codegen.GetNumberOfCoreRegisters() |
| 484 | : codegen.GetNumberOfFloatingPointRegisters(); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 485 | ArenaVector<ArenaBitVector*> liveness_of_values( |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 486 | allocator->Adapter(kArenaAllocRegisterAllocatorValidate)); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 487 | liveness_of_values.reserve(number_of_registers + number_of_spill_slots); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 488 | |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 489 | size_t max_end = 0u; |
| 490 | for (LiveInterval* start_interval : intervals) { |
| 491 | for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { |
| 492 | max_end = std::max(max_end, it.CurrentRange()->GetEnd()); |
| 493 | } |
| 494 | } |
| 495 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 496 | // Allocate a bit vector per register. A live interval that has a register |
| 497 | // allocated will populate the associated bit vector based on its live ranges. |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 498 | for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 499 | liveness_of_values.push_back( |
| 500 | ArenaBitVector::Create(allocator, max_end, false, kArenaAllocRegisterAllocatorValidate)); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 501 | } |
| 502 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 503 | for (LiveInterval* start_interval : intervals) { |
| 504 | for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 505 | LiveInterval* current = it.CurrentInterval(); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 506 | HInstruction* defined_by = current->GetParent()->GetDefinedBy(); |
| 507 | if (current->GetParent()->HasSpillSlot() |
Nicolas Geoffray | 76b1e17 | 2015-05-27 17:18:33 +0100 | [diff] [blame] | 508 | // Parameters and current method have their own stack slot. |
| 509 | && !(defined_by != nullptr && (defined_by->IsParameterValue() |
| 510 | || defined_by->IsCurrentMethod()))) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 511 | BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 512 | + current->GetParent()->GetSpillSlot() / kVRegSize |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 513 | - number_of_out_slots]; |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 514 | for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { |
| 515 | if (liveness_of_spill_slot->IsBitSet(j)) { |
| 516 | if (log_fatal_on_failure) { |
| 517 | std::ostringstream message; |
| 518 | message << "Spill slot conflict at " << j; |
| 519 | LOG(FATAL) << message.str(); |
| 520 | } else { |
| 521 | return false; |
| 522 | } |
| 523 | } else { |
| 524 | liveness_of_spill_slot->SetBit(j); |
| 525 | } |
| 526 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 527 | } |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 528 | |
| 529 | if (current->HasRegister()) { |
Nicolas Geoffray | 45b83af | 2015-07-06 15:12:53 +0000 | [diff] [blame] | 530 | if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) { |
| 531 | // Only check when an error is fatal. Only tests code ask for non-fatal failures |
| 532 | // and test code may not properly fill the right information to the code generator. |
| 533 | CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister())); |
| 534 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 535 | BitVector* liveness_of_register = liveness_of_values[current->GetRegister()]; |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 536 | for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { |
| 537 | if (liveness_of_register->IsBitSet(j)) { |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 538 | if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { |
| 539 | continue; |
| 540 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 541 | if (log_fatal_on_failure) { |
| 542 | std::ostringstream message; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 543 | message << "Register conflict at " << j << " "; |
| 544 | if (defined_by != nullptr) { |
| 545 | message << "(" << defined_by->DebugName() << ")"; |
| 546 | } |
| 547 | message << "for "; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 548 | if (processing_core_registers) { |
| 549 | codegen.DumpCoreRegister(message, current->GetRegister()); |
| 550 | } else { |
| 551 | codegen.DumpFloatingPointRegister(message, current->GetRegister()); |
| 552 | } |
| 553 | LOG(FATAL) << message.str(); |
| 554 | } else { |
| 555 | return false; |
| 556 | } |
| 557 | } else { |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 558 | liveness_of_register->SetBit(j); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 559 | } |
| 560 | } |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 561 | } |
| 562 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 563 | } |
| 564 | return true; |
| 565 | } |
| 566 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 567 | void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 568 | interval->Dump(stream); |
| 569 | stream << ": "; |
| 570 | if (interval->HasRegister()) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 571 | if (interval->IsFloatingPoint()) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 572 | codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 573 | } else { |
| 574 | codegen_->DumpCoreRegister(stream, interval->GetRegister()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 575 | } |
| 576 | } else { |
| 577 | stream << "spilled"; |
| 578 | } |
| 579 | stream << std::endl; |
| 580 | } |
| 581 | |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 582 | void RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { |
| 583 | stream << "inactive: " << std::endl; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 584 | for (LiveInterval* inactive_interval : inactive_) { |
| 585 | DumpInterval(stream, inactive_interval); |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 586 | } |
| 587 | stream << "active: " << std::endl; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 588 | for (LiveInterval* active_interval : active_) { |
| 589 | DumpInterval(stream, active_interval); |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 590 | } |
| 591 | stream << "unhandled: " << std::endl; |
| 592 | auto unhandled = (unhandled_ != nullptr) ? |
| 593 | unhandled_ : &unhandled_core_intervals_; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 594 | for (LiveInterval* unhandled_interval : *unhandled) { |
| 595 | DumpInterval(stream, unhandled_interval); |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 596 | } |
| 597 | stream << "handled: " << std::endl; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 598 | for (LiveInterval* handled_interval : handled_) { |
| 599 | DumpInterval(stream, handled_interval); |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 600 | } |
| 601 | } |
| 602 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 603 | // By the book implementation of a linear scan register allocator. |
| 604 | void RegisterAllocator::LinearScan() { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 605 | while (!unhandled_->empty()) { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 606 | // (1) Remove interval with the lowest start position from unhandled. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 607 | LiveInterval* current = unhandled_->back(); |
| 608 | unhandled_->pop_back(); |
Nicolas Geoffray | 2e92bc2 | 2015-08-20 19:52:26 +0100 | [diff] [blame] | 609 | |
| 610 | // Make sure the interval is an expected state. |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 611 | DCHECK(!current->IsFixed() && !current->HasSpillSlot()); |
Nicolas Geoffray | 2e92bc2 | 2015-08-20 19:52:26 +0100 | [diff] [blame] | 612 | // Make sure we are going in the right order. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 613 | DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() >= current->GetStart()); |
Nicolas Geoffray | 2e92bc2 | 2015-08-20 19:52:26 +0100 | [diff] [blame] | 614 | // Make sure a low interval is always with a high. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 615 | DCHECK(!current->IsLowInterval() || unhandled_->back()->IsHighInterval()); |
Nicolas Geoffray | 2e92bc2 | 2015-08-20 19:52:26 +0100 | [diff] [blame] | 616 | // Make sure a high interval is always with a low. |
| 617 | DCHECK(current->IsLowInterval() || |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 618 | unhandled_->empty() || |
| 619 | !unhandled_->back()->IsHighInterval()); |
Nicolas Geoffray | 87d0376 | 2014-11-19 15:17:56 +0000 | [diff] [blame] | 620 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 621 | size_t position = current->GetStart(); |
| 622 | |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 623 | // Remember the inactive_ size here since the ones moved to inactive_ from |
| 624 | // active_ below shouldn't need to be re-checked. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 625 | size_t inactive_intervals_to_handle = inactive_.size(); |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 626 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 627 | // (2) Remove currently active intervals that are dead at this position. |
| 628 | // Move active intervals that have a lifetime hole at this position |
| 629 | // to inactive. |
Vladimir Marko | b95fb77 | 2015-09-30 13:32:31 +0100 | [diff] [blame] | 630 | auto active_kept_end = std::remove_if( |
| 631 | active_.begin(), |
| 632 | active_.end(), |
| 633 | [this, position](LiveInterval* interval) { |
| 634 | if (interval->IsDeadAt(position)) { |
| 635 | handled_.push_back(interval); |
| 636 | return true; |
| 637 | } else if (!interval->Covers(position)) { |
| 638 | inactive_.push_back(interval); |
| 639 | return true; |
| 640 | } else { |
| 641 | return false; // Keep this interval. |
| 642 | } |
| 643 | }); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 644 | active_.erase(active_kept_end, active_.end()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 645 | |
| 646 | // (3) Remove currently inactive intervals that are dead at this position. |
| 647 | // Move inactive intervals that cover this position to active. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 648 | auto inactive_to_handle_end = inactive_.begin() + inactive_intervals_to_handle; |
Vladimir Marko | b95fb77 | 2015-09-30 13:32:31 +0100 | [diff] [blame] | 649 | auto inactive_kept_end = std::remove_if( |
| 650 | inactive_.begin(), |
| 651 | inactive_to_handle_end, |
| 652 | [this, position](LiveInterval* interval) { |
| 653 | DCHECK(interval->GetStart() < position || interval->IsFixed()); |
| 654 | if (interval->IsDeadAt(position)) { |
| 655 | handled_.push_back(interval); |
| 656 | return true; |
| 657 | } else if (interval->Covers(position)) { |
| 658 | active_.push_back(interval); |
| 659 | return true; |
| 660 | } else { |
| 661 | return false; // Keep this interval. |
| 662 | } |
| 663 | }); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 664 | inactive_.erase(inactive_kept_end, inactive_to_handle_end); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 665 | |
Nicolas Geoffray | acd0339 | 2014-11-26 15:46:52 +0000 | [diff] [blame] | 666 | if (current->IsSlowPathSafepoint()) { |
| 667 | // Synthesized interval to record the maximum number of live registers |
| 668 | // at safepoints. No need to allocate a register for it. |
Mark Mendell | f85a9ca | 2015-01-13 09:20:58 -0500 | [diff] [blame] | 669 | if (processing_core_registers_) { |
| 670 | maximum_number_of_live_core_registers_ = |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 671 | std::max(maximum_number_of_live_core_registers_, active_.size()); |
Mark Mendell | f85a9ca | 2015-01-13 09:20:58 -0500 | [diff] [blame] | 672 | } else { |
| 673 | maximum_number_of_live_fp_registers_ = |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 674 | std::max(maximum_number_of_live_fp_registers_, active_.size()); |
Mark Mendell | f85a9ca | 2015-01-13 09:20:58 -0500 | [diff] [blame] | 675 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 676 | DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() > current->GetStart()); |
Nicolas Geoffray | acd0339 | 2014-11-26 15:46:52 +0000 | [diff] [blame] | 677 | continue; |
| 678 | } |
| 679 | |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 680 | if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) { |
| 681 | DCHECK(!current->HasRegister()); |
| 682 | // Allocating the low part was unsucessful. The splitted interval for the high part |
| 683 | // will be handled next (it is in the `unhandled_` list). |
| 684 | continue; |
| 685 | } |
| 686 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 687 | // (4) Try to find an available register. |
| 688 | bool success = TryAllocateFreeReg(current); |
| 689 | |
| 690 | // (5) If no register could be found, we need to spill. |
| 691 | if (!success) { |
| 692 | success = AllocateBlockedReg(current); |
| 693 | } |
| 694 | |
| 695 | // (6) If the interval had a register allocated, add it to the list of active |
| 696 | // intervals. |
| 697 | if (success) { |
Nicolas Geoffray | 9889396 | 2015-01-21 12:32:32 +0000 | [diff] [blame] | 698 | codegen_->AddAllocatedRegister(processing_core_registers_ |
| 699 | ? Location::RegisterLocation(current->GetRegister()) |
| 700 | : Location::FpuRegisterLocation(current->GetRegister())); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 701 | active_.push_back(current); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 702 | if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) { |
| 703 | current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister())); |
| 704 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 705 | } |
| 706 | } |
| 707 | } |
| 708 | |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 709 | static void FreeIfNotCoverAt(LiveInterval* interval, size_t position, size_t* free_until) { |
| 710 | DCHECK(!interval->IsHighInterval()); |
| 711 | // Note that the same instruction may occur multiple times in the input list, |
| 712 | // so `free_until` may have changed already. |
David Brazdil | 3fc992f | 2015-04-16 18:31:55 +0100 | [diff] [blame] | 713 | // Since `position` is not the current scan position, we need to use CoversSlow. |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 714 | if (interval->IsDeadAt(position)) { |
| 715 | // Set the register to be free. Note that inactive intervals might later |
| 716 | // update this. |
| 717 | free_until[interval->GetRegister()] = kMaxLifetimePosition; |
| 718 | if (interval->HasHighInterval()) { |
| 719 | DCHECK(interval->GetHighInterval()->IsDeadAt(position)); |
| 720 | free_until[interval->GetHighInterval()->GetRegister()] = kMaxLifetimePosition; |
| 721 | } |
David Brazdil | 3fc992f | 2015-04-16 18:31:55 +0100 | [diff] [blame] | 722 | } else if (!interval->CoversSlow(position)) { |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 723 | // The interval becomes inactive at `defined_by`. We make its register |
| 724 | // available only until the next use strictly after `defined_by`. |
| 725 | free_until[interval->GetRegister()] = interval->FirstUseAfter(position); |
| 726 | if (interval->HasHighInterval()) { |
David Brazdil | 3fc992f | 2015-04-16 18:31:55 +0100 | [diff] [blame] | 727 | DCHECK(!interval->GetHighInterval()->CoversSlow(position)); |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 728 | free_until[interval->GetHighInterval()->GetRegister()] = free_until[interval->GetRegister()]; |
| 729 | } |
| 730 | } |
| 731 | } |
| 732 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 733 | // Find a free register. If multiple are found, pick the register that |
| 734 | // is free the longest. |
| 735 | bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { |
| 736 | size_t* free_until = registers_array_; |
| 737 | |
| 738 | // First set all registers to be free. |
| 739 | for (size_t i = 0; i < number_of_registers_; ++i) { |
| 740 | free_until[i] = kMaxLifetimePosition; |
| 741 | } |
| 742 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 743 | // For each active interval, set its register to not free. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 744 | for (LiveInterval* interval : active_) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 745 | DCHECK(interval->HasRegister()); |
| 746 | free_until[interval->GetRegister()] = 0; |
| 747 | } |
| 748 | |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 749 | // An interval that starts an instruction (that is, it is not split), may |
| 750 | // re-use the registers used by the inputs of that instruciton, based on the |
| 751 | // location summary. |
| 752 | HInstruction* defined_by = current->GetDefinedBy(); |
| 753 | if (defined_by != nullptr && !current->IsSplit()) { |
| 754 | LocationSummary* locations = defined_by->GetLocations(); |
| 755 | if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) { |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame^] | 756 | auto&& inputs = defined_by->GetInputs(); |
| 757 | for (size_t i = 0; i < inputs.size(); ++i) { |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 758 | // Take the last interval of the input. It is the location of that interval |
| 759 | // that will be used at `defined_by`. |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame^] | 760 | LiveInterval* interval = inputs[i]->GetLiveInterval()->GetLastSibling(); |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 761 | // Note that interval may have not been processed yet. |
| 762 | // TODO: Handle non-split intervals last in the work list. |
Nicolas Geoffray | 94015b9 | 2015-06-04 18:21:04 +0100 | [diff] [blame] | 763 | if (locations->InAt(i).IsValid() |
| 764 | && interval->HasRegister() |
| 765 | && interval->SameRegisterKind(*current)) { |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 766 | // The input must be live until the end of `defined_by`, to comply to |
| 767 | // the linear scan algorithm. So we use `defined_by`'s end lifetime |
| 768 | // position to check whether the input is dead or is inactive after |
| 769 | // `defined_by`. |
David Brazdil | 3fc992f | 2015-04-16 18:31:55 +0100 | [diff] [blame] | 770 | DCHECK(interval->CoversSlow(defined_by->GetLifetimePosition())); |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 771 | size_t position = defined_by->GetLifetimePosition() + 1; |
| 772 | FreeIfNotCoverAt(interval, position, free_until); |
| 773 | } |
| 774 | } |
| 775 | } |
| 776 | } |
| 777 | |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 778 | // For each inactive interval, set its register to be free until |
| 779 | // the next intersection with `current`. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 780 | for (LiveInterval* inactive : inactive_) { |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 781 | // Temp/Slow-path-safepoint interval has no holes. |
| 782 | DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); |
| 783 | if (!current->IsSplit() && !inactive->IsFixed()) { |
| 784 | // Neither current nor inactive are fixed. |
| 785 | // Thanks to SSA, a non-split interval starting in a hole of an |
| 786 | // inactive interval should never intersect with that inactive interval. |
| 787 | // Only if it's not fixed though, because fixed intervals don't come from SSA. |
| 788 | DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); |
| 789 | continue; |
| 790 | } |
| 791 | |
| 792 | DCHECK(inactive->HasRegister()); |
| 793 | if (free_until[inactive->GetRegister()] == 0) { |
| 794 | // Already used by some active interval. No need to intersect. |
| 795 | continue; |
| 796 | } |
| 797 | size_t next_intersection = inactive->FirstIntersectionWith(current); |
| 798 | if (next_intersection != kNoLifetime) { |
| 799 | free_until[inactive->GetRegister()] = |
| 800 | std::min(free_until[inactive->GetRegister()], next_intersection); |
| 801 | } |
| 802 | } |
| 803 | |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 804 | int reg = kNoRegister; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 805 | if (current->HasRegister()) { |
| 806 | // Some instructions have a fixed register output. |
| 807 | reg = current->GetRegister(); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 808 | if (free_until[reg] == 0) { |
| 809 | DCHECK(current->IsHighInterval()); |
| 810 | // AllocateBlockedReg will spill the holder of the register. |
| 811 | return false; |
| 812 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 813 | } else { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 814 | DCHECK(!current->IsHighInterval()); |
Nicolas Geoffray | fbda5f3 | 2015-04-29 14:16:00 +0100 | [diff] [blame] | 815 | int hint = current->FindFirstRegisterHint(free_until, liveness_); |
Nicolas Geoffray | f297581 | 2015-08-07 18:13:03 -0700 | [diff] [blame] | 816 | if ((hint != kNoRegister) |
| 817 | // For simplicity, if the hint we are getting for a pair cannot be used, |
| 818 | // we are just going to allocate a new pair. |
| 819 | && !(current->IsLowInterval() && IsBlocked(GetHighForLowRegister(hint)))) { |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 820 | DCHECK(!IsBlocked(hint)); |
| 821 | reg = hint; |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 822 | } else if (current->IsLowInterval()) { |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 823 | reg = FindAvailableRegisterPair(free_until, current->GetStart()); |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 824 | } else { |
Nicolas Geoffray | 8826f67 | 2015-04-17 09:15:11 +0100 | [diff] [blame] | 825 | reg = FindAvailableRegister(free_until, current); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 826 | } |
| 827 | } |
| 828 | |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 829 | DCHECK_NE(reg, kNoRegister); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 830 | // If we could not find a register, we need to spill. |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 831 | if (free_until[reg] == 0) { |
| 832 | return false; |
| 833 | } |
| 834 | |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 835 | if (current->IsLowInterval()) { |
| 836 | // If the high register of this interval is not available, we need to spill. |
| 837 | int high_reg = current->GetHighInterval()->GetRegister(); |
| 838 | if (high_reg == kNoRegister) { |
| 839 | high_reg = GetHighForLowRegister(reg); |
| 840 | } |
| 841 | if (free_until[high_reg] == 0) { |
| 842 | return false; |
| 843 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 844 | } |
| 845 | |
| 846 | current->SetRegister(reg); |
| 847 | if (!current->IsDeadAt(free_until[reg])) { |
| 848 | // If the register is only available for a subset of live ranges |
Nicolas Geoffray | 8272688 | 2015-06-01 13:51:57 +0100 | [diff] [blame] | 849 | // covered by `current`, split `current` before the position where |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 850 | // the register is not available anymore. |
Nicolas Geoffray | 8272688 | 2015-06-01 13:51:57 +0100 | [diff] [blame] | 851 | LiveInterval* split = SplitBetween(current, current->GetStart(), free_until[reg]); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 852 | DCHECK(split != nullptr); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 853 | AddSorted(unhandled_, split); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 854 | } |
| 855 | return true; |
| 856 | } |
| 857 | |
| 858 | bool RegisterAllocator::IsBlocked(int reg) const { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 859 | return processing_core_registers_ |
| 860 | ? blocked_core_registers_[reg] |
| 861 | : blocked_fp_registers_[reg]; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 862 | } |
| 863 | |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 864 | int RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const { |
| 865 | int reg = kNoRegister; |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 866 | // Pick the register pair that is used the last. |
| 867 | for (size_t i = 0; i < number_of_registers_; ++i) { |
| 868 | if (IsBlocked(i)) continue; |
| 869 | if (!IsLowRegister(i)) continue; |
| 870 | int high_register = GetHighForLowRegister(i); |
| 871 | if (IsBlocked(high_register)) continue; |
| 872 | int existing_high_register = GetHighForLowRegister(reg); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 873 | if ((reg == kNoRegister) || (next_use[i] >= next_use[reg] |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 874 | && next_use[high_register] >= next_use[existing_high_register])) { |
| 875 | reg = i; |
| 876 | if (next_use[i] == kMaxLifetimePosition |
| 877 | && next_use[high_register] == kMaxLifetimePosition) { |
| 878 | break; |
| 879 | } |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 880 | } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) { |
| 881 | // If one of the current register is known to be unavailable, just unconditionally |
| 882 | // try a new one. |
| 883 | reg = i; |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 884 | } |
| 885 | } |
| 886 | return reg; |
| 887 | } |
| 888 | |
Nicolas Geoffray | 8826f67 | 2015-04-17 09:15:11 +0100 | [diff] [blame] | 889 | bool RegisterAllocator::IsCallerSaveRegister(int reg) const { |
| 890 | return processing_core_registers_ |
| 891 | ? !codegen_->IsCoreCalleeSaveRegister(reg) |
| 892 | : !codegen_->IsFloatingPointCalleeSaveRegister(reg); |
| 893 | } |
| 894 | |
| 895 | int RegisterAllocator::FindAvailableRegister(size_t* next_use, LiveInterval* current) const { |
| 896 | // We special case intervals that do not span a safepoint to try to find a caller-save |
| 897 | // register if one is available. We iterate from 0 to the number of registers, |
| 898 | // so if there are caller-save registers available at the end, we continue the iteration. |
| 899 | bool prefers_caller_save = !current->HasWillCallSafepoint(); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 900 | int reg = kNoRegister; |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 901 | for (size_t i = 0; i < number_of_registers_; ++i) { |
Nicolas Geoffray | 8826f67 | 2015-04-17 09:15:11 +0100 | [diff] [blame] | 902 | if (IsBlocked(i)) { |
| 903 | // Register cannot be used. Continue. |
| 904 | continue; |
| 905 | } |
| 906 | |
| 907 | // Best case: we found a register fully available. |
| 908 | if (next_use[i] == kMaxLifetimePosition) { |
| 909 | if (prefers_caller_save && !IsCallerSaveRegister(i)) { |
| 910 | // We can get shorter encodings on some platforms by using |
| 911 | // small register numbers. So only update the candidate if the previous |
| 912 | // one was not available for the whole method. |
| 913 | if (reg == kNoRegister || next_use[reg] != kMaxLifetimePosition) { |
| 914 | reg = i; |
| 915 | } |
| 916 | // Continue the iteration in the hope of finding a caller save register. |
| 917 | continue; |
| 918 | } else { |
| 919 | reg = i; |
| 920 | // We know the register is good enough. Return it. |
| 921 | break; |
| 922 | } |
| 923 | } |
| 924 | |
| 925 | // If we had no register before, take this one as a reference. |
| 926 | if (reg == kNoRegister) { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 927 | reg = i; |
Nicolas Geoffray | 8826f67 | 2015-04-17 09:15:11 +0100 | [diff] [blame] | 928 | continue; |
| 929 | } |
| 930 | |
| 931 | // Pick the register that is used the last. |
| 932 | if (next_use[i] > next_use[reg]) { |
| 933 | reg = i; |
| 934 | continue; |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 935 | } |
| 936 | } |
| 937 | return reg; |
| 938 | } |
| 939 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 940 | // Remove interval and its other half if any. Return iterator to the following element. |
| 941 | static ArenaVector<LiveInterval*>::iterator RemoveIntervalAndPotentialOtherHalf( |
| 942 | ArenaVector<LiveInterval*>* intervals, ArenaVector<LiveInterval*>::iterator pos) { |
| 943 | DCHECK(intervals->begin() <= pos && pos < intervals->end()); |
| 944 | LiveInterval* interval = *pos; |
| 945 | if (interval->IsLowInterval()) { |
| 946 | DCHECK(pos + 1 < intervals->end()); |
| 947 | DCHECK_EQ(*(pos + 1), interval->GetHighInterval()); |
| 948 | return intervals->erase(pos, pos + 2); |
| 949 | } else if (interval->IsHighInterval()) { |
| 950 | DCHECK(intervals->begin() < pos); |
| 951 | DCHECK_EQ(*(pos - 1), interval->GetLowInterval()); |
| 952 | return intervals->erase(pos - 1, pos + 1); |
| 953 | } else { |
| 954 | return intervals->erase(pos); |
| 955 | } |
| 956 | } |
| 957 | |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 958 | bool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, |
| 959 | size_t first_register_use, |
| 960 | size_t* next_use) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 961 | for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { |
| 962 | LiveInterval* active = *it; |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 963 | DCHECK(active->HasRegister()); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 964 | if (active->IsFixed()) continue; |
| 965 | if (active->IsHighInterval()) continue; |
| 966 | if (first_register_use > next_use[active->GetRegister()]) continue; |
| 967 | |
Nicolas Geoffray | 2e92bc2 | 2015-08-20 19:52:26 +0100 | [diff] [blame] | 968 | // Split the first interval found that is either: |
| 969 | // 1) A non-pair interval. |
| 970 | // 2) A pair interval whose high is not low + 1. |
| 971 | // 3) A pair interval whose low is not even. |
| 972 | if (!active->IsLowInterval() || |
| 973 | IsLowOfUnalignedPairInterval(active) || |
| 974 | !IsLowRegister(active->GetRegister())) { |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 975 | LiveInterval* split = Split(active, position); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 976 | if (split != active) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 977 | handled_.push_back(active); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 978 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 979 | RemoveIntervalAndPotentialOtherHalf(&active_, it); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 980 | AddSorted(unhandled_, split); |
| 981 | return true; |
| 982 | } |
| 983 | } |
| 984 | return false; |
| 985 | } |
| 986 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 987 | // Find the register that is used the last, and spill the interval |
| 988 | // that holds it. If the first use of `current` is after that register |
| 989 | // we spill `current` instead. |
| 990 | bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { |
| 991 | size_t first_register_use = current->FirstRegisterUse(); |
Nicolas Geoffray | da2b254 | 2015-08-06 19:56:45 -0700 | [diff] [blame] | 992 | if (current->HasRegister()) { |
| 993 | DCHECK(current->IsHighInterval()); |
| 994 | // The low interval has allocated the register for the high interval. In |
| 995 | // case the low interval had to split both intervals, we may end up in a |
| 996 | // situation where the high interval does not have a register use anymore. |
| 997 | // We must still proceed in order to split currently active and inactive |
| 998 | // uses of the high interval's register, and put the high interval in the |
| 999 | // active set. |
| 1000 | DCHECK(first_register_use != kNoLifetime || (current->GetNextSibling() != nullptr)); |
| 1001 | } else if (first_register_use == kNoLifetime) { |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 1002 | AllocateSpillSlotFor(current); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1003 | return false; |
| 1004 | } |
| 1005 | |
| 1006 | // First set all registers as not being used. |
| 1007 | size_t* next_use = registers_array_; |
| 1008 | for (size_t i = 0; i < number_of_registers_; ++i) { |
| 1009 | next_use[i] = kMaxLifetimePosition; |
| 1010 | } |
| 1011 | |
| 1012 | // For each active interval, find the next use of its register after the |
| 1013 | // start of current. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1014 | for (LiveInterval* active : active_) { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1015 | DCHECK(active->HasRegister()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1016 | if (active->IsFixed()) { |
| 1017 | next_use[active->GetRegister()] = current->GetStart(); |
| 1018 | } else { |
Nicolas Geoffray | 119a885 | 2016-02-06 17:01:15 +0000 | [diff] [blame] | 1019 | size_t use = active->FirstRegisterUseAfter(current->GetStart()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1020 | if (use != kNoLifetime) { |
| 1021 | next_use[active->GetRegister()] = use; |
| 1022 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1023 | } |
| 1024 | } |
| 1025 | |
| 1026 | // For each inactive interval, find the next use of its register after the |
| 1027 | // start of current. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1028 | for (LiveInterval* inactive : inactive_) { |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 1029 | // Temp/Slow-path-safepoint interval has no holes. |
| 1030 | DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); |
| 1031 | if (!current->IsSplit() && !inactive->IsFixed()) { |
| 1032 | // Neither current nor inactive are fixed. |
| 1033 | // Thanks to SSA, a non-split interval starting in a hole of an |
| 1034 | // inactive interval should never intersect with that inactive interval. |
| 1035 | // Only if it's not fixed though, because fixed intervals don't come from SSA. |
| 1036 | DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); |
| 1037 | continue; |
| 1038 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1039 | DCHECK(inactive->HasRegister()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1040 | size_t next_intersection = inactive->FirstIntersectionWith(current); |
| 1041 | if (next_intersection != kNoLifetime) { |
| 1042 | if (inactive->IsFixed()) { |
| 1043 | next_use[inactive->GetRegister()] = |
| 1044 | std::min(next_intersection, next_use[inactive->GetRegister()]); |
| 1045 | } else { |
Nicolas Geoffray | 1ba1981 | 2015-04-21 09:12:40 +0100 | [diff] [blame] | 1046 | size_t use = inactive->FirstUseAfter(current->GetStart()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1047 | if (use != kNoLifetime) { |
| 1048 | next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); |
| 1049 | } |
| 1050 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1051 | } |
| 1052 | } |
| 1053 | |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1054 | int reg = kNoRegister; |
| 1055 | bool should_spill = false; |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1056 | if (current->HasRegister()) { |
| 1057 | DCHECK(current->IsHighInterval()); |
| 1058 | reg = current->GetRegister(); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1059 | // When allocating the low part, we made sure the high register was available. |
Nicolas Geoffray | 119a885 | 2016-02-06 17:01:15 +0000 | [diff] [blame] | 1060 | DCHECK_LT(first_register_use, next_use[reg]); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1061 | } else if (current->IsLowInterval()) { |
Nicolas Geoffray | 119a885 | 2016-02-06 17:01:15 +0000 | [diff] [blame] | 1062 | reg = FindAvailableRegisterPair(next_use, first_register_use); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1063 | // We should spill if both registers are not available. |
Nicolas Geoffray | 119a885 | 2016-02-06 17:01:15 +0000 | [diff] [blame] | 1064 | should_spill = (first_register_use >= next_use[reg]) |
| 1065 | || (first_register_use >= next_use[GetHighForLowRegister(reg)]); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1066 | } else { |
| 1067 | DCHECK(!current->IsHighInterval()); |
Nicolas Geoffray | 8826f67 | 2015-04-17 09:15:11 +0100 | [diff] [blame] | 1068 | reg = FindAvailableRegister(next_use, current); |
Nicolas Geoffray | 119a885 | 2016-02-06 17:01:15 +0000 | [diff] [blame] | 1069 | should_spill = (first_register_use >= next_use[reg]); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1070 | } |
| 1071 | |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1072 | DCHECK_NE(reg, kNoRegister); |
| 1073 | if (should_spill) { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1074 | DCHECK(!current->IsHighInterval()); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1075 | bool is_allocation_at_use_site = (current->GetStart() >= (first_register_use - 1)); |
Nicolas Geoffray | da2b254 | 2015-08-06 19:56:45 -0700 | [diff] [blame] | 1076 | if (is_allocation_at_use_site) { |
| 1077 | if (!current->IsLowInterval()) { |
| 1078 | DumpInterval(std::cerr, current); |
| 1079 | DumpAllIntervals(std::cerr); |
| 1080 | // This situation has the potential to infinite loop, so we make it a non-debug CHECK. |
| 1081 | HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2); |
| 1082 | CHECK(false) << "There is not enough registers available for " |
| 1083 | << current->GetParent()->GetDefinedBy()->DebugName() << " " |
| 1084 | << current->GetParent()->GetDefinedBy()->GetId() |
| 1085 | << " at " << first_register_use - 1 << " " |
| 1086 | << (at == nullptr ? "" : at->DebugName()); |
| 1087 | } |
| 1088 | |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1089 | // If we're allocating a register for `current` because the instruction at |
| 1090 | // that position requires it, but we think we should spill, then there are |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1091 | // non-pair intervals or unaligned pair intervals blocking the allocation. |
| 1092 | // We split the first interval found, and put ourselves first in the |
| 1093 | // `unhandled_` list. |
Nicolas Geoffray | da2b254 | 2015-08-06 19:56:45 -0700 | [diff] [blame] | 1094 | bool success = TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(), |
| 1095 | first_register_use, |
| 1096 | next_use); |
| 1097 | DCHECK(success); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1098 | LiveInterval* existing = unhandled_->back(); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1099 | DCHECK(existing->IsHighInterval()); |
| 1100 | DCHECK_EQ(existing->GetLowInterval(), current); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1101 | unhandled_->push_back(current); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1102 | } else { |
| 1103 | // If the first use of that instruction is after the last use of the found |
| 1104 | // register, we split this interval just before its first register use. |
| 1105 | AllocateSpillSlotFor(current); |
Nicolas Geoffray | 8cbab3c | 2015-04-23 15:14:36 +0100 | [diff] [blame] | 1106 | LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); |
Nicolas Geoffray | da2b254 | 2015-08-06 19:56:45 -0700 | [diff] [blame] | 1107 | DCHECK(current != split); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1108 | AddSorted(unhandled_, split); |
| 1109 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1110 | return false; |
| 1111 | } else { |
| 1112 | // Use this register and spill the active and inactives interval that |
| 1113 | // have that register. |
| 1114 | current->SetRegister(reg); |
| 1115 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1116 | for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { |
| 1117 | LiveInterval* active = *it; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1118 | if (active->GetRegister() == reg) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1119 | DCHECK(!active->IsFixed()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1120 | LiveInterval* split = Split(active, current->GetStart()); |
Nicolas Geoffray | dd8f887 | 2015-01-15 15:37:37 +0000 | [diff] [blame] | 1121 | if (split != active) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1122 | handled_.push_back(active); |
Nicolas Geoffray | dd8f887 | 2015-01-15 15:37:37 +0000 | [diff] [blame] | 1123 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1124 | RemoveIntervalAndPotentialOtherHalf(&active_, it); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1125 | AddSorted(unhandled_, split); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1126 | break; |
| 1127 | } |
| 1128 | } |
| 1129 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1130 | // NOTE: Retrieve end() on each iteration because we're removing elements in the loop body. |
| 1131 | for (auto it = inactive_.begin(); it != inactive_.end(); ) { |
| 1132 | LiveInterval* inactive = *it; |
| 1133 | bool erased = false; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1134 | if (inactive->GetRegister() == reg) { |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 1135 | if (!current->IsSplit() && !inactive->IsFixed()) { |
| 1136 | // Neither current nor inactive are fixed. |
| 1137 | // Thanks to SSA, a non-split interval starting in a hole of an |
| 1138 | // inactive interval should never intersect with that inactive interval. |
| 1139 | // Only if it's not fixed though, because fixed intervals don't come from SSA. |
| 1140 | DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1141 | } else { |
| 1142 | size_t next_intersection = inactive->FirstIntersectionWith(current); |
| 1143 | if (next_intersection != kNoLifetime) { |
| 1144 | if (inactive->IsFixed()) { |
| 1145 | LiveInterval* split = Split(current, next_intersection); |
| 1146 | DCHECK_NE(split, current); |
| 1147 | AddSorted(unhandled_, split); |
| 1148 | } else { |
| 1149 | // Split at the start of `current`, which will lead to splitting |
| 1150 | // at the end of the lifetime hole of `inactive`. |
| 1151 | LiveInterval* split = Split(inactive, current->GetStart()); |
| 1152 | // If it's inactive, it must start before the current interval. |
| 1153 | DCHECK_NE(split, inactive); |
| 1154 | it = RemoveIntervalAndPotentialOtherHalf(&inactive_, it); |
| 1155 | erased = true; |
| 1156 | handled_.push_back(inactive); |
| 1157 | AddSorted(unhandled_, split); |
Nicolas Geoffray | 5b168de | 2015-03-27 10:27:22 +0000 | [diff] [blame] | 1158 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1159 | } |
| 1160 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1161 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1162 | // If we have erased the element, `it` already points to the next element. |
| 1163 | // Otherwise we need to move to the next element. |
| 1164 | if (!erased) { |
| 1165 | ++it; |
| 1166 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1167 | } |
| 1168 | |
| 1169 | return true; |
| 1170 | } |
| 1171 | } |
| 1172 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1173 | void RegisterAllocator::AddSorted(ArenaVector<LiveInterval*>* array, LiveInterval* interval) { |
Nicolas Geoffray | c8147a7 | 2014-10-21 16:06:20 +0100 | [diff] [blame] | 1174 | DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1175 | size_t insert_at = 0; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1176 | for (size_t i = array->size(); i > 0; --i) { |
| 1177 | LiveInterval* current = (*array)[i - 1u]; |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1178 | // High intervals must be processed right after their low equivalent. |
| 1179 | if (current->StartsAfter(interval) && !current->IsHighInterval()) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1180 | insert_at = i; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1181 | break; |
Nicolas Geoffray | acd0339 | 2014-11-26 15:46:52 +0000 | [diff] [blame] | 1182 | } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { |
| 1183 | // Ensure the slow path interval is the last to be processed at its location: we want the |
| 1184 | // interval to know all live registers at this location. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1185 | DCHECK(i == 1 || (*array)[i - 2u]->StartsAfter(current)); |
Nicolas Geoffray | acd0339 | 2014-11-26 15:46:52 +0000 | [diff] [blame] | 1186 | insert_at = i; |
| 1187 | break; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1188 | } |
| 1189 | } |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1190 | |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1191 | // Insert the high interval before the low, to ensure the low is processed before. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1192 | auto insert_pos = array->begin() + insert_at; |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1193 | if (interval->HasHighInterval()) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1194 | array->insert(insert_pos, { interval->GetHighInterval(), interval }); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1195 | } else if (interval->HasLowInterval()) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1196 | array->insert(insert_pos, { interval, interval->GetLowInterval() }); |
| 1197 | } else { |
| 1198 | array->insert(insert_pos, interval); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1199 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1200 | } |
| 1201 | |
Nicolas Geoffray | 8cbab3c | 2015-04-23 15:14:36 +0100 | [diff] [blame] | 1202 | LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { |
Nicolas Geoffray | fbda5f3 | 2015-04-29 14:16:00 +0100 | [diff] [blame] | 1203 | HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2); |
| 1204 | HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2); |
Nicolas Geoffray | 8cbab3c | 2015-04-23 15:14:36 +0100 | [diff] [blame] | 1205 | DCHECK(block_from != nullptr); |
| 1206 | DCHECK(block_to != nullptr); |
| 1207 | |
| 1208 | // Both locations are in the same block. We split at the given location. |
| 1209 | if (block_from == block_to) { |
| 1210 | return Split(interval, to); |
| 1211 | } |
| 1212 | |
Nicolas Geoffray | fbda5f3 | 2015-04-29 14:16:00 +0100 | [diff] [blame] | 1213 | /* |
| 1214 | * Non-linear control flow will force moves at every branch instruction to the new location. |
| 1215 | * To avoid having all branches doing the moves, we find the next non-linear position and |
| 1216 | * split the interval at this position. Take the following example (block number is the linear |
| 1217 | * order position): |
| 1218 | * |
| 1219 | * B1 |
| 1220 | * / \ |
| 1221 | * B2 B3 |
| 1222 | * \ / |
| 1223 | * B4 |
| 1224 | * |
| 1225 | * B2 needs to split an interval, whose next use is in B4. If we were to split at the |
| 1226 | * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval |
| 1227 | * is now in the correct location. It makes performance worst if the interval is spilled |
| 1228 | * and both B2 and B3 need to reload it before entering B4. |
| 1229 | * |
| 1230 | * By splitting at B3, we give a chance to the register allocator to allocate the |
| 1231 | * interval to the same register as in B1, and therefore avoid doing any |
| 1232 | * moves in B3. |
| 1233 | */ |
| 1234 | if (block_from->GetDominator() != nullptr) { |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 1235 | for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) { |
| 1236 | size_t position = dominated->GetLifetimeStart(); |
Nicolas Geoffray | fbda5f3 | 2015-04-29 14:16:00 +0100 | [diff] [blame] | 1237 | if ((position > from) && (block_to->GetLifetimeStart() > position)) { |
| 1238 | // Even if we found a better block, we continue iterating in case |
| 1239 | // a dominated block is closer. |
| 1240 | // Note that dominated blocks are not sorted in liveness order. |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 1241 | block_to = dominated; |
Nicolas Geoffray | fbda5f3 | 2015-04-29 14:16:00 +0100 | [diff] [blame] | 1242 | DCHECK_NE(block_to, block_from); |
| 1243 | } |
| 1244 | } |
| 1245 | } |
| 1246 | |
Nicolas Geoffray | 8cbab3c | 2015-04-23 15:14:36 +0100 | [diff] [blame] | 1247 | // If `to` is in a loop, find the outermost loop header which does not contain `from`. |
| 1248 | for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { |
| 1249 | HBasicBlock* header = it.Current()->GetHeader(); |
| 1250 | if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { |
| 1251 | break; |
| 1252 | } |
| 1253 | block_to = header; |
| 1254 | } |
| 1255 | |
| 1256 | // Split at the start of the found block, to piggy back on existing moves |
| 1257 | // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). |
| 1258 | return Split(interval, block_to->GetLifetimeStart()); |
| 1259 | } |
| 1260 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1261 | LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1262 | DCHECK_GE(position, interval->GetStart()); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1263 | DCHECK(!interval->IsDeadAt(position)); |
| 1264 | if (position == interval->GetStart()) { |
| 1265 | // Spill slot will be allocated when handling `interval` again. |
| 1266 | interval->ClearRegister(); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1267 | if (interval->HasHighInterval()) { |
| 1268 | interval->GetHighInterval()->ClearRegister(); |
| 1269 | } else if (interval->HasLowInterval()) { |
| 1270 | interval->GetLowInterval()->ClearRegister(); |
| 1271 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1272 | return interval; |
| 1273 | } else { |
| 1274 | LiveInterval* new_interval = interval->SplitAt(position); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1275 | if (interval->HasHighInterval()) { |
| 1276 | LiveInterval* high = interval->GetHighInterval()->SplitAt(position); |
| 1277 | new_interval->SetHighInterval(high); |
| 1278 | high->SetLowInterval(new_interval); |
| 1279 | } else if (interval->HasLowInterval()) { |
| 1280 | LiveInterval* low = interval->GetLowInterval()->SplitAt(position); |
| 1281 | new_interval->SetLowInterval(low); |
| 1282 | low->SetHighInterval(new_interval); |
| 1283 | } |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1284 | return new_interval; |
| 1285 | } |
| 1286 | } |
| 1287 | |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 1288 | void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1289 | if (interval->IsHighInterval()) { |
Nicolas Geoffray | da2b254 | 2015-08-06 19:56:45 -0700 | [diff] [blame] | 1290 | // The low interval already took care of allocating the spill slot. |
| 1291 | DCHECK(!interval->GetLowInterval()->HasRegister()); |
| 1292 | DCHECK(interval->GetLowInterval()->GetParent()->HasSpillSlot()); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1293 | return; |
| 1294 | } |
| 1295 | |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 1296 | LiveInterval* parent = interval->GetParent(); |
| 1297 | |
| 1298 | // An instruction gets a spill slot for its entire lifetime. If the parent |
| 1299 | // of this interval already has a spill slot, there is nothing to do. |
| 1300 | if (parent->HasSpillSlot()) { |
| 1301 | return; |
| 1302 | } |
| 1303 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1304 | HInstruction* defined_by = parent->GetDefinedBy(); |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1305 | DCHECK(!defined_by->IsPhi() || !defined_by->AsPhi()->IsCatchPhi()); |
| 1306 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1307 | if (defined_by->IsParameterValue()) { |
| 1308 | // Parameters have their own stack slot. |
| 1309 | parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); |
| 1310 | return; |
| 1311 | } |
| 1312 | |
Nicolas Geoffray | 76b1e17 | 2015-05-27 17:18:33 +0100 | [diff] [blame] | 1313 | if (defined_by->IsCurrentMethod()) { |
| 1314 | parent->SetSpillSlot(0); |
| 1315 | return; |
| 1316 | } |
| 1317 | |
Nicolas Geoffray | 96f89a2 | 2014-07-11 10:57:49 +0100 | [diff] [blame] | 1318 | if (defined_by->IsConstant()) { |
| 1319 | // Constants don't need a spill slot. |
| 1320 | return; |
| 1321 | } |
| 1322 | |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1323 | ArenaVector<size_t>* spill_slots = nullptr; |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1324 | switch (interval->GetType()) { |
| 1325 | case Primitive::kPrimDouble: |
| 1326 | spill_slots = &double_spill_slots_; |
| 1327 | break; |
| 1328 | case Primitive::kPrimLong: |
| 1329 | spill_slots = &long_spill_slots_; |
| 1330 | break; |
| 1331 | case Primitive::kPrimFloat: |
| 1332 | spill_slots = &float_spill_slots_; |
| 1333 | break; |
| 1334 | case Primitive::kPrimNot: |
| 1335 | case Primitive::kPrimInt: |
| 1336 | case Primitive::kPrimChar: |
| 1337 | case Primitive::kPrimByte: |
| 1338 | case Primitive::kPrimBoolean: |
| 1339 | case Primitive::kPrimShort: |
| 1340 | spill_slots = &int_spill_slots_; |
| 1341 | break; |
| 1342 | case Primitive::kPrimVoid: |
| 1343 | LOG(FATAL) << "Unexpected type for interval " << interval->GetType(); |
| 1344 | } |
| 1345 | |
Nicolas Geoffray | 412f10c | 2014-06-19 10:00:34 +0100 | [diff] [blame] | 1346 | // Find an available spill slot. |
| 1347 | size_t slot = 0; |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1348 | for (size_t e = spill_slots->size(); slot < e; ++slot) { |
| 1349 | if ((*spill_slots)[slot] <= parent->GetStart() |
| 1350 | && (slot == (e - 1) || (*spill_slots)[slot + 1] <= parent->GetStart())) { |
Nicolas Geoffray | 412f10c | 2014-06-19 10:00:34 +0100 | [diff] [blame] | 1351 | break; |
| 1352 | } |
| 1353 | } |
| 1354 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1355 | size_t end = interval->GetLastSibling()->GetEnd(); |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1356 | if (parent->NeedsTwoSpillSlots()) { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1357 | if (slot + 2u > spill_slots->size()) { |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 1358 | // We need a new spill slot. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1359 | spill_slots->resize(slot + 2u, end); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 1360 | } |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1361 | (*spill_slots)[slot] = end; |
| 1362 | (*spill_slots)[slot + 1] = end; |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 1363 | } else { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1364 | if (slot == spill_slots->size()) { |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 1365 | // We need a new spill slot. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1366 | spill_slots->push_back(end); |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 1367 | } else { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1368 | (*spill_slots)[slot] = end; |
Nicolas Geoffray | 3c04974 | 2014-09-24 18:10:46 +0100 | [diff] [blame] | 1369 | } |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 1370 | } |
| 1371 | |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1372 | // Note that the exact spill slot location will be computed when we resolve, |
| 1373 | // that is when we know the number of spill slots for each type. |
| 1374 | parent->SetSpillSlot(slot); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1375 | } |
| 1376 | |
Nicolas Geoffray | 2a877f3 | 2014-09-10 10:49:34 +0100 | [diff] [blame] | 1377 | static bool IsValidDestination(Location destination) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 1378 | return destination.IsRegister() |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1379 | || destination.IsRegisterPair() |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 1380 | || destination.IsFpuRegister() |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1381 | || destination.IsFpuRegisterPair() |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 1382 | || destination.IsStackSlot() |
| 1383 | || destination.IsDoubleStackSlot(); |
Nicolas Geoffray | 2a877f3 | 2014-09-10 10:49:34 +0100 | [diff] [blame] | 1384 | } |
| 1385 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1386 | void RegisterAllocator::AllocateSpillSlotForCatchPhi(HPhi* phi) { |
| 1387 | LiveInterval* interval = phi->GetLiveInterval(); |
| 1388 | |
| 1389 | HInstruction* previous_phi = phi->GetPrevious(); |
| 1390 | DCHECK(previous_phi == nullptr || |
| 1391 | previous_phi->AsPhi()->GetRegNumber() <= phi->GetRegNumber()) |
| 1392 | << "Phis expected to be sorted by vreg number, so that equivalent phis are adjacent."; |
| 1393 | |
| 1394 | if (phi->IsVRegEquivalentOf(previous_phi)) { |
| 1395 | // This is an equivalent of the previous phi. We need to assign the same |
| 1396 | // catch phi slot. |
| 1397 | DCHECK(previous_phi->GetLiveInterval()->HasSpillSlot()); |
| 1398 | interval->SetSpillSlot(previous_phi->GetLiveInterval()->GetSpillSlot()); |
| 1399 | } else { |
| 1400 | // Allocate a new spill slot for this catch phi. |
| 1401 | // TODO: Reuse spill slots when intervals of phis from different catch |
| 1402 | // blocks do not overlap. |
| 1403 | interval->SetSpillSlot(catch_phi_spill_slots_); |
| 1404 | catch_phi_spill_slots_ += interval->NeedsTwoSpillSlots() ? 2 : 1; |
| 1405 | } |
| 1406 | } |
| 1407 | |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1408 | void RegisterAllocator::AddMove(HParallelMove* move, |
| 1409 | Location source, |
| 1410 | Location destination, |
| 1411 | HInstruction* instruction, |
| 1412 | Primitive::Type type) const { |
| 1413 | if (type == Primitive::kPrimLong |
| 1414 | && codegen_->ShouldSplitLongMoves() |
| 1415 | // The parallel move resolver knows how to deal with long constants. |
| 1416 | && !source.IsConstant()) { |
Nicolas Geoffray | 9021825 | 2015-04-15 11:56:51 +0100 | [diff] [blame] | 1417 | move->AddMove(source.ToLow(), destination.ToLow(), Primitive::kPrimInt, instruction); |
| 1418 | move->AddMove(source.ToHigh(), destination.ToHigh(), Primitive::kPrimInt, nullptr); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1419 | } else { |
Nicolas Geoffray | 9021825 | 2015-04-15 11:56:51 +0100 | [diff] [blame] | 1420 | move->AddMove(source, destination, type, instruction); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1421 | } |
| 1422 | } |
| 1423 | |
| 1424 | void RegisterAllocator::AddInputMoveFor(HInstruction* input, |
| 1425 | HInstruction* user, |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1426 | Location source, |
| 1427 | Location destination) const { |
| 1428 | if (source.Equals(destination)) return; |
| 1429 | |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 1430 | DCHECK(!user->IsPhi()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1431 | |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1432 | HInstruction* previous = user->GetPrevious(); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1433 | HParallelMove* move = nullptr; |
| 1434 | if (previous == nullptr |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 1435 | || !previous->IsParallelMove() |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 1436 | || previous->GetLifetimePosition() < user->GetLifetimePosition()) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1437 | move = new (allocator_) HParallelMove(allocator_); |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 1438 | move->SetLifetimePosition(user->GetLifetimePosition()); |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1439 | user->GetBlock()->InsertInstructionBefore(move, user); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1440 | } else { |
| 1441 | move = previous->AsParallelMove(); |
| 1442 | } |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 1443 | DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1444 | AddMove(move, source, destination, nullptr, input->GetType()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1445 | } |
| 1446 | |
Nicolas Geoffray | 46fbaab | 2014-11-26 18:30:23 +0000 | [diff] [blame] | 1447 | static bool IsInstructionStart(size_t position) { |
| 1448 | return (position & 1) == 0; |
| 1449 | } |
| 1450 | |
| 1451 | static bool IsInstructionEnd(size_t position) { |
| 1452 | return (position & 1) == 1; |
| 1453 | } |
| 1454 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1455 | void RegisterAllocator::InsertParallelMoveAt(size_t position, |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1456 | HInstruction* instruction, |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1457 | Location source, |
| 1458 | Location destination) const { |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1459 | DCHECK(IsValidDestination(destination)) << destination; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1460 | if (source.Equals(destination)) return; |
| 1461 | |
| 1462 | HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1463 | HParallelMove* move; |
Nicolas Geoffray | 46fbaab | 2014-11-26 18:30:23 +0000 | [diff] [blame] | 1464 | if (at == nullptr) { |
| 1465 | if (IsInstructionStart(position)) { |
| 1466 | // Block boundary, don't do anything the connection of split siblings will handle it. |
| 1467 | return; |
| 1468 | } else { |
| 1469 | // Move must happen before the first instruction of the block. |
| 1470 | at = liveness_.GetInstructionFromPosition((position + 1) / 2); |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 1471 | // Note that parallel moves may have already been inserted, so we explicitly |
| 1472 | // ask for the first instruction of the block: `GetInstructionFromPosition` does |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1473 | // not contain the `HParallelMove` instructions. |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 1474 | at = at->GetBlock()->GetFirstInstruction(); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1475 | |
| 1476 | if (at->GetLifetimePosition() < position) { |
| 1477 | // We may insert moves for split siblings and phi spills at the beginning of the block. |
| 1478 | // Since this is a different lifetime position, we need to go to the next instruction. |
| 1479 | DCHECK(at->IsParallelMove()); |
| 1480 | at = at->GetNext(); |
| 1481 | } |
| 1482 | |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 1483 | if (at->GetLifetimePosition() != position) { |
| 1484 | DCHECK_GT(at->GetLifetimePosition(), position); |
Nicolas Geoffray | 46fbaab | 2014-11-26 18:30:23 +0000 | [diff] [blame] | 1485 | move = new (allocator_) HParallelMove(allocator_); |
| 1486 | move->SetLifetimePosition(position); |
| 1487 | at->GetBlock()->InsertInstructionBefore(move, at); |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 1488 | } else { |
| 1489 | DCHECK(at->IsParallelMove()); |
| 1490 | move = at->AsParallelMove(); |
Nicolas Geoffray | 46fbaab | 2014-11-26 18:30:23 +0000 | [diff] [blame] | 1491 | } |
| 1492 | } |
| 1493 | } else if (IsInstructionEnd(position)) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1494 | // Move must happen after the instruction. |
| 1495 | DCHECK(!at->IsControlFlow()); |
| 1496 | move = at->GetNext()->AsParallelMove(); |
Nicolas Geoffray | e27f31a | 2014-06-12 17:53:14 +0100 | [diff] [blame] | 1497 | // This is a parallel move for connecting siblings in a same block. We need to |
| 1498 | // differentiate it with moves for connecting blocks, and input moves. |
Nicolas Geoffray | 8e3964b | 2014-10-17 11:06:38 +0100 | [diff] [blame] | 1499 | if (move == nullptr || move->GetLifetimePosition() > position) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1500 | move = new (allocator_) HParallelMove(allocator_); |
| 1501 | move->SetLifetimePosition(position); |
| 1502 | at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); |
| 1503 | } |
| 1504 | } else { |
| 1505 | // Move must happen before the instruction. |
| 1506 | HInstruction* previous = at->GetPrevious(); |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1507 | if (previous == nullptr |
| 1508 | || !previous->IsParallelMove() |
| 1509 | || previous->GetLifetimePosition() != position) { |
| 1510 | // If the previous is a parallel move, then its position must be lower |
| 1511 | // than the given `position`: it was added just after the non-parallel |
| 1512 | // move instruction that precedes `instruction`. |
| 1513 | DCHECK(previous == nullptr |
| 1514 | || !previous->IsParallelMove() |
| 1515 | || previous->GetLifetimePosition() < position); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1516 | move = new (allocator_) HParallelMove(allocator_); |
| 1517 | move->SetLifetimePosition(position); |
| 1518 | at->GetBlock()->InsertInstructionBefore(move, at); |
| 1519 | } else { |
| 1520 | move = previous->AsParallelMove(); |
| 1521 | } |
| 1522 | } |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1523 | DCHECK_EQ(move->GetLifetimePosition(), position); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1524 | AddMove(move, source, destination, instruction, instruction->GetType()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1525 | } |
| 1526 | |
| 1527 | void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1528 | HInstruction* instruction, |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1529 | Location source, |
| 1530 | Location destination) const { |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1531 | DCHECK(IsValidDestination(destination)) << destination; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1532 | if (source.Equals(destination)) return; |
| 1533 | |
David Brazdil | d26a411 | 2015-11-10 11:07:31 +0000 | [diff] [blame] | 1534 | DCHECK_EQ(block->GetNormalSuccessors().size(), 1u); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1535 | HInstruction* last = block->GetLastInstruction(); |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 1536 | // We insert moves at exit for phi predecessors and connecting blocks. |
Mark Mendell | fe57faa | 2015-09-18 09:26:15 -0400 | [diff] [blame] | 1537 | // A block ending with an if or a packed switch cannot branch to a block |
| 1538 | // with phis because we do not allow critical edges. It can also not connect |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 1539 | // a split interval between two blocks: the move has to happen in the successor. |
Mark Mendell | fe57faa | 2015-09-18 09:26:15 -0400 | [diff] [blame] | 1540 | DCHECK(!last->IsIf() && !last->IsPackedSwitch()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1541 | HInstruction* previous = last->GetPrevious(); |
| 1542 | HParallelMove* move; |
Nicolas Geoffray | e27f31a | 2014-06-12 17:53:14 +0100 | [diff] [blame] | 1543 | // This is a parallel move for connecting blocks. We need to differentiate |
| 1544 | // it with moves for connecting siblings in a same block, and output moves. |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 1545 | size_t position = last->GetLifetimePosition(); |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1546 | if (previous == nullptr || !previous->IsParallelMove() |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 1547 | || previous->AsParallelMove()->GetLifetimePosition() != position) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1548 | move = new (allocator_) HParallelMove(allocator_); |
Nicolas Geoffray | 5976857 | 2014-12-01 09:50:04 +0000 | [diff] [blame] | 1549 | move->SetLifetimePosition(position); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1550 | block->InsertInstructionBefore(move, last); |
| 1551 | } else { |
| 1552 | move = previous->AsParallelMove(); |
| 1553 | } |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1554 | AddMove(move, source, destination, instruction, instruction->GetType()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1555 | } |
| 1556 | |
| 1557 | void RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1558 | HInstruction* instruction, |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1559 | Location source, |
| 1560 | Location destination) const { |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1561 | DCHECK(IsValidDestination(destination)) << destination; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1562 | if (source.Equals(destination)) return; |
| 1563 | |
| 1564 | HInstruction* first = block->GetFirstInstruction(); |
| 1565 | HParallelMove* move = first->AsParallelMove(); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1566 | size_t position = block->GetLifetimeStart(); |
Nicolas Geoffray | e27f31a | 2014-06-12 17:53:14 +0100 | [diff] [blame] | 1567 | // This is a parallel move for connecting blocks. We need to differentiate |
| 1568 | // it with moves for connecting siblings in a same block, and input moves. |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1569 | if (move == nullptr || move->GetLifetimePosition() != position) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1570 | move = new (allocator_) HParallelMove(allocator_); |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1571 | move->SetLifetimePosition(position); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1572 | block->InsertInstructionBefore(move, first); |
| 1573 | } |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1574 | AddMove(move, source, destination, instruction, instruction->GetType()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1575 | } |
| 1576 | |
| 1577 | void RegisterAllocator::InsertMoveAfter(HInstruction* instruction, |
| 1578 | Location source, |
| 1579 | Location destination) const { |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1580 | DCHECK(IsValidDestination(destination)) << destination; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1581 | if (source.Equals(destination)) return; |
| 1582 | |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 1583 | if (instruction->IsPhi()) { |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1584 | InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1585 | return; |
| 1586 | } |
| 1587 | |
Nicolas Geoffray | e27f31a | 2014-06-12 17:53:14 +0100 | [diff] [blame] | 1588 | size_t position = instruction->GetLifetimePosition() + 1; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1589 | HParallelMove* move = instruction->GetNext()->AsParallelMove(); |
Nicolas Geoffray | e27f31a | 2014-06-12 17:53:14 +0100 | [diff] [blame] | 1590 | // This is a parallel move for moving the output of an instruction. We need |
| 1591 | // to differentiate with input moves, moves for connecting siblings in a |
| 1592 | // and moves for connecting blocks. |
| 1593 | if (move == nullptr || move->GetLifetimePosition() != position) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1594 | move = new (allocator_) HParallelMove(allocator_); |
Nicolas Geoffray | e27f31a | 2014-06-12 17:53:14 +0100 | [diff] [blame] | 1595 | move->SetLifetimePosition(position); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1596 | instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); |
| 1597 | } |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 1598 | AddMove(move, source, destination, instruction, instruction->GetType()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1599 | } |
| 1600 | |
| 1601 | void RegisterAllocator::ConnectSiblings(LiveInterval* interval) { |
| 1602 | LiveInterval* current = interval; |
Nicolas Geoffray | 76b1e17 | 2015-05-27 17:18:33 +0100 | [diff] [blame] | 1603 | if (current->HasSpillSlot() |
| 1604 | && current->HasRegister() |
| 1605 | // Currently, we spill unconditionnally the current method in the code generators. |
| 1606 | && !interval->GetDefinedBy()->IsCurrentMethod()) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1607 | // We spill eagerly, so move must be at definition. |
| 1608 | InsertMoveAfter(interval->GetDefinedBy(), |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1609 | interval->ToLocation(), |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1610 | interval->NeedsTwoSpillSlots() |
Nicolas Geoffray | 412f10c | 2014-06-19 10:00:34 +0100 | [diff] [blame] | 1611 | ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) |
| 1612 | : Location::StackSlot(interval->GetParent()->GetSpillSlot())); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1613 | } |
| 1614 | UsePosition* use = current->GetFirstUse(); |
Nicolas Geoffray | 4ed947a | 2015-04-27 16:58:06 +0100 | [diff] [blame] | 1615 | UsePosition* env_use = current->GetFirstEnvironmentUse(); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1616 | |
| 1617 | // Walk over all siblings, updating locations of use positions, and |
| 1618 | // connecting them when they are adjacent. |
| 1619 | do { |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1620 | Location source = current->ToLocation(); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1621 | |
| 1622 | // Walk over all uses covered by this interval, and update the location |
| 1623 | // information. |
Nicolas Geoffray | d8126be | 2015-03-27 10:22:41 +0000 | [diff] [blame] | 1624 | |
| 1625 | LiveRange* range = current->GetFirstRange(); |
| 1626 | while (range != nullptr) { |
Nicolas Geoffray | 5790260 | 2015-04-21 14:28:41 +0100 | [diff] [blame] | 1627 | while (use != nullptr && use->GetPosition() < range->GetStart()) { |
| 1628 | DCHECK(use->IsSynthesized()); |
| 1629 | use = use->GetNext(); |
| 1630 | } |
Nicolas Geoffray | d8126be | 2015-03-27 10:22:41 +0000 | [diff] [blame] | 1631 | while (use != nullptr && use->GetPosition() <= range->GetEnd()) { |
Nicolas Geoffray | 4ed947a | 2015-04-27 16:58:06 +0100 | [diff] [blame] | 1632 | DCHECK(!use->GetIsEnvironment()); |
David Brazdil | 3fc992f | 2015-04-16 18:31:55 +0100 | [diff] [blame] | 1633 | DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd())); |
Nicolas Geoffray | 5790260 | 2015-04-21 14:28:41 +0100 | [diff] [blame] | 1634 | if (!use->IsSynthesized()) { |
| 1635 | LocationSummary* locations = use->GetUser()->GetLocations(); |
| 1636 | Location expected_location = locations->InAt(use->GetInputIndex()); |
| 1637 | // The expected (actual) location may be invalid in case the input is unused. Currently |
| 1638 | // this only happens for intrinsics. |
| 1639 | if (expected_location.IsValid()) { |
| 1640 | if (expected_location.IsUnallocated()) { |
| 1641 | locations->SetInAt(use->GetInputIndex(), source); |
| 1642 | } else if (!expected_location.IsConstant()) { |
| 1643 | AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location); |
| 1644 | } |
| 1645 | } else { |
| 1646 | DCHECK(use->GetUser()->IsInvoke()); |
| 1647 | DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); |
Nicolas Geoffray | d8126be | 2015-03-27 10:22:41 +0000 | [diff] [blame] | 1648 | } |
| 1649 | } |
| 1650 | use = use->GetNext(); |
| 1651 | } |
Nicolas Geoffray | 4ed947a | 2015-04-27 16:58:06 +0100 | [diff] [blame] | 1652 | |
| 1653 | // Walk over the environment uses, and update their locations. |
| 1654 | while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) { |
| 1655 | env_use = env_use->GetNext(); |
| 1656 | } |
| 1657 | |
| 1658 | while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) { |
Nicolas Geoffray | 0a23d74 | 2015-05-07 11:57:35 +0100 | [diff] [blame] | 1659 | DCHECK(current->CoversSlow(env_use->GetPosition()) |
| 1660 | || (env_use->GetPosition() == range->GetEnd())); |
Nicolas Geoffray | d23eeef | 2015-05-18 22:31:29 +0100 | [diff] [blame] | 1661 | HEnvironment* environment = env_use->GetEnvironment(); |
Nicolas Geoffray | 0a23d74 | 2015-05-07 11:57:35 +0100 | [diff] [blame] | 1662 | environment->SetLocationAt(env_use->GetInputIndex(), source); |
Nicolas Geoffray | 4ed947a | 2015-04-27 16:58:06 +0100 | [diff] [blame] | 1663 | env_use = env_use->GetNext(); |
| 1664 | } |
| 1665 | |
Nicolas Geoffray | d8126be | 2015-03-27 10:22:41 +0000 | [diff] [blame] | 1666 | range = range->GetNext(); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1667 | } |
| 1668 | |
| 1669 | // If the next interval starts just after this one, and has a register, |
| 1670 | // insert a move. |
| 1671 | LiveInterval* next_sibling = current->GetNextSibling(); |
| 1672 | if (next_sibling != nullptr |
| 1673 | && next_sibling->HasRegister() |
| 1674 | && current->GetEnd() == next_sibling->GetStart()) { |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1675 | Location destination = next_sibling->ToLocation(); |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1676 | InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1677 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1678 | |
Nicolas Geoffray | 43af728 | 2015-04-16 13:01:01 +0100 | [diff] [blame] | 1679 | for (SafepointPosition* safepoint_position = current->GetFirstSafepoint(); |
| 1680 | safepoint_position != nullptr; |
| 1681 | safepoint_position = safepoint_position->GetNext()) { |
David Brazdil | 3fc992f | 2015-04-16 18:31:55 +0100 | [diff] [blame] | 1682 | DCHECK(current->CoversSlow(safepoint_position->GetPosition())); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1683 | |
Nicolas Geoffray | 5588e58 | 2015-04-14 14:10:59 +0100 | [diff] [blame] | 1684 | LocationSummary* locations = safepoint_position->GetLocations(); |
Nicolas Geoffray | 3bca0df | 2014-09-19 11:01:00 +0100 | [diff] [blame] | 1685 | if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { |
Nicolas Geoffray | 1af564e | 2016-01-13 12:09:39 +0000 | [diff] [blame] | 1686 | DCHECK(interval->GetDefinedBy()->IsActualObject()) |
| 1687 | << interval->GetDefinedBy()->DebugName() |
| 1688 | << "@" << safepoint_position->GetInstruction()->DebugName(); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1689 | locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); |
| 1690 | } |
| 1691 | |
| 1692 | switch (source.GetKind()) { |
| 1693 | case Location::kRegister: { |
Nicolas Geoffray | 3bca0df | 2014-09-19 11:01:00 +0100 | [diff] [blame] | 1694 | locations->AddLiveRegister(source); |
Nicolas Geoffray | 9889396 | 2015-01-21 12:32:32 +0000 | [diff] [blame] | 1695 | if (kIsDebugBuild && locations->OnlyCallsOnSlowPath()) { |
| 1696 | DCHECK_LE(locations->GetNumberOfLiveRegisters(), |
| 1697 | maximum_number_of_live_core_registers_ + |
| 1698 | maximum_number_of_live_fp_registers_); |
| 1699 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1700 | if (current->GetType() == Primitive::kPrimNot) { |
Nicolas Geoffray | a3eca2d | 2016-01-12 16:03:16 +0000 | [diff] [blame] | 1701 | DCHECK(interval->GetDefinedBy()->IsActualObject()) |
Nicolas Geoffray | 1af564e | 2016-01-13 12:09:39 +0000 | [diff] [blame] | 1702 | << interval->GetDefinedBy()->DebugName() |
| 1703 | << "@" << safepoint_position->GetInstruction()->DebugName(); |
Nicolas Geoffray | 56b9ee6 | 2014-10-09 11:47:51 +0100 | [diff] [blame] | 1704 | locations->SetRegisterBit(source.reg()); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1705 | } |
| 1706 | break; |
| 1707 | } |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 1708 | case Location::kFpuRegister: { |
| 1709 | locations->AddLiveRegister(source); |
| 1710 | break; |
| 1711 | } |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 1712 | |
| 1713 | case Location::kRegisterPair: |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1714 | case Location::kFpuRegisterPair: { |
| 1715 | locations->AddLiveRegister(source.ToLow()); |
| 1716 | locations->AddLiveRegister(source.ToHigh()); |
| 1717 | break; |
| 1718 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1719 | case Location::kStackSlot: // Fall-through |
| 1720 | case Location::kDoubleStackSlot: // Fall-through |
| 1721 | case Location::kConstant: { |
| 1722 | // Nothing to do. |
| 1723 | break; |
| 1724 | } |
| 1725 | default: { |
| 1726 | LOG(FATAL) << "Unexpected location for object"; |
| 1727 | } |
| 1728 | } |
| 1729 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1730 | current = next_sibling; |
| 1731 | } while (current != nullptr); |
Nicolas Geoffray | d8126be | 2015-03-27 10:22:41 +0000 | [diff] [blame] | 1732 | |
Nicolas Geoffray | 5790260 | 2015-04-21 14:28:41 +0100 | [diff] [blame] | 1733 | if (kIsDebugBuild) { |
| 1734 | // Following uses can only be synthesized uses. |
| 1735 | while (use != nullptr) { |
| 1736 | DCHECK(use->IsSynthesized()); |
| 1737 | use = use->GetNext(); |
| 1738 | } |
| 1739 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1740 | } |
| 1741 | |
Nicolas Geoffray | 04eb70f | 2016-01-21 18:22:23 +0000 | [diff] [blame] | 1742 | static bool IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop( |
| 1743 | HInstruction* instruction) { |
| 1744 | return instruction->GetBlock()->GetGraph()->HasIrreducibleLoops() && |
| 1745 | (instruction->IsConstant() || instruction->IsCurrentMethod()); |
| 1746 | } |
| 1747 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1748 | void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, |
| 1749 | HBasicBlock* from, |
| 1750 | HBasicBlock* to) const { |
| 1751 | if (interval->GetNextSibling() == nullptr) { |
| 1752 | // Nothing to connect. The whole range was allocated to the same location. |
| 1753 | return; |
| 1754 | } |
| 1755 | |
David Brazdil | 241a486 | 2015-04-16 17:59:03 +0100 | [diff] [blame] | 1756 | // Find the intervals that cover `from` and `to`. |
Nicolas Geoffray | ad4ed08 | 2016-01-27 14:15:23 +0000 | [diff] [blame] | 1757 | size_t destination_position = to->GetLifetimeStart(); |
| 1758 | size_t source_position = from->GetLifetimeEnd() - 1; |
| 1759 | LiveInterval* destination = interval->GetSiblingAt(destination_position); |
| 1760 | LiveInterval* source = interval->GetSiblingAt(source_position); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1761 | |
| 1762 | if (destination == source) { |
| 1763 | // Interval was not split. |
| 1764 | return; |
| 1765 | } |
Nicolas Geoffray | 04eb70f | 2016-01-21 18:22:23 +0000 | [diff] [blame] | 1766 | |
| 1767 | LiveInterval* parent = interval->GetParent(); |
| 1768 | HInstruction* defined_by = parent->GetDefinedBy(); |
Nicolas Geoffray | ad4ed08 | 2016-01-27 14:15:23 +0000 | [diff] [blame] | 1769 | if (codegen_->GetGraph()->HasIrreducibleLoops() && |
| 1770 | (destination == nullptr || !destination->CoversSlow(destination_position))) { |
Nicolas Geoffray | 04eb70f | 2016-01-21 18:22:23 +0000 | [diff] [blame] | 1771 | // Our live_in fixed point calculation has found that the instruction is live |
| 1772 | // in the `to` block because it will eventually enter an irreducible loop. Our |
| 1773 | // live interval computation however does not compute a fixed point, and |
| 1774 | // therefore will not have a location for that instruction for `to`. |
| 1775 | // Because the instruction is a constant or the ArtMethod, we don't need to |
| 1776 | // do anything: it will be materialized in the irreducible loop. |
Nicolas Geoffray | d7c2fdc | 2016-05-10 14:35:34 +0100 | [diff] [blame] | 1777 | DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by)) |
| 1778 | << defined_by->DebugName() << ":" << defined_by->GetId() |
| 1779 | << " " << from->GetBlockId() << " -> " << to->GetBlockId(); |
Nicolas Geoffray | 04eb70f | 2016-01-21 18:22:23 +0000 | [diff] [blame] | 1780 | return; |
| 1781 | } |
Nicolas Geoffray | 8ddb00c | 2014-09-29 12:00:40 +0100 | [diff] [blame] | 1782 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1783 | if (!destination->HasRegister()) { |
| 1784 | // Values are eagerly spilled. Spill slot already contains appropriate value. |
| 1785 | return; |
| 1786 | } |
| 1787 | |
Nicolas Geoffray | ad4ed08 | 2016-01-27 14:15:23 +0000 | [diff] [blame] | 1788 | Location location_source; |
| 1789 | // `GetSiblingAt` returns the interval whose start and end cover `position`, |
| 1790 | // but does not check whether the interval is inactive at that position. |
| 1791 | // The only situation where the interval is inactive at that position is in the |
| 1792 | // presence of irreducible loops for constants and ArtMethod. |
| 1793 | if (codegen_->GetGraph()->HasIrreducibleLoops() && |
| 1794 | (source == nullptr || !source->CoversSlow(source_position))) { |
| 1795 | DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by)); |
| 1796 | if (defined_by->IsConstant()) { |
| 1797 | location_source = defined_by->GetLocations()->Out(); |
| 1798 | } else { |
| 1799 | DCHECK(defined_by->IsCurrentMethod()); |
| 1800 | location_source = parent->NeedsTwoSpillSlots() |
| 1801 | ? Location::DoubleStackSlot(parent->GetSpillSlot()) |
| 1802 | : Location::StackSlot(parent->GetSpillSlot()); |
| 1803 | } |
| 1804 | } else { |
| 1805 | DCHECK(source != nullptr); |
| 1806 | DCHECK(source->CoversSlow(source_position)); |
| 1807 | DCHECK(destination->CoversSlow(destination_position)); |
| 1808 | location_source = source->ToLocation(); |
| 1809 | } |
| 1810 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1811 | // If `from` has only one successor, we can put the moves at the exit of it. Otherwise |
| 1812 | // we need to put the moves at the entry of `to`. |
David Brazdil | d26a411 | 2015-11-10 11:07:31 +0000 | [diff] [blame] | 1813 | if (from->GetNormalSuccessors().size() == 1) { |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1814 | InsertParallelMoveAtExitOf(from, |
Nicolas Geoffray | 04eb70f | 2016-01-21 18:22:23 +0000 | [diff] [blame] | 1815 | defined_by, |
Nicolas Geoffray | ad4ed08 | 2016-01-27 14:15:23 +0000 | [diff] [blame] | 1816 | location_source, |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1817 | destination->ToLocation()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1818 | } else { |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 1819 | DCHECK_EQ(to->GetPredecessors().size(), 1u); |
Nicolas Geoffray | 740475d | 2014-09-29 10:33:25 +0100 | [diff] [blame] | 1820 | InsertParallelMoveAtEntryOf(to, |
Nicolas Geoffray | 04eb70f | 2016-01-21 18:22:23 +0000 | [diff] [blame] | 1821 | defined_by, |
Nicolas Geoffray | ad4ed08 | 2016-01-27 14:15:23 +0000 | [diff] [blame] | 1822 | location_source, |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1823 | destination->ToLocation()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1824 | } |
| 1825 | } |
| 1826 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1827 | void RegisterAllocator::Resolve() { |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1828 | codegen_->InitializeCodeGeneration(GetNumberOfSpillSlots(), |
Nicolas Geoffray | 4c204ba | 2015-02-03 15:12:35 +0000 | [diff] [blame] | 1829 | maximum_number_of_live_core_registers_, |
| 1830 | maximum_number_of_live_fp_registers_, |
| 1831 | reserved_out_slots_, |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 1832 | codegen_->GetGraph()->GetLinearOrder()); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1833 | |
| 1834 | // Adjust the Out Location of instructions. |
| 1835 | // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. |
| 1836 | for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { |
| 1837 | HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); |
| 1838 | LiveInterval* current = instruction->GetLiveInterval(); |
| 1839 | LocationSummary* locations = instruction->GetLocations(); |
| 1840 | Location location = locations->Out(); |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 1841 | if (instruction->IsParameterValue()) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1842 | // Now that we know the frame size, adjust the parameter's location. |
| 1843 | if (location.IsStackSlot()) { |
| 1844 | location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); |
| 1845 | current->SetSpillSlot(location.GetStackIndex()); |
Nicolas Geoffray | f43083d | 2014-11-07 10:48:10 +0000 | [diff] [blame] | 1846 | locations->UpdateOut(location); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1847 | } else if (location.IsDoubleStackSlot()) { |
| 1848 | location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); |
| 1849 | current->SetSpillSlot(location.GetStackIndex()); |
Nicolas Geoffray | f43083d | 2014-11-07 10:48:10 +0000 | [diff] [blame] | 1850 | locations->UpdateOut(location); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1851 | } else if (current->HasSpillSlot()) { |
| 1852 | current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); |
| 1853 | } |
Nicolas Geoffray | 76b1e17 | 2015-05-27 17:18:33 +0100 | [diff] [blame] | 1854 | } else if (instruction->IsCurrentMethod()) { |
| 1855 | // The current method is always at offset 0. |
| 1856 | DCHECK(!current->HasSpillSlot() || (current->GetSpillSlot() == 0)); |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1857 | } else if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { |
| 1858 | DCHECK(current->HasSpillSlot()); |
| 1859 | size_t slot = current->GetSpillSlot() |
| 1860 | + GetNumberOfSpillSlots() |
| 1861 | + reserved_out_slots_ |
| 1862 | - catch_phi_spill_slots_; |
| 1863 | current->SetSpillSlot(slot * kVRegSize); |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1864 | } else if (current->HasSpillSlot()) { |
| 1865 | // Adjust the stack slot, now that we know the number of them for each type. |
| 1866 | // The way this implementation lays out the stack is the following: |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1867 | // [parameter slots ] |
| 1868 | // [catch phi spill slots ] |
| 1869 | // [double spill slots ] |
| 1870 | // [long spill slots ] |
| 1871 | // [float spill slots ] |
| 1872 | // [int/ref values ] |
| 1873 | // [maximum out values ] (number of arguments for calls) |
| 1874 | // [art method ]. |
| 1875 | size_t slot = current->GetSpillSlot(); |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1876 | switch (current->GetType()) { |
| 1877 | case Primitive::kPrimDouble: |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1878 | slot += long_spill_slots_.size(); |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1879 | FALLTHROUGH_INTENDED; |
| 1880 | case Primitive::kPrimLong: |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1881 | slot += float_spill_slots_.size(); |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1882 | FALLTHROUGH_INTENDED; |
| 1883 | case Primitive::kPrimFloat: |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1884 | slot += int_spill_slots_.size(); |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 1885 | FALLTHROUGH_INTENDED; |
| 1886 | case Primitive::kPrimNot: |
| 1887 | case Primitive::kPrimInt: |
| 1888 | case Primitive::kPrimChar: |
| 1889 | case Primitive::kPrimByte: |
| 1890 | case Primitive::kPrimBoolean: |
| 1891 | case Primitive::kPrimShort: |
| 1892 | slot += reserved_out_slots_; |
| 1893 | break; |
| 1894 | case Primitive::kPrimVoid: |
| 1895 | LOG(FATAL) << "Unexpected type for interval " << current->GetType(); |
| 1896 | } |
| 1897 | current->SetSpillSlot(slot * kVRegSize); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1898 | } |
| 1899 | |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1900 | Location source = current->ToLocation(); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1901 | |
| 1902 | if (location.IsUnallocated()) { |
| 1903 | if (location.GetPolicy() == Location::kSameAsFirstInput) { |
Calin Juravle | d0d4852 | 2014-11-04 16:40:20 +0000 | [diff] [blame] | 1904 | if (locations->InAt(0).IsUnallocated()) { |
| 1905 | locations->SetInAt(0, source); |
| 1906 | } else { |
| 1907 | DCHECK(locations->InAt(0).Equals(source)); |
| 1908 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1909 | } |
Nicolas Geoffray | 829280c | 2015-01-28 10:20:37 +0000 | [diff] [blame] | 1910 | locations->UpdateOut(source); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1911 | } else { |
| 1912 | DCHECK(source.Equals(location)); |
| 1913 | } |
| 1914 | } |
| 1915 | |
| 1916 | // Connect siblings. |
| 1917 | for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { |
| 1918 | HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); |
| 1919 | ConnectSiblings(instruction->GetLiveInterval()); |
| 1920 | } |
| 1921 | |
| 1922 | // Resolve non-linear control flow across branches. Order does not matter. |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 1923 | for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1924 | HBasicBlock* block = it.Current(); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 1925 | if (block->IsCatchBlock() || |
Nicolas Geoffray | ad4ed08 | 2016-01-27 14:15:23 +0000 | [diff] [blame] | 1926 | (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 1927 | // Instructions live at the top of catch blocks or irreducible loop header |
| 1928 | // were forced to spill. |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1929 | if (kIsDebugBuild) { |
| 1930 | BitVector* live = liveness_.GetLiveInSet(*block); |
| 1931 | for (uint32_t idx : live->Indexes()) { |
| 1932 | LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval(); |
Nicolas Geoffray | 974bbdd | 2016-03-22 15:12:07 +0000 | [diff] [blame] | 1933 | LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart()); |
| 1934 | // `GetSiblingAt` returns the sibling that contains a position, but there could be |
| 1935 | // a lifetime hole in it. `CoversSlow` returns whether the interval is live at that |
| 1936 | // position. |
Nicolas Geoffray | 32cc778 | 2016-03-23 11:32:27 +0000 | [diff] [blame] | 1937 | if ((sibling != nullptr) && sibling->CoversSlow(block->GetLifetimeStart())) { |
Nicolas Geoffray | 974bbdd | 2016-03-22 15:12:07 +0000 | [diff] [blame] | 1938 | DCHECK(!sibling->HasRegister()); |
| 1939 | } |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1940 | } |
| 1941 | } |
| 1942 | } else { |
| 1943 | BitVector* live = liveness_.GetLiveInSet(*block); |
| 1944 | for (uint32_t idx : live->Indexes()) { |
| 1945 | LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval(); |
| 1946 | for (HBasicBlock* predecessor : block->GetPredecessors()) { |
| 1947 | ConnectSplitSiblings(interval, predecessor, block); |
| 1948 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1949 | } |
| 1950 | } |
| 1951 | } |
| 1952 | |
| 1953 | // Resolve phi inputs. Order does not matter. |
Nicolas Geoffray | 0d9f17d | 2015-04-15 14:17:44 +0100 | [diff] [blame] | 1954 | for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1955 | HBasicBlock* current = it.Current(); |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1956 | if (current->IsCatchBlock()) { |
| 1957 | // Catch phi values are set at runtime by the exception delivery mechanism. |
| 1958 | } else { |
| 1959 | for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
| 1960 | HInstruction* phi = inst_it.Current(); |
| 1961 | for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) { |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 1962 | HBasicBlock* predecessor = current->GetPredecessors()[i]; |
David Brazdil | d26a411 | 2015-11-10 11:07:31 +0000 | [diff] [blame] | 1963 | DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u); |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 1964 | HInstruction* input = phi->InputAt(i); |
| 1965 | Location source = input->GetLiveInterval()->GetLocationAt( |
| 1966 | predecessor->GetLifetimeEnd() - 1); |
| 1967 | Location destination = phi->GetLiveInterval()->ToLocation(); |
| 1968 | InsertParallelMoveAtExitOf(predecessor, phi, source, destination); |
| 1969 | } |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 1970 | } |
| 1971 | } |
| 1972 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 1973 | |
| 1974 | // Assign temp locations. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 1975 | for (LiveInterval* temp : temp_intervals_) { |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1976 | if (temp->IsHighInterval()) { |
| 1977 | // High intervals can be skipped, they are already handled by the low interval. |
| 1978 | continue; |
| 1979 | } |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1980 | HInstruction* at = liveness_.GetTempUser(temp); |
Nicolas Geoffray | f01d344 | 2015-03-27 17:15:49 +0000 | [diff] [blame] | 1981 | size_t temp_index = liveness_.GetTempIndex(temp); |
Nicolas Geoffray | 01ef345 | 2014-10-01 11:32:17 +0100 | [diff] [blame] | 1982 | LocationSummary* locations = at->GetLocations(); |
Roland Levillain | 5368c21 | 2014-11-27 15:03:41 +0000 | [diff] [blame] | 1983 | switch (temp->GetType()) { |
| 1984 | case Primitive::kPrimInt: |
Nicolas Geoffray | f01d344 | 2015-03-27 17:15:49 +0000 | [diff] [blame] | 1985 | locations->SetTempAt(temp_index, Location::RegisterLocation(temp->GetRegister())); |
Roland Levillain | 5368c21 | 2014-11-27 15:03:41 +0000 | [diff] [blame] | 1986 | break; |
| 1987 | |
| 1988 | case Primitive::kPrimDouble: |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1989 | if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { |
| 1990 | Location location = Location::FpuRegisterPairLocation( |
| 1991 | temp->GetRegister(), temp->GetHighInterval()->GetRegister()); |
Nicolas Geoffray | f01d344 | 2015-03-27 17:15:49 +0000 | [diff] [blame] | 1992 | locations->SetTempAt(temp_index, location); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1993 | } else { |
Nicolas Geoffray | f01d344 | 2015-03-27 17:15:49 +0000 | [diff] [blame] | 1994 | locations->SetTempAt(temp_index, Location::FpuRegisterLocation(temp->GetRegister())); |
Nicolas Geoffray | 840e546 | 2015-01-07 16:01:24 +0000 | [diff] [blame] | 1995 | } |
Roland Levillain | 5368c21 | 2014-11-27 15:03:41 +0000 | [diff] [blame] | 1996 | break; |
| 1997 | |
| 1998 | default: |
| 1999 | LOG(FATAL) << "Unexpected type for temporary location " |
| 2000 | << temp->GetType(); |
| 2001 | } |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 2002 | } |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 2003 | } |
| 2004 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 2005 | } // namespace art |