Refactor safepoints in register allocator.
This is in preparation for adding logic around callee/caller
saved in the register allocator.
Change-Id: I4204169f0a6a01074880538833144be7b0810882
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 4bca434..8f26328 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -224,7 +224,7 @@
temp_intervals_.Add(interval);
interval->AddTempUse(instruction, i);
if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) {
- interval->AddHighInterval(true);
+ interval->AddHighInterval(/* is_temp */ true);
LiveInterval* high = interval->GetHighInterval();
temp_intervals_.Add(high);
unhandled_fp_intervals_.Add(high);
@@ -310,6 +310,29 @@
current->AddHighInterval();
}
+ for (size_t safepoint_index = safepoints_.Size(); safepoint_index > 0; --safepoint_index) {
+ HInstruction* safepoint = safepoints_.Get(safepoint_index - 1);
+ size_t safepoint_position = safepoint->GetLifetimePosition();
+
+ // Test that safepoints are ordered in the optimal way.
+ DCHECK(safepoint_index == safepoints_.Size()
+ || safepoints_.Get(safepoint_index)->GetLifetimePosition() < safepoint_position);
+
+ if (safepoint_position == current->GetStart()) {
+ // The safepoint is for this instruction, so the location of the instruction
+ // does not need to be saved.
+ DCHECK_EQ(safepoint_index, safepoints_.Size());
+ DCHECK_EQ(safepoint, instruction);
+ continue;
+ } else if (current->IsDeadAt(safepoint_position)) {
+ break;
+ } else if (!current->Covers(safepoint_position)) {
+ // Hole in the interval.
+ continue;
+ }
+ current->AddSafepoint(safepoint);
+ }
+
// Some instructions define their output in fixed register/stack slot. We need
// to ensure we know these locations before doing register allocation. For a
// given register, we create an interval that covers these locations. The register
@@ -1399,7 +1422,7 @@
: Location::StackSlot(interval->GetParent()->GetSpillSlot()));
}
UsePosition* use = current->GetFirstUse();
- size_t safepoint_index = safepoints_.Size();
+ SafepointPosition* safepoint_position = interval->GetFirstSafepoint();
// Walk over all siblings, updating locations of use positions, and
// connecting them when they are adjacent.
@@ -1450,28 +1473,13 @@
InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination);
}
- // At each safepoint, we record stack and register information.
- // We iterate backwards to test safepoints in ascending order of positions,
- // which is what LiveInterval::Covers is optimized for.
- for (; safepoint_index > 0; --safepoint_index) {
- HInstruction* safepoint = safepoints_.Get(safepoint_index - 1);
- size_t position = safepoint->GetLifetimePosition();
-
- // Test that safepoints are ordered in the optimal way.
- DCHECK(safepoint_index == safepoints_.Size()
- || safepoints_.Get(safepoint_index)->GetLifetimePosition() <= position);
-
- if (current->IsDeadAt(position)) {
+ for (; safepoint_position != nullptr; safepoint_position = safepoint_position->GetNext()) {
+ if (!current->Covers(safepoint_position->GetPosition())) {
+ DCHECK(next_sibling != nullptr);
break;
- } else if (!current->Covers(position)) {
- continue;
- } 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();
+ LocationSummary* locations = safepoint_position->GetLocations();
if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) {
locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize);
}
@@ -1515,6 +1523,7 @@
} while (current != nullptr);
if (kIsDebugBuild) {
+ DCHECK(safepoint_position == nullptr);
// Following uses can only be environment uses. The location for
// these environments will be none.
while (use != nullptr) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index d2da84c..b6e4028 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -149,6 +149,39 @@
DISALLOW_COPY_AND_ASSIGN(UsePosition);
};
+class SafepointPosition : public ArenaObject<kArenaAllocMisc> {
+ public:
+ explicit SafepointPosition(HInstruction* instruction)
+ : instruction_(instruction),
+ next_(nullptr) {}
+
+ void SetNext(SafepointPosition* next) {
+ next_ = next;
+ }
+
+ size_t GetPosition() const {
+ return instruction_->GetLifetimePosition();
+ }
+
+ SafepointPosition* GetNext() const {
+ return next_;
+ }
+
+ LocationSummary* GetLocations() const {
+ return instruction_->GetLocations();
+ }
+
+ HInstruction* GetInstruction() const {
+ return instruction_;
+ }
+
+ private:
+ HInstruction* const instruction_;
+ SafepointPosition* next_;
+
+ DISALLOW_COPY_AND_ASSIGN(SafepointPosition);
+};
+
/**
* An interval is a list of disjoint live ranges where an instruction is live.
* Each instruction that has uses gets an interval.
@@ -703,6 +736,22 @@
UNREACHABLE();
}
+ void AddSafepoint(HInstruction* instruction) {
+ SafepointPosition* safepoint = new (allocator_) SafepointPosition(instruction);
+ if (first_safepoint_ == nullptr) {
+ first_safepoint_ = last_safepoint_ = safepoint;
+ } else {
+ DCHECK_LT(last_safepoint_->GetPosition(), safepoint->GetPosition());
+ last_safepoint_->SetNext(safepoint);
+ last_safepoint_ = safepoint;
+ }
+ }
+
+ SafepointPosition* GetFirstSafepoint() const {
+ DCHECK_EQ(GetParent(), this) << "Only the first sibling lists safepoints";
+ return first_safepoint_;
+ }
+
private:
LiveInterval(ArenaAllocator* allocator,
Primitive::Type type,
@@ -715,6 +764,8 @@
: allocator_(allocator),
first_range_(nullptr),
last_range_(nullptr),
+ first_safepoint_(nullptr),
+ last_safepoint_(nullptr),
last_visited_range_(nullptr),
first_use_(nullptr),
type_(type),
@@ -771,6 +822,10 @@
LiveRange* first_range_;
LiveRange* last_range_;
+ // Safepoints where this interval is live. Only set in the parent interval.
+ SafepointPosition* first_safepoint_;
+ SafepointPosition* last_safepoint_;
+
// Last visited range. This is a range search optimization leveraging the fact
// that the register allocator does a linear scan through the intervals.
LiveRange* last_visited_range_;