ART: Replace expensive calls to Covers in reg alloc
LiveInterval::Covers is implemented as a linear-time search over
liveness ranges and can therefore be rather expensive and should be
avoided unless necessary. This patch replaces calls to Covers when
searching for a sibling with the cheaper IsDefinedAt call.
Change-Id: I93fc73529c15a518335f4cbdc3a0def52d9501e5
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index a02b1da..830f2c2 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1538,35 +1538,14 @@
return;
}
- // Intervals end at the lifetime end of a block. The decrement by one
- // ensures the `Cover` call will return true.
- size_t from_position = from->GetLifetimeEnd() - 1;
- size_t to_position = to->GetLifetimeStart();
-
- LiveInterval* destination = nullptr;
- LiveInterval* source = nullptr;
-
- LiveInterval* current = interval;
-
- // Check the intervals that cover `from` and `to`.
- while ((current != nullptr) && (source == nullptr || destination == nullptr)) {
- if (current->Covers(from_position)) {
- DCHECK(source == nullptr);
- source = current;
- }
- if (current->Covers(to_position)) {
- DCHECK(destination == nullptr);
- destination = current;
- }
-
- current = current->GetNextSibling();
- }
+ // Find the intervals that cover `from` and `to`.
+ LiveInterval* destination = interval->GetSiblingAt(to->GetLifetimeStart());
+ LiveInterval* source = interval->GetSiblingAt(from->GetLifetimeEnd() - 1);
if (destination == source) {
// Interval was not split.
return;
}
-
DCHECK(destination != nullptr && source != nullptr);
if (!destination->HasRegister()) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 302df2a..ea0e7c3 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -402,11 +402,11 @@
for (size_t i = 0, e = defined_by_->InputCount(); i < e; ++i) {
HInstruction* input = defined_by_->InputAt(i);
size_t end = predecessors.Get(i)->GetLifetimeEnd();
- const LiveInterval& input_interval = input->GetLiveInterval()->GetIntervalAt(end - 1);
- if (input_interval.GetEnd() == end) {
+ LiveInterval* input_interval = input->GetLiveInterval()->GetSiblingAt(end - 1);
+ if (input_interval->GetEnd() == end) {
// If the input dies at the end of the predecessor, we know its register can
// be reused.
- Location input_location = input_interval.ToLocation();
+ Location input_location = input_interval->ToLocation();
if (input_location.IsRegisterKind()) {
DCHECK(SameRegisterKind(input_location));
return RegisterOrLowRegister(input_location);
@@ -418,12 +418,12 @@
Location out = locations->Out();
if (out.IsUnallocated() && out.GetPolicy() == Location::kSameAsFirstInput) {
// Try to use the same register as the first input.
- const LiveInterval& input_interval =
- GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetIntervalAt(GetStart() - 1);
- if (input_interval.GetEnd() == GetStart()) {
+ LiveInterval* input_interval =
+ GetDefinedBy()->InputAt(0)->GetLiveInterval()->GetSiblingAt(GetStart() - 1);
+ if (input_interval->GetEnd() == GetStart()) {
// If the input dies at the start of this instruction, we know its register can
// be reused.
- Location location = input_interval.ToLocation();
+ Location location = input_interval->ToLocation();
if (location.IsRegisterKind()) {
DCHECK(SameRegisterKind(location));
return RegisterOrLowRegister(location);
@@ -487,16 +487,17 @@
}
Location LiveInterval::GetLocationAt(size_t position) {
- return GetIntervalAt(position).ToLocation();
+ LiveInterval* sibling = GetSiblingAt(position);
+ DCHECK(sibling != nullptr);
+ return sibling->ToLocation();
}
-const LiveInterval& LiveInterval::GetIntervalAt(size_t position) {
+LiveInterval* LiveInterval::GetSiblingAt(size_t position) {
LiveInterval* current = this;
- while (!current->Covers(position)) {
+ while (current != nullptr && !current->IsDefinedAt(position)) {
current = current->GetNextSibling();
- DCHECK(current != nullptr);
}
- return *current;
+ return current;
}
} // namespace art
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 98f98a2..beb4907 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -372,7 +372,11 @@
bool HasRegister() const { return register_ != kNoRegister; }
bool IsDeadAt(size_t position) const {
- return last_range_->GetEnd() <= position;
+ return GetEnd() <= position;
+ }
+
+ bool IsDefinedAt(size_t position) const {
+ return GetStart() <= position && !IsDeadAt(position);
}
bool Covers(size_t position) {
@@ -513,7 +517,7 @@
DCHECK(!is_fixed_);
DCHECK_GT(position, GetStart());
- if (last_range_->GetEnd() <= position) {
+ if (GetEnd() <= position) {
// This range dies before `position`, no need to split.
return nullptr;
}
@@ -643,8 +647,8 @@
// Returns the location of the interval following its siblings at `position`.
Location GetLocationAt(size_t position);
- // Finds the interval that covers `position`.
- const LiveInterval& GetIntervalAt(size_t position);
+ // Finds the sibling that is defined at `position`.
+ LiveInterval* GetSiblingAt(size_t position);
// Returns whether `other` and `this` share the same kind of register.
bool SameRegisterKind(Location other) const;
