Finally implement Location::kNoOutputOverlap.
The [i, i + 1) interval scheme we chose for representing
lifetime positions is not optimal for doing this optimization.
It however doesn't prevent recognizing a non-split interval
during the TryAllocateFreeReg phase, and try to re-use
its inputs' registers.
Change-Id: I80a2823b0048d3310becfc5f5fb7b1230dfd8201
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index b0d3853..0e68a61 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -18,6 +18,7 @@
#define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_
#include "nodes.h"
+#include <iostream>
namespace art {
@@ -181,12 +182,21 @@
void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) {
// Set the use within the instruction.
- size_t position = instruction->GetLifetimePosition();
- if (instruction->GetLocations()->InputOverlapsWithOutputOrTemp(input_index, is_environment)) {
- // If it overlaps, we need to make sure the user will not try to allocate a temp
- // or its output to the same register.
- ++position;
+ size_t position = instruction->GetLifetimePosition() + 1;
+ LocationSummary* locations = instruction->GetLocations();
+ if (!is_environment) {
+ if (locations->IsFixedInput(input_index) || locations->OutputUsesSameAs(input_index)) {
+ // For fixed inputs and output same as input, the register allocator
+ // requires to have inputs die at the instruction, so that input moves use the
+ // location of the input just before that instruction (and not potential moves due
+ // to splitting).
+ position = instruction->GetLifetimePosition();
+ }
}
+
+ DCHECK(position == instruction->GetLifetimePosition()
+ || position == instruction->GetLifetimePosition() + 1);
+
if ((first_use_ != nullptr)
&& (first_use_->GetUser() == instruction)
&& (first_use_->GetPosition() < position)) {
@@ -301,6 +311,7 @@
LiveInterval* GetParent() const { return parent_; }
LiveRange* GetFirstRange() const { return first_range_; }
+ LiveRange* GetLastRange() const { return last_range_; }
int GetRegister() const { return register_; }
void SetRegister(int reg) { register_ = reg; }
@@ -403,6 +414,23 @@
return FirstRegisterUseAfter(GetStart());
}
+ size_t FirstUseAfter(size_t position) const {
+ if (is_temp_) {
+ return position == GetStart() ? position : kNoLifetime;
+ }
+
+ UsePosition* use = first_use_;
+ size_t end = GetEnd();
+ while (use != nullptr && use->GetPosition() <= end) {
+ size_t use_position = use->GetPosition();
+ if (use_position > position) {
+ return use_position;
+ }
+ use = use->GetNext();
+ }
+ return kNoLifetime;
+ }
+
UsePosition* GetFirstUse() const {
return first_use_;
}
@@ -511,6 +539,13 @@
}
LiveInterval* GetNextSibling() const { return next_sibling_; }
+ LiveInterval* GetLastSibling() {
+ LiveInterval* result = this;
+ while (result->next_sibling_ != nullptr) {
+ result = result->next_sibling_;
+ }
+ return result;
+ }
// Returns the first register hint that is at least free before
// the value contained in `free_until`. If none is found, returns
@@ -541,6 +576,9 @@
// Returns whether `other` and `this` share the same kind of register.
bool SameRegisterKind(Location other) const;
+ bool SameRegisterKind(const LiveInterval& other) const {
+ return IsFloatingPoint() == other.IsFloatingPoint();
+ }
bool HasHighInterval() const {
return IsLowInterval();
@@ -594,6 +632,60 @@
}
}
+ // Returns whether an interval, when it is non-split, is using
+ // the same register of one of its input.
+ bool IsUsingInputRegister() const {
+ if (defined_by_ != nullptr && !IsSplit()) {
+ for (HInputIterator it(defined_by_); !it.Done(); it.Advance()) {
+ LiveInterval* interval = it.Current()->GetLiveInterval();
+
+ // Find the interval that covers `defined_by`_.
+ while (interval != nullptr && !interval->Covers(defined_by_->GetLifetimePosition())) {
+ interval = interval->GetNextSibling();
+ }
+
+ // Check if both intervals have the same register of the same kind.
+ if (interval != nullptr
+ && interval->SameRegisterKind(*this)
+ && interval->GetRegister() == GetRegister()) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ // Returns whether an interval, when it is non-split, can safely use
+ // the same register of one of its input. Note that this method requires
+ // IsUsingInputRegister() to be true.
+ bool CanUseInputRegister() const {
+ DCHECK(IsUsingInputRegister());
+ if (defined_by_ != nullptr && !IsSplit()) {
+ LocationSummary* locations = defined_by_->GetLocations();
+ if (locations->OutputCanOverlapWithInputs()) {
+ return false;
+ }
+ for (HInputIterator it(defined_by_); !it.Done(); it.Advance()) {
+ LiveInterval* interval = it.Current()->GetLiveInterval();
+
+ // Find the interval that covers `defined_by`_.
+ while (interval != nullptr && !interval->Covers(defined_by_->GetLifetimePosition())) {
+ interval = interval->GetNextSibling();
+ }
+
+ if (interval != nullptr
+ && interval->SameRegisterKind(*this)
+ && interval->GetRegister() == GetRegister()) {
+ // We found the input that has the same register. Check if it is live after
+ // `defined_by`_.
+ return !interval->Covers(defined_by_->GetLifetimePosition() + 1);
+ }
+ }
+ }
+ LOG(FATAL) << "Unreachable";
+ UNREACHABLE();
+ }
+
private:
LiveInterval(ArenaAllocator* allocator,
Primitive::Type type,