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