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/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