tree 80dbd414dd8ff4398fae817b64bc374b95896b7a
parent 2eb5168bd9e43b80452eaee5be32c063e124886e
author David Brazdil <dbrazdil@google.com> 1424881025 +0000
committer David Brazdil <dbrazdil@google.com> 1425313585 +0000

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