Register allocator: refine instructions liveness.
Add support for instructions that die at the beginning
of another instruction. Before, an instruction needed
to stay alive during the instruction, so the register
allocator was not able not reuse the register.
Change-Id: I5f11a80b0a20778227229eb797816edcc6365297
diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h
index a2f5bfa..f358e05 100644
--- a/compiler/optimizing/locations.h
+++ b/compiler/optimizing/locations.h
@@ -387,6 +387,16 @@
return &live_registers_;
}
+ bool InputOverlapsWithOutputOrTemp(uint32_t input, bool is_environment) const {
+ if (is_environment) return true;
+ Location location = Out();
+ // TODO: Add more policies.
+ if (input == 0 && location.IsUnallocated() && location.GetPolicy() == Location::kSameAsFirstInput) {
+ return false;
+ }
+ return true;
+ }
+
private:
GrowableArray<Location> inputs_;
GrowableArray<Location> temps_;
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 78f20a1..4b45f43 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -205,7 +205,7 @@
LiveInterval* current = instruction->GetLiveInterval();
if (current == nullptr) return;
- DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek()));
+ DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek()));
// Some instructions define their output in fixed register/stack slot. We need
// to ensure we know these locations before doing register allocation. For a
// given register, we create an interval that covers these locations. The register
@@ -228,7 +228,7 @@
// Split 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 = Split(current, first_register_use);
// Don't add direclty 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);
@@ -236,7 +236,7 @@
// Nothing to do, we won't allocate a register for this value.
}
} else {
- DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek()));
+ DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek()));
unhandled.Add(current);
}
}
@@ -586,7 +586,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 = Split(current, first_register_use);
AddSorted(unhandled_, split);
return false;
} else {
@@ -977,7 +977,11 @@
}
size_t from_position = from->GetLifetimeEnd() - 1;
- size_t to_position = to->GetLifetimeStart();
+ // When an instructions 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.
+ size_t to_position = to->GetLifetimeStart() + 1;
LiveInterval* destination = nullptr;
LiveInterval* source = nullptr;
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index dea6181..3ef2413 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -76,7 +76,7 @@
private:
size_t start_;
- const size_t end_;
+ size_t end_;
LiveRange* next_;
friend class LiveInterval;
@@ -99,13 +99,16 @@
is_environment_(is_environment),
position_(position),
next_(next) {
- DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition() + 1);
+ DCHECK(user->IsPhi()
+ || (GetPosition() == user->GetLifetimePosition() + 1)
+ || (GetPosition() == user->GetLifetimePosition()));
DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
}
size_t GetPosition() const { return position_; }
UsePosition* GetNext() const { return next_; }
+ void SetNext(UsePosition* next) { next_ = next; }
HInstruction* GetUser() const { return user_; }
@@ -122,7 +125,7 @@
const size_t input_index_;
const bool is_environment_;
const size_t position_;
- UsePosition* const next_;
+ UsePosition* next_;
DISALLOW_COPY_AND_ASSIGN(UsePosition);
};
@@ -174,11 +177,29 @@
void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) {
// Set the use within the instruction.
- // TODO: Use the instruction's location to know whether the instruction can die
- // at entry, or needs to say alive within the user.
- size_t position = instruction->GetLifetimePosition() + 1;
+ size_t position = instruction->GetLifetimePosition();
+ if (instruction->GetLocations()->InputOverlapsWithOutputOrTemp(input_index, is_environment)) {
+ // If it overlaps, we need to make sure the user will not try to allocate a temp
+ // or its output to the same register.
+ ++position;
+ }
size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
+ if ((first_use_ != nullptr)
+ && (first_use_->GetUser() == instruction)
+ && (first_use_->GetPosition() < position)) {
+ // The user uses the instruction multiple times, and one use dies before the other.
+ // We update the use list so that the latter is first.
+ DCHECK(first_use_->GetPosition() + 1 == position);
+ UsePosition* new_use = new (allocator_) UsePosition(
+ instruction, input_index, is_environment, position, first_use_->GetNext());
+ first_use_->SetNext(new_use);
+ if (first_range_->GetEnd() == first_use_->GetPosition()) {
+ first_range_->end_ = position;
+ }
+ return;
+ }
+
if (first_range_ == nullptr) {
// First time we see a use of that interval.
first_range_ = last_range_ = new (allocator_) LiveRange(start_block_position, position, nullptr);
@@ -198,7 +219,7 @@
}
void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) {
- DCHECK(instruction->AsPhi() != nullptr);
+ DCHECK(instruction->IsPhi());
first_use_ = new (allocator_) UsePosition(
instruction, input_index, false, block->GetLifetimeEnd(), first_use_);
}
@@ -339,7 +360,9 @@
if (use_position >= position && !use->GetIsEnvironment()) {
Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
if (location.IsUnallocated() && location.GetPolicy() == Location::kRequiresRegister) {
- return use_position;
+ // Return the lifetime just before the user, so that the interval has a register
+ // when entering the user.
+ return use->GetUser()->GetLifetimePosition() - 1;
}
}
use = use->GetNext();
@@ -428,12 +451,12 @@
return nullptr;
}
- bool StartsBefore(LiveInterval* other) const {
+ bool StartsBeforeOrAt(LiveInterval* other) const {
return GetStart() <= other->GetStart();
}
bool StartsAfter(LiveInterval* other) const {
- return GetStart() >= other->GetStart();
+ return GetStart() > other->GetStart();
}
void Dump(std::ostream& stream) const {