Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2016 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 | |
| 19 | #include <iostream> |
| 20 | #include <sstream> |
| 21 | |
| 22 | #include "base/bit_vector-inl.h" |
| 23 | #include "code_generator.h" |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 24 | #include "register_allocator_graph_color.h" |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 25 | #include "register_allocator_linear_scan.h" |
| 26 | #include "ssa_liveness_analysis.h" |
| 27 | |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 28 | namespace art { |
| 29 | |
| 30 | RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, |
| 31 | CodeGenerator* codegen, |
| 32 | const SsaLivenessAnalysis& liveness) |
| 33 | : allocator_(allocator), |
| 34 | codegen_(codegen), |
| 35 | liveness_(liveness) {} |
| 36 | |
| 37 | RegisterAllocator* RegisterAllocator::Create(ArenaAllocator* allocator, |
| 38 | CodeGenerator* codegen, |
| 39 | const SsaLivenessAnalysis& analysis, |
| 40 | Strategy strategy) { |
| 41 | switch (strategy) { |
| 42 | case kRegisterAllocatorLinearScan: |
| 43 | return new (allocator) RegisterAllocatorLinearScan(allocator, codegen, analysis); |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 44 | case kRegisterAllocatorGraphColor: |
| 45 | return new (allocator) RegisterAllocatorGraphColor(allocator, codegen, analysis); |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 46 | default: |
| 47 | LOG(FATAL) << "Invalid register allocation strategy: " << strategy; |
| 48 | UNREACHABLE(); |
| 49 | } |
| 50 | } |
| 51 | |
| 52 | bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph ATTRIBUTE_UNUSED, |
| 53 | InstructionSet instruction_set) { |
| 54 | return instruction_set == kArm |
| 55 | || instruction_set == kArm64 |
| 56 | || instruction_set == kMips |
| 57 | || instruction_set == kMips64 |
| 58 | || instruction_set == kThumb2 |
| 59 | || instruction_set == kX86 |
| 60 | || instruction_set == kX86_64; |
| 61 | } |
| 62 | |
| 63 | class AllRangesIterator : public ValueObject { |
| 64 | public: |
| 65 | explicit AllRangesIterator(LiveInterval* interval) |
| 66 | : current_interval_(interval), |
| 67 | current_range_(interval->GetFirstRange()) {} |
| 68 | |
| 69 | bool Done() const { return current_interval_ == nullptr; } |
| 70 | LiveRange* CurrentRange() const { return current_range_; } |
| 71 | LiveInterval* CurrentInterval() const { return current_interval_; } |
| 72 | |
| 73 | void Advance() { |
| 74 | current_range_ = current_range_->GetNext(); |
| 75 | if (current_range_ == nullptr) { |
| 76 | current_interval_ = current_interval_->GetNextSibling(); |
| 77 | if (current_interval_ != nullptr) { |
| 78 | current_range_ = current_interval_->GetFirstRange(); |
| 79 | } |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | private: |
| 84 | LiveInterval* current_interval_; |
| 85 | LiveRange* current_range_; |
| 86 | |
| 87 | DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); |
| 88 | }; |
| 89 | |
| 90 | bool RegisterAllocator::ValidateIntervals(const ArenaVector<LiveInterval*>& intervals, |
| 91 | size_t number_of_spill_slots, |
| 92 | size_t number_of_out_slots, |
| 93 | const CodeGenerator& codegen, |
| 94 | ArenaAllocator* allocator, |
| 95 | bool processing_core_registers, |
| 96 | bool log_fatal_on_failure) { |
| 97 | size_t number_of_registers = processing_core_registers |
| 98 | ? codegen.GetNumberOfCoreRegisters() |
| 99 | : codegen.GetNumberOfFloatingPointRegisters(); |
| 100 | ArenaVector<ArenaBitVector*> liveness_of_values( |
| 101 | allocator->Adapter(kArenaAllocRegisterAllocatorValidate)); |
| 102 | liveness_of_values.reserve(number_of_registers + number_of_spill_slots); |
| 103 | |
| 104 | size_t max_end = 0u; |
| 105 | for (LiveInterval* start_interval : intervals) { |
| 106 | for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { |
| 107 | max_end = std::max(max_end, it.CurrentRange()->GetEnd()); |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | // Allocate a bit vector per register. A live interval that has a register |
| 112 | // allocated will populate the associated bit vector based on its live ranges. |
| 113 | for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { |
| 114 | liveness_of_values.push_back( |
| 115 | ArenaBitVector::Create(allocator, max_end, false, kArenaAllocRegisterAllocatorValidate)); |
| 116 | } |
| 117 | |
| 118 | for (LiveInterval* start_interval : intervals) { |
| 119 | for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { |
| 120 | LiveInterval* current = it.CurrentInterval(); |
| 121 | HInstruction* defined_by = current->GetParent()->GetDefinedBy(); |
| 122 | if (current->GetParent()->HasSpillSlot() |
| 123 | // Parameters and current method have their own stack slot. |
| 124 | && !(defined_by != nullptr && (defined_by->IsParameterValue() |
| 125 | || defined_by->IsCurrentMethod()))) { |
| 126 | BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers |
| 127 | + current->GetParent()->GetSpillSlot() / kVRegSize |
| 128 | - number_of_out_slots]; |
| 129 | for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { |
| 130 | if (liveness_of_spill_slot->IsBitSet(j)) { |
| 131 | if (log_fatal_on_failure) { |
| 132 | std::ostringstream message; |
| 133 | message << "Spill slot conflict at " << j; |
| 134 | LOG(FATAL) << message.str(); |
| 135 | } else { |
| 136 | return false; |
| 137 | } |
| 138 | } else { |
| 139 | liveness_of_spill_slot->SetBit(j); |
| 140 | } |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | if (current->HasRegister()) { |
| 145 | if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) { |
| 146 | // Only check when an error is fatal. Only tests code ask for non-fatal failures |
| 147 | // and test code may not properly fill the right information to the code generator. |
| 148 | CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister())); |
| 149 | } |
| 150 | BitVector* liveness_of_register = liveness_of_values[current->GetRegister()]; |
| 151 | for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { |
| 152 | if (liveness_of_register->IsBitSet(j)) { |
| 153 | if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { |
| 154 | continue; |
| 155 | } |
| 156 | if (log_fatal_on_failure) { |
| 157 | std::ostringstream message; |
| 158 | message << "Register conflict at " << j << " "; |
| 159 | if (defined_by != nullptr) { |
| 160 | message << "(" << defined_by->DebugName() << ")"; |
| 161 | } |
| 162 | message << "for "; |
| 163 | if (processing_core_registers) { |
| 164 | codegen.DumpCoreRegister(message, current->GetRegister()); |
| 165 | } else { |
| 166 | codegen.DumpFloatingPointRegister(message, current->GetRegister()); |
| 167 | } |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 168 | for (LiveInterval* interval : intervals) { |
| 169 | if (interval->HasRegister() |
| 170 | && interval->GetRegister() == current->GetRegister() |
| 171 | && interval->CoversSlow(j)) { |
| 172 | message << std::endl; |
| 173 | if (interval->GetDefinedBy() != nullptr) { |
| 174 | message << interval->GetDefinedBy()->GetKind() << " "; |
| 175 | } else { |
| 176 | message << "physical "; |
| 177 | } |
| 178 | interval->Dump(message); |
| 179 | } |
| 180 | } |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 181 | LOG(FATAL) << message.str(); |
| 182 | } else { |
| 183 | return false; |
| 184 | } |
| 185 | } else { |
| 186 | liveness_of_register->SetBit(j); |
| 187 | } |
| 188 | } |
| 189 | } |
| 190 | } |
| 191 | } |
| 192 | return true; |
| 193 | } |
| 194 | |
| 195 | LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { |
| 196 | DCHECK_GE(position, interval->GetStart()); |
| 197 | DCHECK(!interval->IsDeadAt(position)); |
| 198 | if (position == interval->GetStart()) { |
| 199 | // Spill slot will be allocated when handling `interval` again. |
| 200 | interval->ClearRegister(); |
| 201 | if (interval->HasHighInterval()) { |
| 202 | interval->GetHighInterval()->ClearRegister(); |
| 203 | } else if (interval->HasLowInterval()) { |
| 204 | interval->GetLowInterval()->ClearRegister(); |
| 205 | } |
| 206 | return interval; |
| 207 | } else { |
| 208 | LiveInterval* new_interval = interval->SplitAt(position); |
| 209 | if (interval->HasHighInterval()) { |
| 210 | LiveInterval* high = interval->GetHighInterval()->SplitAt(position); |
| 211 | new_interval->SetHighInterval(high); |
| 212 | high->SetLowInterval(new_interval); |
| 213 | } else if (interval->HasLowInterval()) { |
| 214 | LiveInterval* low = interval->GetLowInterval()->SplitAt(position); |
| 215 | new_interval->SetLowInterval(low); |
| 216 | low->SetHighInterval(new_interval); |
| 217 | } |
| 218 | return new_interval; |
| 219 | } |
| 220 | } |
| 221 | |
| 222 | LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { |
| 223 | HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2); |
| 224 | HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2); |
| 225 | DCHECK(block_from != nullptr); |
| 226 | DCHECK(block_to != nullptr); |
| 227 | |
| 228 | // Both locations are in the same block. We split at the given location. |
| 229 | if (block_from == block_to) { |
| 230 | return Split(interval, to); |
| 231 | } |
| 232 | |
| 233 | /* |
| 234 | * Non-linear control flow will force moves at every branch instruction to the new location. |
| 235 | * To avoid having all branches doing the moves, we find the next non-linear position and |
| 236 | * split the interval at this position. Take the following example (block number is the linear |
| 237 | * order position): |
| 238 | * |
| 239 | * B1 |
| 240 | * / \ |
| 241 | * B2 B3 |
| 242 | * \ / |
| 243 | * B4 |
| 244 | * |
| 245 | * B2 needs to split an interval, whose next use is in B4. If we were to split at the |
| 246 | * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval |
| 247 | * is now in the correct location. It makes performance worst if the interval is spilled |
| 248 | * and both B2 and B3 need to reload it before entering B4. |
| 249 | * |
| 250 | * By splitting at B3, we give a chance to the register allocator to allocate the |
| 251 | * interval to the same register as in B1, and therefore avoid doing any |
| 252 | * moves in B3. |
| 253 | */ |
| 254 | if (block_from->GetDominator() != nullptr) { |
| 255 | for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) { |
| 256 | size_t position = dominated->GetLifetimeStart(); |
| 257 | if ((position > from) && (block_to->GetLifetimeStart() > position)) { |
| 258 | // Even if we found a better block, we continue iterating in case |
| 259 | // a dominated block is closer. |
| 260 | // Note that dominated blocks are not sorted in liveness order. |
| 261 | block_to = dominated; |
| 262 | DCHECK_NE(block_to, block_from); |
| 263 | } |
| 264 | } |
| 265 | } |
| 266 | |
| 267 | // If `to` is in a loop, find the outermost loop header which does not contain `from`. |
| 268 | for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { |
| 269 | HBasicBlock* header = it.Current()->GetHeader(); |
| 270 | if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { |
| 271 | break; |
| 272 | } |
| 273 | block_to = header; |
| 274 | } |
| 275 | |
| 276 | // Split at the start of the found block, to piggy back on existing moves |
| 277 | // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). |
| 278 | return Split(interval, block_to->GetLifetimeStart()); |
| 279 | } |
| 280 | |
| 281 | } // namespace art |