ART: Cache last returned range in LiveInterval::Covers
Optimizing spends ~10% of compilation time in the register allocator.
One of the frequently called methods is LiveInterval::Covers which
has linear complexity w.r.t. the number of gaps in liveness intervals.
This patch leverages the fact that the register allocator calls Covers
with non-decreasing position values and caches the last returned
result to start the iteration closer to the result the next time the
method is invoked. Stats from compiling the framework show that this
optimization reduces the average number of iterations needed to find
the result by 40%.
Change-Id: I4dd26b900879d5e1d03818ebc1e117cc6a53053c
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index bebb73b..d009390 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -477,12 +477,12 @@
}
}
-Location LiveInterval::GetLocationAt(size_t position) const {
+Location LiveInterval::GetLocationAt(size_t position) {
return GetIntervalAt(position).ToLocation();
}
-const LiveInterval& LiveInterval::GetIntervalAt(size_t position) const {
- const LiveInterval* current = this;
+const LiveInterval& LiveInterval::GetIntervalAt(size_t position) {
+ LiveInterval* current = this;
while (!current->Covers(position)) {
current = current->GetNextSibling();
DCHECK(current != nullptr);