Some improvement to reg alloc.
Change-Id: If579a37791278500a7e5bc763f144c241f261920
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 497e9b9..8adf7b9 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -141,6 +141,10 @@
for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) {
LiveInterval* fixed = physical_core_register_intervals_.Get(i);
if (fixed != nullptr) {
+ // Fixed interval is added to inactive_ instead of unhandled_.
+ // It's also the only type of inactive interval whose start position
+ // can be after the current interval during linear scan.
+ // Fixed interval is never split and never moves to unhandled_.
inactive_.Add(fixed);
}
}
@@ -160,6 +164,10 @@
for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) {
LiveInterval* fixed = physical_fp_register_intervals_.Get(i);
if (fixed != nullptr) {
+ // Fixed interval is added to inactive_ instead of unhandled_.
+ // It's also the only type of inactive interval whose start position
+ // can be after the current interval during linear scan.
+ // Fixed interval is never split and never moves to unhandled_.
inactive_.Add(fixed);
}
}
@@ -434,6 +442,27 @@
stream << std::endl;
}
+void RegisterAllocator::DumpAllIntervals(std::ostream& stream) const {
+ stream << "inactive: " << std::endl;
+ for (size_t i = 0; i < inactive_.Size(); i ++) {
+ DumpInterval(stream, inactive_.Get(i));
+ }
+ stream << "active: " << std::endl;
+ for (size_t i = 0; i < active_.Size(); i ++) {
+ DumpInterval(stream, active_.Get(i));
+ }
+ stream << "unhandled: " << std::endl;
+ auto unhandled = (unhandled_ != nullptr) ?
+ unhandled_ : &unhandled_core_intervals_;
+ for (size_t i = 0; i < unhandled->Size(); i ++) {
+ DumpInterval(stream, unhandled->Get(i));
+ }
+ stream << "handled: " << std::endl;
+ for (size_t i = 0; i < handled_.Size(); i ++) {
+ DumpInterval(stream, handled_.Get(i));
+ }
+}
+
// By the book implementation of a linear scan register allocator.
void RegisterAllocator::LinearScan() {
while (!unhandled_->IsEmpty()) {
@@ -443,6 +472,10 @@
DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart());
size_t position = current->GetStart();
+ // Remember the inactive_ size here since the ones moved to inactive_ from
+ // active_ below shouldn't need to be re-checked.
+ size_t inactive_intervals_to_handle = inactive_.Size();
+
// (2) Remove currently active intervals that are dead at this position.
// Move active intervals that have a lifetime hole at this position
// to inactive.
@@ -461,15 +494,18 @@
// (3) Remove currently inactive intervals that are dead at this position.
// Move inactive intervals that cover this position to active.
- for (size_t i = 0; i < inactive_.Size(); ++i) {
+ for (size_t i = 0; i < inactive_intervals_to_handle; ++i) {
LiveInterval* interval = inactive_.Get(i);
+ DCHECK(interval->GetStart() < position || interval->IsFixed());
if (interval->IsDeadAt(position)) {
inactive_.Delete(interval);
--i;
+ --inactive_intervals_to_handle;
handled_.Add(interval);
} else if (interval->Covers(position)) {
inactive_.Delete(interval);
--i;
+ --inactive_intervals_to_handle;
active_.Add(interval);
}
}
@@ -508,20 +544,6 @@
free_until[i] = kMaxLifetimePosition;
}
- // For each inactive interval, set its register to be free until
- // the next intersection with `current`.
- // Thanks to SSA, this should only be needed for intervals
- // that are the result of a split.
- for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
- LiveInterval* inactive = inactive_.Get(i);
- DCHECK(inactive->HasRegister());
- size_t next_intersection = inactive->FirstIntersectionWith(current);
- if (next_intersection != kNoLifetime) {
- free_until[inactive->GetRegister()] =
- std::min(free_until[inactive->GetRegister()], next_intersection);
- }
- }
-
// For each active interval, set its register to not free.
for (size_t i = 0, e = active_.Size(); i < e; ++i) {
LiveInterval* interval = active_.Get(i);
@@ -529,6 +551,33 @@
free_until[interval->GetRegister()] = 0;
}
+ // For each inactive interval, set its register to be free until
+ // the next intersection with `current`.
+ for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
+ LiveInterval* inactive = inactive_.Get(i);
+ // Temp/Slow-path-safepoint interval has no holes.
+ DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint());
+ if (!current->IsSplit() && !inactive->IsFixed()) {
+ // Neither current nor inactive are fixed.
+ // Thanks to SSA, a non-split interval starting in a hole of an
+ // inactive interval should never intersect with that inactive interval.
+ // Only if it's not fixed though, because fixed intervals don't come from SSA.
+ DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime);
+ continue;
+ }
+
+ DCHECK(inactive->HasRegister());
+ if (free_until[inactive->GetRegister()] == 0) {
+ // Already used by some active interval. No need to intersect.
+ continue;
+ }
+ size_t next_intersection = inactive->FirstIntersectionWith(current);
+ if (next_intersection != kNoLifetime) {
+ free_until[inactive->GetRegister()] =
+ std::min(free_until[inactive->GetRegister()], next_intersection);
+ }
+ }
+
int reg = -1;
if (current->HasRegister()) {
// Some instructions have a fixed register output.
@@ -607,10 +656,18 @@
// For each inactive interval, find the next use of its register after the
// start of current.
- // Thanks to SSA, this should only be needed for intervals
- // that are the result of a split.
for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
LiveInterval* inactive = inactive_.Get(i);
+ // Temp/Slow-path-safepoint interval has no holes.
+ DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint());
+ if (!current->IsSplit() && !inactive->IsFixed()) {
+ // Neither current nor inactive are fixed.
+ // Thanks to SSA, a non-split interval starting in a hole of an
+ // inactive interval should never intersect with that inactive interval.
+ // Only if it's not fixed though, because fixed intervals don't come from SSA.
+ DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime);
+ continue;
+ }
DCHECK(inactive->HasRegister());
size_t next_intersection = inactive->FirstIntersectionWith(current);
if (next_intersection != kNoLifetime) {
@@ -662,20 +719,29 @@
}
}
- for (size_t i = 0; i < inactive_.Size(); ++i) {
+ for (size_t i = 0, e = inactive_.Size(); i < e; ++i) {
LiveInterval* inactive = inactive_.Get(i);
if (inactive->GetRegister() == reg) {
+ if (!current->IsSplit() && !inactive->IsFixed()) {
+ // Neither current nor inactive are fixed.
+ // Thanks to SSA, a non-split interval starting in a hole of an
+ // inactive interval should never intersect with that inactive interval.
+ // Only if it's not fixed though, because fixed intervals don't come from SSA.
+ DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime);
+ continue;
+ }
size_t next_intersection = inactive->FirstIntersectionWith(current);
if (next_intersection != kNoLifetime) {
if (inactive->IsFixed()) {
LiveInterval* split = Split(current, next_intersection);
AddSorted(unhandled_, split);
} else {
- LiveInterval* split = Split(inactive, current->GetStart());
+ LiveInterval* split = Split(inactive, next_intersection);
inactive_.DeleteAt(i);
+ --i;
+ --e;
handled_.Add(inactive);
AddSorted(unhandled_, split);
- --i;
}
}
}
@@ -814,7 +880,7 @@
HInstruction* at = liveness_.GetInstructionFromPosition(position / 2);
if (at == nullptr) {
- // Block boundary, don't no anything the connection of split siblings will handle it.
+ // Block boundary, don't do anything the connection of split siblings will handle it.
return;
}
HParallelMove* move;
@@ -1025,7 +1091,7 @@
}
size_t from_position = from->GetLifetimeEnd() - 1;
- // When an instructions dies at entry of another, and the latter is the beginning
+ // When an instruction dies at entry of another, and the latter is the beginning
// of a block, the register allocator ensures the former has a register
// at block->GetLifetimeStart() + 1. Since this is at a block boundary, it must
// must be handled in this method.