Linear scan: Use FirstUse instead of FirstRegisterUse.
This is in preparation for introducing synthesized used at back edges.
Change-Id: Ie28d6725d2dde982cf2137f2110daabcbab9f789
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 649038b..44931c6 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -2162,7 +2162,7 @@
uint32_t GetDexMethodIndex() const { return dex_method_index_; }
- Intrinsics GetIntrinsic() {
+ Intrinsics GetIntrinsic() const {
return intrinsic_;
}
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index 830f2c2..e11ca65 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -901,6 +901,10 @@
return false;
}
+ // We use the first use to compare with other intervals. If this interval
+ // is used after any active intervals, we will spill this interval.
+ size_t first_use = current->FirstUseAfter(current->GetStart());
+
// First set all registers as not being used.
size_t* next_use = registers_array_;
for (size_t i = 0; i < number_of_registers_; ++i) {
@@ -915,7 +919,7 @@
if (active->IsFixed()) {
next_use[active->GetRegister()] = current->GetStart();
} else {
- size_t use = active->FirstRegisterUseAfter(current->GetStart());
+ size_t use = active->FirstUseAfter(current->GetStart());
if (use != kNoLifetime) {
next_use[active->GetRegister()] = use;
}
@@ -943,7 +947,7 @@
next_use[inactive->GetRegister()] =
std::min(next_intersection, next_use[inactive->GetRegister()]);
} else {
- size_t use = inactive->FirstRegisterUseAfter(current->GetStart());
+ size_t use = inactive->FirstUseAfter(current->GetStart());
if (use != kNoLifetime) {
next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]);
}
@@ -957,16 +961,16 @@
DCHECK(current->IsHighInterval());
reg = current->GetRegister();
// When allocating the low part, we made sure the high register was available.
- DCHECK_LT(first_register_use, next_use[reg]);
+ DCHECK_LT(first_use, next_use[reg]);
} else if (current->IsLowInterval()) {
reg = FindAvailableRegisterPair(next_use, first_register_use);
// We should spill if both registers are not available.
- should_spill = (first_register_use >= next_use[reg])
- || (first_register_use >= next_use[GetHighForLowRegister(reg)]);
+ should_spill = (first_use >= next_use[reg])
+ || (first_use >= next_use[GetHighForLowRegister(reg)]);
} else {
DCHECK(!current->IsHighInterval());
reg = FindAvailableRegister(next_use);
- should_spill = (first_register_use >= next_use[reg]);
+ should_spill = (first_use >= next_use[reg]);
}
DCHECK_NE(reg, kNoRegister);
@@ -996,10 +1000,12 @@
DumpInterval(std::cerr, current);
DumpAllIntervals(std::cerr);
// This situation has the potential to infinite loop, so we make it a non-debug CHECK.
+ HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2);
CHECK(false) << "There is not enough registers available for "
<< split->GetParent()->GetDefinedBy()->DebugName() << " "
<< split->GetParent()->GetDefinedBy()->GetId()
- << " at " << first_register_use - 1;
+ << " at " << first_register_use - 1 << " "
+ << (at == nullptr ? "" : at->DebugName());
}
AddSorted(unhandled_, split);
}
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index beb4907..e3a4d81 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -131,6 +131,9 @@
void Dump(std::ostream& stream) const {
stream << position_;
+ if (is_environment_) {
+ stream << " (env)";
+ }
}
UsePosition* Dup(ArenaAllocator* allocator) const {
@@ -363,6 +366,10 @@
LiveInterval* GetParent() const { return parent_; }
+ // Returns whether this interval is the parent interval, that is, the interval
+ // that starts where the HInstruction is defined.
+ bool IsParent() const { return parent_ == this; }
+
LiveRange* GetFirstRange() const { return first_range_; }
LiveRange* GetLastRange() const { return last_range_; }
@@ -421,7 +428,7 @@
if (is_temp_) {
return position == GetStart() ? position : kNoLifetime;
}
- if (position == GetStart() && defined_by_ != nullptr) {
+ if (position == GetStart() && IsParent()) {
LocationSummary* locations = defined_by_->GetLocations();
Location location = locations->Out();
// This interval is the first interval of the instruction. If the output
@@ -470,12 +477,19 @@
return position == GetStart() ? position : kNoLifetime;
}
+ if (position == GetStart() && IsParent()) {
+ if (defined_by_->GetLocations()->Out().IsValid()) {
+ return position;
+ }
+ }
+
UsePosition* use = first_use_;
size_t end = GetEnd();
while (use != nullptr && use->GetPosition() <= end) {
if (!use->GetIsEnvironment()) {
+ Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
size_t use_position = use->GetPosition();
- if (use_position > position) {
+ if (use_position > position && location.IsValid()) {
return use_position;
}
}
@@ -693,7 +707,7 @@
}
void AddHighInterval(bool is_temp = false) {
- DCHECK_EQ(GetParent(), this);
+ DCHECK(IsParent());
DCHECK(!HasHighInterval());
DCHECK(!HasLowInterval());
high_or_low_interval_ = new (allocator_) LiveInterval(