ART: Optimize iteration of safepoints
The LiveInterval::Covers method is optimized for multiple calls with
non-decreasing positions. This patch reverts the order of iteration
over safepoints in RegisterAllocator::ConnectSiblings to capitalize
on this effect.
Change-Id: Ieb70eb9d5c0a06ee79379aab6c87cb3290c15bf7
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 54e62a5..0e9c4d6 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1381,6 +1381,7 @@
: Location::StackSlot(interval->GetParent()->GetSpillSlot()));
}
UsePosition* use = current->GetFirstUse();
+ size_t safepoint_index = safepoints_.Size();
// Walk over all siblings, updating locations of use positions, and
// connecting them when they are adjacent.
@@ -1422,19 +1423,27 @@
}
// At each safepoint, we record stack and register information.
- for (size_t i = 0, e = safepoints_.Size(); i < e; ++i) {
- HInstruction* safepoint = safepoints_.Get(i);
+ // We iterate backwards to test safepoints in ascending order of positions,
+ // which is what LiveInterval::Covers is optimized for.
+ while (safepoint_index > 0) {
+ HInstruction* safepoint = safepoints_.Get(--safepoint_index);
size_t position = safepoint->GetLifetimePosition();
- LocationSummary* locations = safepoint->GetLocations();
- if (!current->Covers(position)) {
+
+ // Test that safepoints are ordered in the optimal way.
+ DCHECK(safepoint_index == 0
+ || safepoints_.Get(safepoint_index - 1)->GetLifetimePosition() >= position);
+
+ if (current->IsDeadAt(position)) {
+ break;
+ } else if (!current->Covers(position)) {
continue;
- }
- if (interval->GetStart() == position) {
+ } else if (interval->GetStart() == position) {
// The safepoint is for this instruction, so the location of the instruction
// does not need to be saved.
continue;
}
+ LocationSummary* locations = safepoint->GetLocations();
if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) {
locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize);
}
