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
29namespace art {
30
31RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator,
32                                     CodeGenerator* codegen,
33                                     const SsaLivenessAnalysis& liveness)
34    : allocator_(allocator),
35      codegen_(codegen),
36      liveness_(liveness) {}
37
38RegisterAllocator* 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
53bool 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
64class 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
91bool 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
196LiveInterval* 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
223LiveInterval* 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