Add synthesize uses at back edge.
This reduces the cost of linearizing the graph (hence removing
the notion of back edge). Since linear scan allocates/spills registers
based on next use, adding a use at a back edge ensures we do count
for loop uses.
Change-Id: Idaa882cb120edbdd08ca6bff142d326a8245bd14
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 0533bff..c16f6f5 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -397,6 +397,11 @@
return back_edges_;
}
+ HBasicBlock* GetSingleBackEdge() const {
+ DCHECK_EQ(back_edges_.Size(), 1u);
+ return back_edges_.Get(0);
+ }
+
void ClearBackEdges() {
back_edges_.Reset();
}
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index a8d006f..812642b 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1467,23 +1467,28 @@
LiveRange* range = current->GetFirstRange();
while (range != nullptr) {
- DCHECK(use == nullptr || use->GetPosition() >= range->GetStart());
+ while (use != nullptr && use->GetPosition() < range->GetStart()) {
+ DCHECK(use->IsSynthesized());
+ use = use->GetNext();
+ }
while (use != nullptr && use->GetPosition() <= range->GetEnd()) {
DCHECK(!use->GetIsEnvironment());
DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd()));
- LocationSummary* locations = use->GetUser()->GetLocations();
- Location expected_location = locations->InAt(use->GetInputIndex());
- // The expected (actual) location may be invalid in case the input is unused. Currently
- // this only happens for intrinsics.
- if (expected_location.IsValid()) {
- if (expected_location.IsUnallocated()) {
- locations->SetInAt(use->GetInputIndex(), source);
- } else if (!expected_location.IsConstant()) {
- AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location);
+ if (!use->IsSynthesized()) {
+ LocationSummary* locations = use->GetUser()->GetLocations();
+ Location expected_location = locations->InAt(use->GetInputIndex());
+ // The expected (actual) location may be invalid in case the input is unused. Currently
+ // this only happens for intrinsics.
+ if (expected_location.IsValid()) {
+ if (expected_location.IsUnallocated()) {
+ locations->SetInAt(use->GetInputIndex(), source);
+ } else if (!expected_location.IsConstant()) {
+ AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location);
+ }
+ } else {
+ DCHECK(use->GetUser()->IsInvoke());
+ DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
}
- } else {
- DCHECK(use->GetUser()->IsInvoke());
- DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
}
use = use->GetNext();
}
@@ -1561,7 +1566,13 @@
current = next_sibling;
} while (current != nullptr);
- DCHECK(use == nullptr);
+ if (kIsDebugBuild) {
+ // Following uses can only be synthesized uses.
+ while (use != nullptr) {
+ DCHECK(use->IsSynthesized());
+ use = use->GetNext();
+ }
+ }
}
void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index b674f74..0bbcb30 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -341,7 +341,7 @@
size_t end = GetEnd();
while (use != nullptr && use->GetPosition() <= end) {
size_t use_position = use->GetPosition();
- if (use_position >= start) {
+ if (use_position >= start && !use->IsSynthesized()) {
HInstruction* user = use->GetUser();
size_t input_index = use->GetInputIndex();
if (user->IsPhi()) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index b95276a..b74e655 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -112,12 +112,15 @@
is_environment_(is_environment),
position_(position),
next_(next) {
- DCHECK(user->IsPhi()
+ DCHECK((user == nullptr)
+ || user->IsPhi()
|| (GetPosition() == user->GetLifetimePosition() + 1)
|| (GetPosition() == user->GetLifetimePosition()));
DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
}
+ static constexpr size_t kNoInput = -1;
+
size_t GetPosition() const { return position_; }
UsePosition* GetNext() const { return next_; }
@@ -126,14 +129,16 @@
HInstruction* GetUser() const { return user_; }
bool GetIsEnvironment() const { return is_environment_; }
+ bool IsSynthesized() const { return user_ == nullptr; }
size_t GetInputIndex() const { return input_index_; }
void Dump(std::ostream& stream) const {
stream << position_;
- if (is_environment_) {
- stream << " (env)";
- }
+ }
+
+ HLoopInformation* GetLoopInformation() const {
+ return user_->GetBlock()->GetLoopInformation();
}
UsePosition* Dup(ArenaAllocator* allocator) const {
@@ -142,6 +147,15 @@
next_ == nullptr ? nullptr : next_->Dup(allocator));
}
+ bool RequiresRegister() const {
+ if (GetIsEnvironment()) return false;
+ if (IsSynthesized()) return false;
+ Location location = GetUser()->GetLocations()->InAt(GetInputIndex());
+ return location.IsUnallocated()
+ && (location.GetPolicy() == Location::kRequiresRegister
+ || location.GetPolicy() == Location::kRequiresFpuRegister);
+ }
+
private:
HInstruction* const user_;
const size_t input_index_;
@@ -240,9 +254,15 @@
// location of the input just before that instruction (and not potential moves due
// to splitting).
position = instruction->GetLifetimePosition();
+ } else if (!locations->InAt(input_index).IsValid()) {
+ return;
}
}
+ if (!is_environment && instruction->IsInLoop()) {
+ AddBackEdgeUses(*instruction->GetBlock());
+ }
+
DCHECK(position == instruction->GetLifetimePosition()
|| position == instruction->GetLifetimePosition() + 1);
@@ -306,6 +326,9 @@
void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) {
DCHECK(instruction->IsPhi());
+ if (block->IsInLoop()) {
+ AddBackEdgeUses(*block);
+ }
first_use_ = new (allocator_) UsePosition(
instruction, input_index, false, block->GetLifetimeEnd(), first_use_);
}
@@ -456,27 +479,9 @@
if (is_temp_) {
return position == GetStart() ? position : kNoLifetime;
}
- 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
- // of the instruction requires a register, we return the position of that instruction
- // as the first register use.
- if (location.IsUnallocated()) {
- if ((location.GetPolicy() == Location::kRequiresRegister)
- || (location.GetPolicy() == Location::kSameAsFirstInput
- && (locations->InAt(0).IsRegister()
- || locations->InAt(0).IsRegisterPair()
- || locations->InAt(0).GetPolicy() == Location::kRequiresRegister))) {
- return position;
- } else if ((location.GetPolicy() == Location::kRequiresFpuRegister)
- || (location.GetPolicy() == Location::kSameAsFirstInput
- && locations->InAt(0).GetPolicy() == Location::kRequiresFpuRegister)) {
- return position;
- }
- } else if (location.IsRegister() || location.IsRegisterPair()) {
- return position;
- }
+
+ if (IsDefiningPosition(position) && DefinitionRequiresRegister()) {
+ return position;
}
UsePosition* use = first_use_;
@@ -484,10 +489,7 @@
while (use != nullptr && use->GetPosition() <= end) {
size_t use_position = use->GetPosition();
if (use_position > position) {
- Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
- if (location.IsUnallocated()
- && (location.GetPolicy() == Location::kRequiresRegister
- || location.GetPolicy() == Location::kRequiresFpuRegister)) {
+ if (use->RequiresRegister()) {
return use_position;
}
}
@@ -505,18 +507,16 @@
return position == GetStart() ? position : kNoLifetime;
}
- if (position == GetStart() && IsParent()) {
- if (defined_by_->GetLocations()->Out().IsValid()) {
- return position;
- }
+ if (IsDefiningPosition(position)) {
+ DCHECK(defined_by_->GetLocations()->Out().IsValid());
+ return position;
}
UsePosition* use = first_use_;
size_t end = GetEnd();
while (use != nullptr && use->GetPosition() <= end) {
- Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex());
size_t use_position = use->GetPosition();
- if (use_position > position && location.IsValid()) {
+ if (use_position > position) {
return use_position;
}
use = use->GetNext();
@@ -664,7 +664,7 @@
stream << " ";
} while ((use = use->GetNext()) != nullptr);
}
- stream << "}, {";
+ stream << "}, { ";
use = first_env_use_;
if (use != nullptr) {
do {
@@ -910,6 +910,100 @@
return range;
}
+ bool DefinitionRequiresRegister() const {
+ DCHECK(IsParent());
+ LocationSummary* locations = defined_by_->GetLocations();
+ Location location = locations->Out();
+ // This interval is the first interval of the instruction. If the output
+ // of the instruction requires a register, we return the position of that instruction
+ // as the first register use.
+ if (location.IsUnallocated()) {
+ if ((location.GetPolicy() == Location::kRequiresRegister)
+ || (location.GetPolicy() == Location::kSameAsFirstInput
+ && (locations->InAt(0).IsRegister()
+ || locations->InAt(0).IsRegisterPair()
+ || locations->InAt(0).GetPolicy() == Location::kRequiresRegister))) {
+ return true;
+ } else if ((location.GetPolicy() == Location::kRequiresFpuRegister)
+ || (location.GetPolicy() == Location::kSameAsFirstInput
+ && (locations->InAt(0).IsFpuRegister()
+ || locations->InAt(0).IsFpuRegisterPair()
+ || locations->InAt(0).GetPolicy() == Location::kRequiresFpuRegister))) {
+ return true;
+ }
+ } else if (location.IsRegister() || location.IsRegisterPair()) {
+ return true;
+ }
+ return false;
+ }
+
+ bool IsDefiningPosition(size_t position) const {
+ return IsParent() && (position == GetStart());
+ }
+
+ bool HasSynthesizeUseAt(size_t position) const {
+ UsePosition* use = first_use_;
+ while (use != nullptr) {
+ size_t use_position = use->GetPosition();
+ if ((use_position == position) && use->IsSynthesized()) {
+ return true;
+ }
+ if (use_position > position) break;
+ use = use->GetNext();
+ }
+ return false;
+ }
+
+ void AddBackEdgeUses(const HBasicBlock& block_at_use) {
+ DCHECK(block_at_use.IsInLoop());
+ // Add synthesized uses at the back edge of loops to help the register allocator.
+ // Note that this method is called in decreasing liveness order, to faciliate adding
+ // uses at the head of the `first_use_` linked list. Because below
+ // we iterate from inner-most to outer-most, which is in increasing liveness order,
+ // we need to take extra care of how the `first_use_` linked list is being updated.
+ UsePosition* first_in_new_list = nullptr;
+ UsePosition* last_in_new_list = nullptr;
+ for (HLoopInformationOutwardIterator it(block_at_use);
+ !it.Done();
+ it.Advance()) {
+ HLoopInformation* current = it.Current();
+ if (GetDefinedBy()->GetLifetimePosition() >= current->GetHeader()->GetLifetimeStart()) {
+ // This interval is defined in the loop. We can stop going outward.
+ break;
+ }
+
+ size_t back_edge_use_position = current->GetSingleBackEdge()->GetLifetimeEnd();
+ if ((first_use_ != nullptr) && (first_use_->GetPosition() <= back_edge_use_position)) {
+ // There was a use already seen in this loop. Therefore the previous call to `AddUse`
+ // already inserted the backedge use. We can stop going outward.
+ DCHECK(HasSynthesizeUseAt(back_edge_use_position));
+ break;
+ }
+
+ DCHECK(last_in_new_list == nullptr
+ || back_edge_use_position > last_in_new_list->GetPosition());
+
+ UsePosition* new_use = new (allocator_) UsePosition(
+ nullptr, UsePosition::kNoInput, /* is_environment */ false,
+ back_edge_use_position, nullptr);
+
+ if (last_in_new_list != nullptr) {
+ // Going outward. The latest created use needs to point to the new use.
+ last_in_new_list->SetNext(new_use);
+ } else {
+ // This is the inner-most loop.
+ DCHECK_EQ(current, block_at_use.GetLoopInformation());
+ first_in_new_list = new_use;
+ }
+ last_in_new_list = new_use;
+ }
+ // Link the newly created linked list with `first_use_`.
+ if (last_in_new_list != nullptr) {
+ last_in_new_list->SetNext(first_use_);
+ first_use_ = first_in_new_list;
+ }
+ }
+
ArenaAllocator* const allocator_;
// Ranges of this interval. We need a quick access to the last range to test
diff --git a/test/482-checker-loop-back-edge-use/expected.txt b/test/482-checker-loop-back-edge-use/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/482-checker-loop-back-edge-use/expected.txt
diff --git a/test/482-checker-loop-back-edge-use/info.txt b/test/482-checker-loop-back-edge-use/info.txt
new file mode 100644
index 0000000..f7fdeff
--- /dev/null
+++ b/test/482-checker-loop-back-edge-use/info.txt
@@ -0,0 +1,2 @@
+Tests the register allocator's optimization of adding synthesized uses
+at back edges.
diff --git a/test/482-checker-loop-back-edge-use/src/Main.java b/test/482-checker-loop-back-edge-use/src/Main.java
new file mode 100644
index 0000000..74184e8
--- /dev/null
+++ b/test/482-checker-loop-back-edge-use/src/Main.java
@@ -0,0 +1,131 @@
+/*
+* Copyright (C) 2015 The Android Open Source Project
+*
+* Licensed under the Apache License, Version 2.0 (the "License");
+* you may not use this file except in compliance with the License.
+* You may obtain a copy of the License at
+*
+* http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing, software
+* distributed under the License is distributed on an "AS IS" BASIS,
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+* See the License for the specific language governing permissions and
+* limitations under the License.
+*/
+
+
+public class Main {
+
+ // CHECK-START: void Main.loop1(boolean) liveness (after)
+ // CHECK: ParameterValue (liveness: 2 ranges: { [2, 22) }, uses: { 17 22 }
+ // CHECK: Goto (liveness: 20)
+ public static void loop1(boolean incoming) {
+ while (incoming) {}
+ }
+
+ // CHECK-START: void Main.loop2(boolean) liveness (after)
+ // CHECK: ParameterValue (liveness: 2 ranges: { [2, 42) }, uses: { 33 38 42 }
+ // CHECK: Goto (liveness: 36)
+ // CHECK: Goto (liveness: 40)
+ public static void loop2(boolean incoming) {
+ while (true) {
+ System.out.println("foo");
+ while (incoming) {}
+ }
+ }
+
+ // CHECK-START: void Main.loop3(boolean) liveness (after)
+ // CHECK: ParameterValue (liveness: 2 ranges: { [2, 60) }, uses: { 56 60 }
+ // CHECK: Goto (liveness: 58)
+
+ // CHECK-START: void Main.loop3(boolean) liveness (after)
+ // CHECK-NOT: Goto (liveness: 54)
+ public static void loop3(boolean incoming) {
+ // 'incoming' only needs a use at the outer loop's back edge.
+ while (System.currentTimeMillis() != 42) {
+ while (Runtime.getRuntime() != null) {}
+ System.out.println(incoming);
+ }
+ }
+
+ // CHECK-START: void Main.loop4(boolean) liveness (after)
+ // CHECK: ParameterValue (liveness: 2 ranges: { [2, 22) }, uses: { 22 }
+
+ // CHECK-START: void Main.loop4(boolean) liveness (after)
+ // CHECK-NOT: Goto (liveness: 20)
+ public static void loop4(boolean incoming) {
+ // 'incoming' has no loop use, so should not have back edge uses.
+ System.out.println(incoming);
+ while (System.currentTimeMillis() != 42) {
+ while (Runtime.getRuntime() != null) {}
+ }
+ }
+
+ // CHECK-START: void Main.loop5(boolean) liveness (after)
+ // CHECK: ParameterValue (liveness: 2 ranges: { [2, 50) }, uses: { 33 42 46 50 }
+ // CHECK: Goto (liveness: 44)
+ // CHECK: Goto (liveness: 48)
+ public static void loop5(boolean incoming) {
+ // 'incoming' must have a use at both back edges.
+ while (Runtime.getRuntime() != null) {
+ while (incoming) {
+ System.out.println(incoming);
+ }
+ }
+ }
+
+ // CHECK-START: void Main.loop6(boolean) liveness (after)
+ // CHECK ParameterValue (liveness: 2 ranges: { [2, 46) }, uses: { 24 46 }
+ // CHECK: Goto (liveness: 44)
+
+ // CHECK-START: void Main.loop6(boolean) liveness (after)
+ // CHECK-NOT: Goto (liveness: 22)
+ public static void loop6(boolean incoming) {
+ // 'incoming' must have a use only at the first loop's back edge.
+ while (true) {
+ System.out.println(incoming);
+ while (Runtime.getRuntime() != null) {}
+ }
+ }
+
+ // CHECK-START: void Main.loop7(boolean) liveness (after)
+ // CHECK: ParameterValue (liveness: 2 ranges: { [2, 50) }, uses: { 32 41 46 50 }
+ // CHECK: Goto (liveness: 44)
+ // CHECK: Goto (liveness: 48)
+ public static void loop7(boolean incoming) {
+ // 'incoming' must have a use at both back edges.
+ while (Runtime.getRuntime() != null) {
+ System.out.println(incoming);
+ while (incoming) {}
+ }
+ }
+
+ // CHECK-START: void Main.loop8() liveness (after)
+ // CHECK: StaticFieldGet (liveness: 12 ranges: { [12, 44) }, uses: { 35 40 44 }
+ // CHECK: Goto (liveness: 38)
+ // CHECK: Goto (liveness: 42)
+ public static void loop8() {
+ // 'incoming' must have a use at both back edges.
+ boolean incoming = field;
+ while (Runtime.getRuntime() != null) {
+ while (incoming) {}
+ }
+ }
+
+ // CHECK-START: void Main.loop9() liveness (after)
+ // CHECK: StaticFieldGet (liveness: 22 ranges: { [22, 36) }, uses: { 31 36 }
+ // CHECK: Goto (liveness: 38)
+ public static void loop9() {
+ while (Runtime.getRuntime() != null) {
+ // 'incoming' must only have a use in the inner loop.
+ boolean incoming = field;
+ while (incoming) {}
+ }
+ }
+
+ public static void main(String[] args) {
+ }
+
+ static boolean field;
+}