Linear scan: split at better positions.

- Split at block entry to piggy back on control flow resolution.
- Split at the loop header, if the split position is within a loop.

Change-Id: I718299a58c02ee02a1b22bda589607c69a35f0e8

4 files changed, 48 insertions, 4 deletions

diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index f8e00f6873..0fdf051957 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -378,7 +378,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
     // Split just before first register use.
     size_t first_register_use = current->FirstRegisterUse();
     if (first_register_use != kNoLifetime) {
-      LiveInterval* split = Split(current, first_register_use - 1);
+      LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1);
       // Don't add directly to `unhandled`, it needs to be sorted and the start
       // of this new interval might be after intervals already in the list.
       AddSorted(&unhandled, split);
@@ -997,7 +997,7 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
       // 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.
       AllocateSpillSlotFor(current);
-      LiveInterval* split = Split(current, first_register_use - 1);
+      LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1);
       if (current == split) {
         DumpInterval(std::cerr, current);
         DumpAllIntervals(std::cerr);
@@ -1100,6 +1100,31 @@ void RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInter
   }
 }
 
+LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) {
+  HBasicBlock* block_from = liveness_.GetBlockFromPosition(from);
+  HBasicBlock* block_to = liveness_.GetBlockFromPosition(to);
+  DCHECK(block_from != nullptr);
+  DCHECK(block_to != nullptr);
+
+  // Both locations are in the same block. We split at the given location.
+  if (block_from == block_to) {
+    return Split(interval, to);
+  }
+
+  // If `to` is in a loop, find the outermost loop header which does not contain `from`.
+  for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) {
+    HBasicBlock* header = it.Current()->GetHeader();
+    if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) {
+      break;
+    }
+    block_to = header;
+  }
+
+  // Split at the start of the found block, to piggy back on existing moves
+  // due to resolution if non-linear control flow (see `ConnectSplitSiblings`).
+  return Split(interval, block_to->GetLifetimeStart());
+}
+
 LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) {
   DCHECK_GE(position, interval->GetStart());
   DCHECK(!interval->IsDeadAt(position));
diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h
index 717be75533..dc9c708eea 100644
--- a/compiler/optimizing/register_allocator.h
+++ b/compiler/optimizing/register_allocator.h
@@ -86,8 +86,12 @@ class RegisterAllocator {
   // Add `interval` in the given sorted list.
   static void AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval);
 
-  // Split `interval` at the position `at`. The new interval starts at `at`.
-  LiveInterval* Split(LiveInterval* interval, size_t at);
+  // Split `interval` at the position `position`. The new interval starts at `position`.
+  LiveInterval* Split(LiveInterval* interval, size_t position);
+
+  // Split `interval` at a position between `from` and `to`. The method will try
+  // to find an optimal split position.
+  LiveInterval* SplitBetween(LiveInterval* interval, size_t from, size_t to);
 
   // Returns whether `reg` is blocked by the code generator.
   bool IsBlocked(int reg) const;
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 182cd0e833..8c6d904a4c 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -854,6 +854,10 @@ TEST(RegisterAllocatorTest, SpillInactive) {
       X86InstructionSetFeatures::FromCppDefines());
   x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
   SsaLivenessAnalysis liveness(graph, &codegen);
+  // Populate the instructions in the liveness object, to please the register allocator.
+  for (size_t i = 0; i < 32; ++i) {
+    liveness.instructions_from_lifetime_position_.Add(user);
+  }
 
   RegisterAllocator register_allocator(&allocator, &codegen, liveness);
   register_allocator.unhandled_core_intervals_.Add(fourth);
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index fe70d3a861..97254edb5e 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -998,6 +998,15 @@ class SsaLivenessAnalysis : public ValueObject {
     return instructions_from_lifetime_position_.Get(index);
   }
 
+  HBasicBlock* GetBlockFromPosition(size_t index) const {
+    HInstruction* instruction = GetInstructionFromPosition(index / 2);
+    if (instruction == nullptr) {
+      // If we are at a block boundary, get the block following.
+      instruction = GetInstructionFromPosition((index / 2) + 1);
+    }
+    return instruction->GetBlock();
+  }
+
   HInstruction* GetTempUser(LiveInterval* temp) const {
     // A temporary shares the same lifetime start as the instruction that requires it.
     DCHECK(temp->IsTemp());
@@ -1068,6 +1077,8 @@ class SsaLivenessAnalysis : public ValueObject {
   GrowableArray<HInstruction*> instructions_from_lifetime_position_;
   size_t number_of_ssa_values_;
 
+  ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive);
+
   DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
 };