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
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index f8e00f6..0fdf051 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -378,7 +378,7 @@
// 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 @@
// 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 @@
}
}
+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 717be75..dc9c708 100644
--- a/compiler/optimizing/register_allocator.h
+++ b/compiler/optimizing/register_allocator.h
@@ -86,8 +86,12 @@
// 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 182cd0e..8c6d904 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -854,6 +854,10 @@
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 fe70d3a..97254ed 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -998,6 +998,15 @@
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 @@
GrowableArray<HInstruction*> instructions_from_lifetime_position_;
size_t number_of_ssa_values_;
+ ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive);
+
DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
};