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
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 @@
}
} 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 @@
}
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 @@
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 @@
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 @@
}
}
+ 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 @@
// 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 @@
}
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());