Add a linear scan register allocator to the optimizing compiler.
This is a "by-the-book" implementation. It currently only deals
with allocating registers, with no hint optimizations.
The changes remaining to make it functional are:
- Allocate spill slots.
- Resolution and placements of Move instructions.
- Connect it to the code generator.
Change-Id: Ie0b2f6ba1b98da85425be721ce4afecd6b4012a4
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 2d91436..4d56e1f 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -48,21 +48,68 @@
* A live range contains the start and end of a range where an instruction
* is live.
*/
-class LiveRange : public ValueObject {
+class LiveRange : public ArenaObject {
public:
- LiveRange(size_t start, size_t end) : start_(start), end_(end) {
+ LiveRange(size_t start, size_t end, LiveRange* next) : start_(start), end_(end), next_(next) {
DCHECK_LT(start, end);
+ DCHECK(next_ == nullptr || next_->GetStart() > GetEnd());
}
size_t GetStart() const { return start_; }
size_t GetEnd() const { return end_; }
+ LiveRange* GetNext() const { return next_; }
+
+ bool IntersectsWith(const LiveRange& other) {
+ return (start_ >= other.start_ && start_ < other.end_)
+ || (other.start_ >= start_ && other.start_ < end_);
+ }
+
+ bool IsBefore(const LiveRange& other) {
+ return end_ <= other.start_;
+ }
+
+ void Dump(std::ostream& stream) {
+ stream << "[" << start_ << ", " << end_ << ")";
+ }
private:
size_t start_;
size_t end_;
+ LiveRange* next_;
+
+ friend class LiveInterval;
+
+ DISALLOW_COPY_AND_ASSIGN(LiveRange);
};
-static constexpr int kDefaultNumberOfRanges = 3;
+/**
+ * A use position represents a live interval use at a given position.
+ */
+class UsePosition : public ArenaObject {
+ public:
+ UsePosition(HInstruction* user, size_t position, UsePosition* next)
+ : user_(user), position_(position), next_(next) {
+ DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition());
+ DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
+ }
+
+ size_t GetPosition() const { return position_; }
+
+ UsePosition* GetNext() const { return next_; }
+
+ HInstruction* GetUser() const { return user_; }
+
+ void Dump(std::ostream& stream) {
+ stream << position_;
+ }
+
+ private:
+ HInstruction* const user_;
+ const size_t position_;
+ UsePosition* const next_;
+
+ DISALLOW_COPY_AND_ASSIGN(UsePosition);
+};
/**
* An interval is a list of disjoint live ranges where an instruction is live.
@@ -70,67 +117,276 @@
*/
class LiveInterval : public ArenaObject {
public:
- explicit LiveInterval(ArenaAllocator* allocator) : ranges_(allocator, kDefaultNumberOfRanges) {}
+ LiveInterval(ArenaAllocator* allocator, Primitive::Type type)
+ : allocator_(allocator),
+ first_range_(nullptr),
+ last_range_(nullptr),
+ first_use_(nullptr),
+ type_(type),
+ next_sibling_(nullptr),
+ register_(kNoRegister) {}
void AddUse(HInstruction* instruction) {
size_t position = instruction->GetLifetimePosition();
size_t start_block_position = instruction->GetBlock()->GetLifetimeStart();
size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd();
- if (ranges_.IsEmpty()) {
+ if (first_range_ == nullptr) {
// First time we see a use of that interval.
- ranges_.Add(LiveRange(start_block_position, position));
- } else if (ranges_.Peek().GetStart() == start_block_position) {
+ first_range_ = last_range_ = new (allocator_) LiveRange(start_block_position, position, nullptr);
+ } else if (first_range_->GetStart() == start_block_position) {
// There is a use later in the same block.
- DCHECK_LE(position, ranges_.Peek().GetEnd());
- } else if (ranges_.Peek().GetStart() == end_block_position + 1) {
- // Last use is in a following block.
- LiveRange existing = ranges_.Pop();
- ranges_.Add(LiveRange(start_block_position, existing.GetEnd()));
+ DCHECK_LE(position, first_range_->GetEnd());
+ } else if (first_range_->GetStart() == end_block_position) {
+ // Last use is in the following block.
+ first_range_->start_ = start_block_position;
} else {
// There is a hole in the interval. Create a new range.
- ranges_.Add(LiveRange(start_block_position, position));
+ first_range_ = new (allocator_) LiveRange(start_block_position, position, first_range_);
}
+ first_use_ = new (allocator_) UsePosition(instruction, position, first_use_);
+ }
+
+ void AddPhiUse(HInstruction* instruction, HBasicBlock* block) {
+ DCHECK(instruction->AsPhi() != nullptr);
+ first_use_ = new (allocator_) UsePosition(instruction, block->GetLifetimeEnd(), first_use_);
}
void AddRange(size_t start, size_t end) {
- if (ranges_.IsEmpty()) {
- ranges_.Add(LiveRange(start, end));
- } else if (ranges_.Peek().GetStart() == end + 1) {
+ if (first_range_ == nullptr) {
+ first_range_ = last_range_ = new (allocator_) LiveRange(start, end, first_range_);
+ } else if (first_range_->GetStart() == end) {
// There is a use in the following block.
- LiveRange existing = ranges_.Pop();
- ranges_.Add(LiveRange(start, existing.GetEnd()));
+ first_range_->start_ = start;
} else {
// There is a hole in the interval. Create a new range.
- ranges_.Add(LiveRange(start, end));
+ first_range_ = new (allocator_) LiveRange(start, end, first_range_);
}
}
void AddLoopRange(size_t start, size_t end) {
- DCHECK(!ranges_.IsEmpty());
- while (!ranges_.IsEmpty() && ranges_.Peek().GetEnd() < end) {
- DCHECK_LE(start, ranges_.Peek().GetStart());
- ranges_.Pop();
+ DCHECK(first_range_ != nullptr);
+ while (first_range_ != nullptr && first_range_->GetEnd() < end) {
+ DCHECK_LE(start, first_range_->GetStart());
+ first_range_ = first_range_->GetNext();
}
- if (ranges_.IsEmpty()) {
+ if (first_range_ == nullptr) {
// Uses are only in the loop.
- ranges_.Add(LiveRange(start, end));
+ first_range_ = last_range_ = new (allocator_) LiveRange(start, end, nullptr);
} else {
// There are uses after the loop.
- LiveRange range = ranges_.Pop();
- ranges_.Add(LiveRange(start, range.GetEnd()));
+ first_range_->start_ = start;
}
}
void SetFrom(size_t from) {
- DCHECK(!ranges_.IsEmpty());
- LiveRange existing = ranges_.Pop();
- ranges_.Add(LiveRange(from, existing.GetEnd()));
+ DCHECK(first_range_ != nullptr);
+ first_range_->start_ = from;
}
- const GrowableArray<LiveRange>& GetRanges() const { return ranges_; }
+ LiveRange* GetFirstRange() const { return first_range_; }
+
+ int GetRegister() const { return register_; }
+ void SetRegister(int reg) { register_ = reg; }
+ void ClearRegister() { register_ = kNoRegister; }
+ bool HasRegister() const { return register_ != kNoRegister; }
+
+ bool IsDeadAt(size_t position) {
+ return last_range_->GetEnd() <= position;
+ }
+
+ bool Covers(size_t position) {
+ LiveRange* current = first_range_;
+ while (current != nullptr) {
+ if (position >= current->GetStart() && position < current->GetEnd()) {
+ return true;
+ }
+ current = current->GetNext();
+ }
+ return false;
+ }
+
+ /**
+ * Returns the first intersection of this interval with `other`.
+ */
+ size_t FirstIntersectionWith(LiveInterval* other) {
+ // We only call this method if there is a lifetime hole in this interval
+ // at the start of `other`.
+ DCHECK(!Covers(other->GetStart()));
+ DCHECK_LE(GetStart(), other->GetStart());
+ // Move to the range in this interval that starts after the other interval.
+ size_t other_start = other->GetStart();
+ LiveRange* my_range = first_range_;
+ while (my_range != nullptr) {
+ if (my_range->GetStart() >= other_start) {
+ break;
+ } else {
+ my_range = my_range->GetNext();
+ }
+ }
+ if (my_range == nullptr) {
+ return kNoLifetime;
+ }
+
+ // Advance both intervals and find the first matching range start in
+ // this interval.
+ LiveRange* other_range = other->first_range_;
+ do {
+ if (my_range->IntersectsWith(*other_range)) {
+ return std::max(my_range->GetStart(), other_range->GetStart());
+ } else if (my_range->IsBefore(*other_range)) {
+ my_range = my_range->GetNext();
+ if (my_range == nullptr) {
+ return kNoLifetime;
+ }
+ } else {
+ DCHECK(other_range->IsBefore(*my_range));
+ other_range = other_range->GetNext();
+ if (other_range == nullptr) {
+ return kNoLifetime;
+ }
+ }
+ } while (true);
+ }
+
+ size_t GetStart() const {
+ return first_range_->GetStart();
+ }
+
+ size_t FirstRegisterUseAfter(size_t position) const {
+ UsePosition* use = first_use_;
+ while (use != nullptr) {
+ size_t use_position = use->GetPosition();
+ // TODO: Once we plug the Locations builder of the code generator
+ // to the register allocator, this method must be adjusted. We
+ // test if there is an environment, because these are currently the only
+ // instructions that could have more uses than the number of registers.
+ if (use_position >= position && !use->GetUser()->NeedsEnvironment()) {
+ return use_position;
+ }
+ use = use->GetNext();
+ }
+ return kNoLifetime;
+ }
+
+ size_t FirstRegisterUse() const {
+ return FirstRegisterUseAfter(GetStart());
+ }
+
+ Primitive::Type GetType() const {
+ return type_;
+ }
+
+ /**
+ * Split this interval at `position`. This interval is changed to:
+ * [start ... position).
+ *
+ * The new interval covers:
+ * [position ... end)
+ */
+ LiveInterval* SplitAt(size_t position) {
+ DCHECK(next_sibling_ == nullptr);
+ DCHECK_GT(position, GetStart());
+
+ if (last_range_->GetEnd() <= position) {
+ // This range dies before `position`, no need to split.
+ return nullptr;
+ }
+
+ LiveInterval* new_interval = new (allocator_) LiveInterval(allocator_, type_);
+ next_sibling_ = new_interval;
+
+ new_interval->first_use_ = first_use_;
+ LiveRange* current = first_range_;
+ LiveRange* previous = nullptr;
+ // Iterate over the ranges, and either find a range that covers this position, or
+ // a two ranges in between this position (that is, the position is in a lifetime hole).
+ do {
+ if (position >= current->GetEnd()) {
+ // Move to next range.
+ previous = current;
+ current = current->next_;
+ } else if (position <= current->GetStart()) {
+ // If the previous range did not cover this position, we know position is in
+ // a lifetime hole. We can just break the first_range_ and last_range_ links
+ // and return the new interval.
+ DCHECK(previous != nullptr);
+ DCHECK(current != first_range_);
+ new_interval->last_range_ = last_range_;
+ last_range_ = previous;
+ previous->next_ = nullptr;
+ new_interval->first_range_ = current;
+ return new_interval;
+ } else {
+ // This range covers position. We create a new last_range_ for this interval
+ // that covers last_range_->Start() and position. We also shorten the current
+ // range and make it the first range of the new interval.
+ DCHECK(position < current->GetEnd() && position > current->GetStart());
+ new_interval->last_range_ = last_range_;
+ last_range_ = new (allocator_) LiveRange(current->start_, position, nullptr);
+ if (previous != nullptr) {
+ previous->next_ = last_range_;
+ } else {
+ first_range_ = last_range_;
+ }
+ new_interval->first_range_ = current;
+ current->start_ = position;
+ return new_interval;
+ }
+ } while (current != nullptr);
+
+ LOG(FATAL) << "Unreachable";
+ return nullptr;
+ }
+
+ bool StartsBefore(LiveInterval* other) const {
+ return GetStart() <= other->GetStart();
+ }
+
+ bool StartsAfter(LiveInterval* other) const {
+ return GetStart() >= other->GetStart();
+ }
+
+ void Dump(std::ostream& stream) const {
+ stream << "ranges: { ";
+ LiveRange* current = first_range_;
+ do {
+ current->Dump(stream);
+ stream << " ";
+ } while ((current = current->GetNext()) != nullptr);
+ stream << "}, uses: { ";
+ UsePosition* use = first_use_;
+ if (use != nullptr) {
+ do {
+ use->Dump(stream);
+ stream << " ";
+ } while ((use = use->GetNext()) != nullptr);
+ }
+ stream << "}";
+ }
+
+ LiveInterval* GetNextSibling() const { return next_sibling_; }
private:
- GrowableArray<LiveRange> ranges_;
+ ArenaAllocator* const allocator_;
+
+ // Ranges of this interval. We need a quick access to the last range to test
+ // for liveness (see `IsDeadAt`).
+ LiveRange* first_range_;
+ LiveRange* last_range_;
+
+ // Uses of this interval. Note that this linked list is shared amongst siblings.
+ UsePosition* first_use_;
+
+ // The instruction type this interval corresponds to.
+ const Primitive::Type type_;
+
+ // Live interval that is the result of a split.
+ LiveInterval* next_sibling_;
+
+ // The register allocated to this interval.
+ int register_;
+
+ static constexpr int kNoRegister = -1;
DISALLOW_COPY_AND_ASSIGN(LiveInterval);
};
@@ -164,10 +420,14 @@
return linear_post_order_;
}
- HInstruction* GetInstructionFromSsaIndex(size_t index) {
+ HInstruction* GetInstructionFromSsaIndex(size_t index) const {
return instructions_from_ssa_index_.Get(index);
}
+ size_t GetNumberOfSsaValues() const {
+ return number_of_ssa_values_;
+ }
+
private:
// Linearize the graph so that:
// (1): a block is always after its dominator,