Find better split positions in the register allocator.

In a standard if/else control flow graph, this avoids doing a move in one branch if the other branch decided to move an interval. This also needs a new register hint kind, which is what was the location of the interval at the predecessor block. Change-Id: I18b78264587b4d693540fbb5e014d12df2add3e2
author: Nicolas Geoffray <ngeoffray@google.com> 2015-04-29 14:16:00 +0100
committer: Nicolas Geoffray <ngeoffray@google.com> 2015-05-05 10:24:17 +0100
commit: fbda5f3e1378f07ae202f62da625ee43a063a052 (patch)
tree: 4c6b9dbadbdf409a878da05bd3d765f9cb55653a
parent: 008b17ae313d033537a3792faf937134315f03bc (diff)
download: art-fbda5f3e1378f07ae202f62da625ee43a063a052.zip
art-fbda5f3e1378f07ae202f62da625ee43a063a052.tar.gz
art-fbda5f3e1378f07ae202f62da625ee43a063a052.tar.bz2
6 files changed, 210 insertions, 7 deletions
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 812642b..2375595 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 0bbcb30..1784168 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 b74e655..7b98c4e 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());
diff --git a/test/484-checker-register-hints/expected.txt b/test/484-checker-register-hints/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/484-checker-register-hints/expected.txt
diff --git a/test/484-checker-register-hints/info.txt b/test/484-checker-register-hints/info.txt
new file mode 100644
index 0000000..8923680
--- /dev/null
+++ b/test/484-checker-register-hints/info.txt
@@ -0,0 +1,4 @@
+Checks that the register allocator does not punish other
+blocks because one block forced spilling. The block that
+forces the spilling should restore the registers at the merge
+point.
diff --git a/test/484-checker-register-hints/src/Main.java b/test/484-checker-register-hints/src/Main.java
new file mode 100644
index 0000000..33952d9
--- /dev/null
+++ b/test/484-checker-register-hints/src/Main.java
@@ -0,0 +1,138 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+public class Main {
+
+  // CHECK-START: void Main.test1(boolean, int, int, int, int, int) register (after)
+  // CHECK:       name "B0"
+  // CHECK-NOT:     ParallelMove
+  // CHECK:       name "B1"
+  // CHECK-NOT:   end_block
+  // CHECK:         If
+  // CHECK-NOT:     ParallelMove
+  // CHECK:       name "B3"
+  // CHECK-NOT:   end_block
+  // CHECK:         ArraySet
+  // We could check here that there is a parallel move, but it's only valid
+  // for some architectures (for example x86), as other architectures may
+  // not do move at all.
+  // CHECK:       end_block
+  // CHECK-NOT:     ParallelMove
+
+  public static void test1(boolean z, int a, int b, int c, int d, int m) {
+    int e = live1;
+    int f = live2;
+    int g = live3;
+    if (z) {
+    } else {
+      // Create enough live instructions to force spilling on x86.
+      int h = live4;
+      int i = live5;
+      array[2] = e + i + h;
+      array[3] = f + i + h;
+      array[4] = g + i + h;
+      array[0] = h;
+      array[1] = i + h;
+
+    }
+    live1 = e + f + g;
+  }
+
+  // CHECK-START: void Main.test2(boolean, int, int, int, int, int) register (after)
+  // CHECK:       name "B0"
+  // CHECK-NOT:     ParallelMove
+  // CHECK:       name "B1"
+  // CHECK-NOT:   end_block
+  // CHECK:         If
+  // CHECK-NOT:     ParallelMove
+  // CHECK:       name "B3"
+  // CHECK-NOT:   end_block
+  // CHECK:         ArraySet
+  // We could check here that there is a parallel move, but it's only valid
+  // for some architectures (for example x86), as other architectures may
+  // not do move at all.
+  // CHECK:       end_block
+  // CHECK-NOT:     ParallelMove
+
+  public static void test2(boolean z, int a, int b, int c, int d, int m) {
+    int e = live1;
+    int f = live2;
+    int g = live3;
+    if (z) {
+      if (y) {
+        int h = live4;
+        int i = live5;
+        array[2] = e + i + h;
+        array[3] = f + i + h;
+        array[4] = g + i + h;
+        array[0] = h;
+        array[1] = i + h;
+      }
+    }
+    live1 = e + f + g;
+  }
+
+  // CHECK-START: void Main.test3(boolean, int, int, int, int, int) register (after)
+  // CHECK:       name "B0"
+  // CHECK-NOT:     ParallelMove
+  // CHECK:       name "B1"
+  // CHECK-NOT:   end_block
+  // CHECK:         If
+  // CHECK-NOT:     ParallelMove
+  // CHECK:       name "B6"
+  // CHECK-NOT:   end_block
+  // CHECK:         ArraySet
+  // We could check here that there is a parallel move, but it's only valid
+  // for some architectures (for example x86), as other architectures may
+  // not do move at all.
+  // CHECK:       end_block
+  // CHECK-NOT:     ParallelMove
+
+  public static void test3(boolean z, int a, int b, int c, int d, int m) {
+    // Same version as test2, but with branches reversed, to ensure
+    // whatever linear order is computed, we will get the same results.
+    int e = live1;
+    int f = live2;
+    int g = live3;
+    if (z) {
+      live1 = e;
+    } else {
+      if (y) {
+        live1 = e;
+      } else {
+        int h = live4;
+        int i = live5;
+        array[2] = e + i + h;
+        array[3] = f + i + h;
+        array[4] = g + i + h;
+        array[0] = h;
+        array[1] = i + h;
+      }
+    }
+    live1 = e + f + g;
+  }
+
+  public static void main(String[] args) {
+  }
+
+  static boolean y;
+  static int live1;
+  static int live2;
+  static int live3;
+  static int live4;
+  static int live5;
+  static int[] array;
+}
author	Nicolas Geoffray <ngeoffray@google.com>	2015-04-29 14:16:00 +0100
committer	Nicolas Geoffray <ngeoffray@google.com>	2015-05-05 10:24:17 +0100
commit	fbda5f3e1378f07ae202f62da625ee43a063a052 (patch)
tree	4c6b9dbadbdf409a878da05bd3d765f9cb55653a
parent	008b17ae313d033537a3792faf937134315f03bc (diff)
download	art-fbda5f3e1378f07ae202f62da625ee43a063a052.zip art-fbda5f3e1378f07ae202f62da625ee43a063a052.tar.gz art-fbda5f3e1378f07ae202f62da625ee43a063a052.tar.bz2