Merge "Find better split positions in the register allocator."

3 files changed, 68 insertions, 7 deletions

diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 812642b1b2..2375595978 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -768,7 +768,7 @@ bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
     }
   } else {
     DCHECK(!current->IsHighInterval());
-    int hint = current->FindFirstRegisterHint(free_until);
+    int hint = current->FindFirstRegisterHint(free_until, liveness_);
     if (hint != kNoRegister) {
       DCHECK(!IsBlocked(hint));
       reg = hint;
@@ -1101,8 +1101,8 @@ 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);
+  HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2);
+  HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2);
   DCHECK(block_from != nullptr);
   DCHECK(block_to != nullptr);
 
@@ -1111,6 +1111,41 @@ LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t fro
     return Split(interval, to);
   }
 
+  /*
+   * Non-linear control flow will force moves at every branch instruction to the new location.
+   * To avoid having all branches doing the moves, we find the next non-linear position and
+   * split the interval at this position. Take the following example (block number is the linear
+   * order position):
+   *
+   *     B1
+   *    /  \
+   *   B2  B3
+   *    \  /
+   *     B4
+   *
+   * B2 needs to split an interval, whose next use is in B4. If we were to split at the
+   * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval
+   * is now in the correct location. It makes performance worst if the interval is spilled
+   * and both B2 and B3 need to reload it before entering B4.
+   *
+   * By splitting at B3, we give a chance to the register allocator to allocate the
+   * interval to the same register as in B1, and therefore avoid doing any
+   * moves in B3.
+   */
+  if (block_from->GetDominator() != nullptr) {
+    const GrowableArray<HBasicBlock*>& dominated = block_from->GetDominator()->GetDominatedBlocks();
+    for (size_t i = 0; i < dominated.Size(); ++i) {
+      size_t position = dominated.Get(i)->GetLifetimeStart();
+      if ((position > from) && (block_to->GetLifetimeStart() > position)) {
+        // Even if we found a better block, we continue iterating in case
+        // a dominated block is closer.
+        // Note that dominated blocks are not sorted in liveness order.
+        block_to = dominated.Get(i);
+        DCHECK_NE(block_to, block_from);
+      }
+    }
+  }
+
   // 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();
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 0bbcb308f3..17841685b1 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -322,7 +322,8 @@ static int RegisterOrLowRegister(Location location) {
   return location.IsPair() ? location.low() : location.reg();
 }
 
-int LiveInterval::FindFirstRegisterHint(size_t* free_until) const {
+int LiveInterval::FindFirstRegisterHint(size_t* free_until,
+                                        const SsaLivenessAnalysis& liveness) const {
   DCHECK(!IsHighInterval());
   if (IsTemp()) return kNoRegister;
 
@@ -336,6 +337,26 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until) const {
     }
   }
 
+  if (IsSplit() && liveness.IsAtBlockBoundary(GetStart() / 2)) {
+    // If the start of this interval is at a block boundary, we look at the
+    // location of the interval in blocks preceding the block this interval
+    // starts at. If one location is a register we return it as a hint. This
+    // will avoid a move between the two blocks.
+    HBasicBlock* block = liveness.GetBlockFromPosition(GetStart() / 2);
+    for (size_t i = 0; i < block->GetPredecessors().Size(); ++i) {
+      size_t position = block->GetPredecessors().Get(i)->GetLifetimeEnd() - 1;
+      // We know positions above GetStart() do not have a location yet.
+      if (position < GetStart()) {
+        LiveInterval* existing = GetParent()->GetSiblingAt(position);
+        if (existing != nullptr
+            && existing->HasRegister()
+            && (free_until[existing->GetRegister()] > GetStart())) {
+          return existing->GetRegister();
+        }
+      }
+    }
+  }
+
   UsePosition* use = first_use_;
   size_t start = GetStart();
   size_t end = GetEnd();
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index b74e65584f..7b98c4eab5 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -23,6 +23,7 @@
 namespace art {
 
 class CodeGenerator;
+class SsaLivenessAnalysis;
 
 static constexpr int kNoRegister = -1;
 
@@ -690,7 +691,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> {
   // Returns the first register hint that is at least free before
   // the value contained in `free_until`. If none is found, returns
   // `kNoRegister`.
-  int FindFirstRegisterHint(size_t* free_until) const;
+  int FindFirstRegisterHint(size_t* free_until, const SsaLivenessAnalysis& liveness) const;
 
   // If there is enough at the definition site to find a register (for example
   // it uses the same input as the first input), returns the register as a hint.
@@ -1116,14 +1117,18 @@ class SsaLivenessAnalysis : public ValueObject {
   }
 
   HBasicBlock* GetBlockFromPosition(size_t index) const {
-    HInstruction* instruction = GetInstructionFromPosition(index / 2);
+    HInstruction* instruction = GetInstructionFromPosition(index);
     if (instruction == nullptr) {
       // If we are at a block boundary, get the block following.
-      instruction = GetInstructionFromPosition((index / 2) + 1);
+      instruction = GetInstructionFromPosition(index + 1);
     }
     return instruction->GetBlock();
   }
 
+  bool IsAtBlockBoundary(size_t index) const {
+    return GetInstructionFromPosition(index) == nullptr;
+  }
+
   HInstruction* GetTempUser(LiveInterval* temp) const {
     // A temporary shares the same lifetime start as the instruction that requires it.
     DCHECK(temp->IsTemp());