Add a linear scan register allocator to the optimizing compiler.

This is a "by-the-book" implementation. It currently only deals
with allocating registers, with no hint optimizations.

The changes remaining to make it functional are:
- Allocate spill slots.
- Resolution and placements of Move instructions.
- Connect it to the code generator.

Change-Id: Ie0b2f6ba1b98da85425be721ce4afecd6b4012a4

1 files changed, 378 insertions, 0 deletions

diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
new file mode 100644
index 0000000..dd175d2
--- /dev/null
+++ b/compiler/optimizing/register_allocator.cc
@@ -0,0 +1,378 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "register_allocator.h"
+
+#include "code_generator.h"
+#include "ssa_liveness_analysis.h"
+
+namespace art {
+
+static constexpr size_t kMaxLifetimePosition = -1;
+
+RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen)
+      : allocator_(allocator),
+        codegen_(codegen),
+        unhandled_(allocator, 0),
+        handled_(allocator, 0),
+        active_(allocator, 0),
+        inactive_(allocator, 0),
+        processing_core_registers_(false),
+        number_of_registers_(-1),
+        registers_array_(nullptr),
+        blocked_registers_(allocator->AllocArray<bool>(codegen.GetNumberOfRegisters())) {
+  codegen.SetupBlockedRegisters(blocked_registers_);
+}
+
+static bool ShouldProcess(bool processing_core_registers, HInstruction* instruction) {
+  bool is_core_register = (instruction->GetType() != Primitive::kPrimDouble)
+      && (instruction->GetType() != Primitive::kPrimFloat);
+  return processing_core_registers == is_core_register;
+}
+
+void RegisterAllocator::AllocateRegistersInternal(const SsaLivenessAnalysis& liveness) {
+  number_of_registers_ = processing_core_registers_
+      ? codegen_.GetNumberOfCoreRegisters()
+      : codegen_.GetNumberOfFloatingPointRegisters();
+
+  registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_);
+
+  // Iterate post-order, to ensure the list is sorted, and the last added interval
+  // is the one with the lowest start position.
+  for (size_t i = liveness.GetNumberOfSsaValues(); i > 0; --i) {
+    HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i - 1);
+    if (ShouldProcess(processing_core_registers_, instruction)) {
+      LiveInterval* current = instruction->GetLiveInterval();
+      DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek()));
+      unhandled_.Add(current);
+    }
+  }
+
+  LinearScan();
+  if (kIsDebugBuild) {
+    ValidateInternal(liveness, true);
+  }
+}
+
+bool RegisterAllocator::ValidateInternal(const SsaLivenessAnalysis& liveness,
+                                         bool log_fatal_on_failure) const {
+  // To simplify unit testing, we eagerly create the array of intervals, and
+  // call the helper method.
+  GrowableArray<LiveInterval*> intervals(allocator_, 0);
+  for (size_t i = 0; i < liveness.GetNumberOfSsaValues(); ++i) {
+    HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i);
+    if (ShouldProcess(processing_core_registers_, instruction)) {
+      intervals.Add(instruction->GetLiveInterval());
+    }
+  }
+  return ValidateIntervals(intervals, codegen_, allocator_, processing_core_registers_,
+                           log_fatal_on_failure);
+}
+
+bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ranges,
+                                          const CodeGenerator& codegen,
+                                          ArenaAllocator* allocator,
+                                          bool processing_core_registers,
+                                          bool log_fatal_on_failure) {
+  size_t number_of_registers = processing_core_registers
+      ? codegen.GetNumberOfCoreRegisters()
+      : codegen.GetNumberOfFloatingPointRegisters();
+  GrowableArray<ArenaBitVector*> bit_vectors(allocator, number_of_registers);
+
+  // Allocate a bit vector per register. A live interval that has a register
+  // allocated will populate the associated bit vector based on its live ranges.
+  for (size_t i = 0; i < number_of_registers; i++) {
+    bit_vectors.Add(new (allocator) ArenaBitVector(allocator, 0, true));
+  }
+
+  for (size_t i = 0, e = ranges.Size(); i < e; ++i) {
+    LiveInterval* current = ranges.Get(i);
+    do {
+      if (!current->HasRegister()) {
+        continue;
+      }
+      BitVector* vector = bit_vectors.Get(current->GetRegister());
+      LiveRange* range = current->GetFirstRange();
+      do {
+        for (size_t j = range->GetStart(); j < range->GetEnd(); ++j) {
+          if (vector->IsBitSet(j)) {
+            if (log_fatal_on_failure) {
+              std::ostringstream message;
+              message << "Register conflict at " << j << " for ";
+              if (processing_core_registers) {
+                codegen.DumpCoreRegister(message, current->GetRegister());
+              } else {
+                codegen.DumpFloatingPointRegister(message, current->GetRegister());
+              }
+              LOG(FATAL) << message.str();
+            } else {
+              return false;
+            }
+          } else {
+            vector->SetBit(j);
+          }
+        }
+      } while ((range = range->GetNext()) != nullptr);
+    } while ((current = current->GetNextSibling()) != nullptr);
+  }
+  return true;
+}
+
+void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) {
+  interval->Dump(stream);
+  stream << ": ";
+  if (interval->HasRegister()) {
+    if (processing_core_registers_) {
+      codegen_.DumpCoreRegister(stream, interval->GetRegister());
+    } else {
+      codegen_.DumpFloatingPointRegister(stream, interval->GetRegister());
+    }
+  } else {
+    stream << "spilled";
+  }
+  stream << std::endl;
+}
+
+// By the book implementation of a linear scan register allocator.
+void RegisterAllocator::LinearScan() {
+  while (!unhandled_.IsEmpty()) {
+    // (1) Remove interval with the lowest start position from unhandled.
+    LiveInterval* current = unhandled_.Pop();
+    size_t position = current->GetStart();
+
+    // (2) Remove currently active intervals that are dead at this position.
+    //     Move active intervals that have a lifetime hole at this position
+    //     to inactive.
+    for (size_t i = 0; i < active_.Size(); ++i) {
+      LiveInterval* interval = active_.Get(i);
+      if (interval->IsDeadAt(position)) {
+        active_.Delete(interval);
+        --i;
+        handled_.Add(interval);
+      } else if (!interval->Covers(position)) {
+        active_.Delete(interval);
+        --i;
+        inactive_.Add(interval);
+      }
+    }
+
+    // (3) Remove currently inactive intervals that are dead at this position.
+    //     Move inactive intervals that cover this position to active.
+    for (size_t i = 0; i < inactive_.Size(); ++i) {
+      LiveInterval* interval = inactive_.Get(i);
+      if (interval->IsDeadAt(position)) {
+        inactive_.Delete(interval);
+        --i;
+        handled_.Add(interval);
+      } else if (interval->Covers(position)) {
+        inactive_.Delete(interval);
+        --i;
+        active_.Add(interval);
+      }
+    }
+
+    // (4) Try to find an available register.
+    bool success = TryAllocateFreeReg(current);
+
+    // (5) If no register could be found, we need to spill.
+    if (!success) {
+      success = AllocateBlockedReg(current);
+    }
+
+    // (6) If the interval had a register allocated, add it to the list of active
+    //     intervals.
+    if (success) {
+      active_.Add(current);
+    }
+  }
+}
+
+// Find a free register. If multiple are found, pick the register that
+// is free the longest.
+bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
+  size_t* free_until = registers_array_;
+
+  // First set all registers to be free.
+  for (size_t i = 0; i < number_of_registers_; ++i) {
+    free_until[i] = kMaxLifetimePosition;
+  }
+
+  // For each active interval, set its register to not free.
+  for (size_t i = 0, e = active_.Size(); i < e; ++i) {
+    LiveInterval* interval = active_.Get(i);
+    DCHECK(interval->HasRegister());
+    free_until[interval->GetRegister()] = 0;
+  }
+
+  // For each inactive interval, set its register to be free until
+  // the next intersection with `current`.
+  // Thanks to SSA, this should only be needed for intervals
+  // that are the result of a split.
+  for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
+    LiveInterval* inactive = inactive_.Get(i);
+    DCHECK(inactive->HasRegister());
+    size_t next_intersection = inactive->FirstIntersectionWith(current);
+    if (next_intersection != kNoLifetime) {
+      free_until[inactive->GetRegister()] = next_intersection;
+    }
+  }
+
+  // Pick the register that is free the longest.
+  int reg = -1;
+  for (size_t i = 0; i < number_of_registers_; ++i) {
+    if (IsBlocked(i)) continue;
+    if (reg == -1 || free_until[i] > free_until[reg]) {
+      reg = i;
+      if (free_until[i] == kMaxLifetimePosition) break;
+    }
+  }
+
+  // If we could not find a register, we need to spill.
+  if (reg == -1 || free_until[reg] == 0) {
+    return false;
+  }
+
+  current->SetRegister(reg);
+  if (!current->IsDeadAt(free_until[reg])) {
+    // If the register is only available for a subset of live ranges
+    // covered by `current`, split `current` at the position where
+    // the register is not available anymore.
+    LiveInterval* split = Split(current, free_until[reg]);
+    DCHECK(split != nullptr);
+    AddToUnhandled(split);
+  }
+  return true;
+}
+
+bool RegisterAllocator::IsBlocked(int reg) const {
+  // TODO: This only works for core registers and needs to be adjusted for
+  // floating point registers.
+  DCHECK(processing_core_registers_);
+  return blocked_registers_[reg];
+}
+
+// Find the register that is used the last, and spill the interval
+// that holds it. If the first use of `current` is after that register
+// we spill `current` instead.
+bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
+  size_t first_register_use = current->FirstRegisterUse();
+  if (current->FirstRegisterUse() == kNoLifetime) {
+    // TODO: Allocate spill slot for `current`.
+    return false;
+  }
+
+  // First set all registers as not being used.
+  size_t* next_use = registers_array_;
+  for (size_t i = 0; i < number_of_registers_; ++i) {
+    next_use[i] = kMaxLifetimePosition;
+  }
+
+  // For each active interval, find the next use of its register after the
+  // start of current.
+  for (size_t i = 0, e = active_.Size(); i < e; ++i) {
+    LiveInterval* active = active_.Get(i);
+    DCHECK(active->HasRegister());
+    size_t use = active->FirstRegisterUseAfter(current->GetStart());
+    if (use != kNoLifetime) {
+      next_use[active->GetRegister()] = use;
+    }
+  }
+
+  // For each inactive interval, find the next use of its register after the
+  // start of current.
+  // Thanks to SSA, this should only be needed for intervals
+  // that are the result of a split.
+  for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
+    LiveInterval* inactive = inactive_.Get(i);
+    DCHECK(inactive->HasRegister());
+    size_t use = inactive->FirstRegisterUseAfter(current->GetStart());
+    if (use != kNoLifetime) {
+      next_use[inactive->GetRegister()] = use;
+    }
+  }
+
+  // Pick the register that is used the last.
+  int reg = -1;
+  for (size_t i = 0; i < number_of_registers_; ++i) {
+    if (IsBlocked(i)) continue;
+    if (reg == -1 || next_use[i] > next_use[reg]) {
+      reg = i;
+      if (next_use[i] == kMaxLifetimePosition) break;
+    }
+  }
+
+  if (first_register_use >= next_use[reg]) {
+    // If the first use of that instruction is after the last use of the found
+    // register, we split this interval just before its first register use.
+    LiveInterval* split = Split(current, first_register_use - 1);
+    AddToUnhandled(split);
+    return false;
+  } else {
+    // Use this register and spill the active and inactives interval that
+    // have that register.
+    current->SetRegister(reg);
+
+    for (size_t i = 0, e = active_.Size(); i < e; ++i) {
+      LiveInterval* active = active_.Get(i);
+      if (active->GetRegister() == reg) {
+        LiveInterval* split = Split(active, current->GetStart());
+        active_.DeleteAt(i);
+        handled_.Add(active);
+        AddToUnhandled(split);
+        break;
+      }
+    }
+
+    for (size_t i = 0; i < inactive_.Size(); ++i) {
+      LiveInterval* inactive = inactive_.Get(i);
+      if (inactive->GetRegister() == reg) {
+        LiveInterval* split = Split(inactive, current->GetStart());
+        inactive_.DeleteAt(i);
+        handled_.Add(inactive);
+        AddToUnhandled(split);
+        --i;
+      }
+    }
+
+    return true;
+  }
+}
+
+void RegisterAllocator::AddToUnhandled(LiveInterval* interval) {
+  for (size_t i = unhandled_.Size(); i > 0; --i) {
+    LiveInterval* current = unhandled_.Get(i - 1);
+    if (current->StartsAfter(interval)) {
+      unhandled_.InsertAt(i, interval);
+      break;
+    }
+  }
+}
+
+LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) {
+  DCHECK(position >= interval->GetStart());
+  DCHECK(!interval->IsDeadAt(position));
+  if (position == interval->GetStart()) {
+    // Spill slot will be allocated when handling `interval` again.
+    interval->ClearRegister();
+    return interval;
+  } else {
+    LiveInterval* new_interval = interval->SplitAt(position);
+    // TODO: Allocate spill slot for `interval`.
+    return new_interval;
+  }
+}
+
+}  // namespace art