diff options
Diffstat (limited to 'compiler/optimizing')
-rw-r--r-- | compiler/optimizing/register_allocation_resolver.cc | 3 | ||||
-rw-r--r-- | compiler/optimizing/register_allocator_test.cc | 12 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.h | 106 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis_test.cc | 230 |
4 files changed, 308 insertions, 43 deletions
diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc index 59523a93a0..8a9c1ccaff 100644 --- a/compiler/optimizing/register_allocation_resolver.cc +++ b/compiler/optimizing/register_allocation_resolver.cc @@ -306,7 +306,7 @@ void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) { : Location::StackSlot(interval->GetParent()->GetSpillSlot())); } UsePosition* use = current->GetFirstUse(); - UsePosition* env_use = current->GetFirstEnvironmentUse(); + EnvUsePosition* env_use = current->GetFirstEnvironmentUse(); // Walk over all siblings, updating locations of use positions, and // connecting them when they are adjacent. @@ -323,7 +323,6 @@ void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) { use = use->GetNext(); } while (use != nullptr && use->GetPosition() <= range->GetEnd()) { - DCHECK(!use->GetIsEnvironment()); DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd())); if (!use->IsSynthesized()) { LocationSummary* locations = use->GetUser()->GetLocations(); diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc index 2227872f76..667afb1ec3 100644 --- a/compiler/optimizing/register_allocator_test.cc +++ b/compiler/optimizing/register_allocator_test.cc @@ -912,9 +912,9 @@ TEST_F(RegisterAllocatorTest, SpillInactive) { // Create an interval with lifetime holes. static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}}; LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one); - first->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, first->first_use_); - first->first_use_ = new(&allocator) UsePosition(user, 0, false, 7, first->first_use_); - first->first_use_ = new(&allocator) UsePosition(user, 0, false, 6, first->first_use_); + first->first_use_ = new(&allocator) UsePosition(user, false, 8, first->first_use_); + first->first_use_ = new(&allocator) UsePosition(user, false, 7, first->first_use_); + first->first_use_ = new(&allocator) UsePosition(user, false, 6, first->first_use_); locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall); locations->SetOut(Location::RequiresRegister()); @@ -934,9 +934,9 @@ TEST_F(RegisterAllocatorTest, SpillInactive) { // before lifetime position 6 yet. static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}}; LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three); - third->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, third->first_use_); - third->first_use_ = new(&allocator) UsePosition(user, 0, false, 4, third->first_use_); - third->first_use_ = new(&allocator) UsePosition(user, 0, false, 3, third->first_use_); + third->first_use_ = new(&allocator) UsePosition(user, false, 8, third->first_use_); + third->first_use_ = new(&allocator) UsePosition(user, false, 4, third->first_use_); + third->first_use_ = new(&allocator) UsePosition(user, false, 3, third->first_use_); locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall); locations->SetOut(Location::RequiresRegister()); third = third->SplitAt(3); diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index a239bd50c2..340d0ccefe 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -17,9 +17,10 @@ #ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ #define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ -#include "nodes.h" #include <iostream> +#include "nodes.h" + namespace art { class CodeGenerator; @@ -103,21 +104,20 @@ class LiveRange FINAL : public ArenaObject<kArenaAllocSsaLiveness> { */ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> { public: - UsePosition(HInstruction* user, - HEnvironment* environment, - size_t input_index, - size_t position, - UsePosition* next) + UsePosition(HInstruction* user, size_t input_index, size_t position, UsePosition* next) : user_(user), - environment_(environment), input_index_(input_index), position_(position), next_(next) { - DCHECK(environment == nullptr || user == nullptr); DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition()); } - static constexpr size_t kNoInput = -1; + explicit UsePosition(size_t position) + : user_(nullptr), + input_index_(kNoInput), + position_(dchecked_integral_cast<uint32_t>(position)), + next_(nullptr) { + } size_t GetPosition() const { return position_; } @@ -125,9 +125,7 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> { void SetNext(UsePosition* next) { next_ = next; } HInstruction* GetUser() const { return user_; } - HEnvironment* GetEnvironment() const { return environment_; } - bool GetIsEnvironment() const { return environment_ != nullptr; } bool IsSynthesized() const { return user_ == nullptr; } size_t GetInputIndex() const { return input_index_; } @@ -142,20 +140,20 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> { UsePosition* Dup(ArenaAllocator* allocator) const { return new (allocator) UsePosition( - user_, environment_, input_index_, position_, + user_, input_index_, position_, 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.RequiresRegisterKind(); } private: + static constexpr uint32_t kNoInput = static_cast<uint32_t>(-1); + HInstruction* const user_; - HEnvironment* const environment_; const size_t input_index_; const size_t position_; UsePosition* next_; @@ -163,6 +161,50 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> { DISALLOW_COPY_AND_ASSIGN(UsePosition); }; +/** + * An environment use position represents a live interval for environment use at a given position. + */ +class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness> { + public: + EnvUsePosition(HEnvironment* environment, + size_t input_index, + size_t position, + EnvUsePosition* next) + : environment_(environment), + input_index_(input_index), + position_(position), + next_(next) { + DCHECK(environment != nullptr); + DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition()); + } + + size_t GetPosition() const { return position_; } + + EnvUsePosition* GetNext() const { return next_; } + void SetNext(EnvUsePosition* next) { next_ = next; } + + HEnvironment* GetEnvironment() const { return environment_; } + size_t GetInputIndex() const { return input_index_; } + + void Dump(std::ostream& stream) const { + stream << position_; + } + + EnvUsePosition* Dup(ArenaAllocator* allocator) const { + return new (allocator) EnvUsePosition( + environment_, input_index_, position_, + next_ == nullptr ? nullptr : next_->Dup(allocator)); + } + + private: + HEnvironment* const environment_; + const size_t input_index_; + const size_t position_; + EnvUsePosition* next_; + + DISALLOW_COPY_AND_ASSIGN(EnvUsePosition); +}; + class SafepointPosition : public ArenaObject<kArenaAllocSsaLiveness> { public: explicit SafepointPosition(HInstruction* instruction) @@ -227,7 +269,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { DCHECK(first_env_use_ == nullptr) << "A temporary cannot have environment user"; size_t position = instruction->GetLifetimePosition(); first_use_ = new (allocator_) UsePosition( - instruction, /* environment */ nullptr, temp_index, position, first_use_); + instruction, temp_index, position, first_use_); AddRange(position, position + 1); } @@ -276,7 +318,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { } DCHECK(first_use_->GetPosition() + 1 == position); UsePosition* new_use = new (allocator_) UsePosition( - instruction, nullptr /* environment */, input_index, position, cursor->GetNext()); + instruction, input_index, position, cursor->GetNext()); cursor->SetNext(new_use); if (first_range_->GetEnd() == first_use_->GetPosition()) { first_range_->end_ = position; @@ -285,11 +327,11 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { } if (is_environment) { - first_env_use_ = new (allocator_) UsePosition( - nullptr /* instruction */, environment, input_index, position, first_env_use_); + first_env_use_ = new (allocator_) EnvUsePosition( + environment, input_index, position, first_env_use_); } else { first_use_ = new (allocator_) UsePosition( - instruction, nullptr /* environment */, input_index, position, first_use_); + instruction, input_index, position, first_use_); } if (is_environment && !keep_alive) { @@ -328,7 +370,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { AddBackEdgeUses(*block); } first_use_ = new (allocator_) UsePosition( - instruction, /* environment */ nullptr, input_index, block->GetLifetimeEnd(), first_use_); + instruction, input_index, block->GetLifetimeEnd(), first_use_); } ALWAYS_INLINE void AddRange(size_t start, size_t end) { @@ -538,7 +580,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { return first_use_; } - UsePosition* GetFirstEnvironmentUse() const { + EnvUsePosition* GetFirstEnvironmentUse() const { return first_env_use_; } @@ -676,7 +718,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { current = current->GetNext(); } stream << "}, uses: { "; - UsePosition* use = first_use_; + const UsePosition* use = first_use_; if (use != nullptr) { do { use->Dump(stream); @@ -684,12 +726,12 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { } while ((use = use->GetNext()) != nullptr); } stream << "}, { "; - use = first_env_use_; - if (use != nullptr) { + const EnvUsePosition* env_use = first_env_use_; + if (env_use != nullptr) { do { - use->Dump(stream); + env_use->Dump(stream); stream << " "; - } while ((use = use->GetNext()) != nullptr); + } while ((env_use = env_use->GetNext()) != nullptr); } stream << "}"; stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit(); @@ -1015,12 +1057,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { DCHECK(last_in_new_list == nullptr || back_edge_use_position > last_in_new_list->GetPosition()); - UsePosition* new_use = new (allocator_) UsePosition( - /* user */ nullptr, - /* environment */ nullptr, - UsePosition::kNoInput, - back_edge_use_position, - /* next */ nullptr); + UsePosition* new_use = new (allocator_) UsePosition(back_edge_use_position); if (last_in_new_list != nullptr) { // Going outward. The latest created use needs to point to the new use. @@ -1056,7 +1093,7 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { // Uses of this interval. Note that this linked list is shared amongst siblings. UsePosition* first_use_; - UsePosition* first_env_use_; + EnvUsePosition* first_env_use_; // The instruction type this interval corresponds to. const Primitive::Type type_; @@ -1210,8 +1247,7 @@ class SsaLivenessAnalysis : public ValueObject { // Returns whether `instruction` in an HEnvironment held by `env_holder` // should be kept live by the HEnvironment. - static bool ShouldBeLiveForEnvironment(HInstruction* env_holder, - HInstruction* instruction) { + static bool ShouldBeLiveForEnvironment(HInstruction* env_holder, HInstruction* instruction) { if (instruction == nullptr) return false; // A value that's not live in compiled code may still be needed in interpreter, // due to code motion, etc. diff --git a/compiler/optimizing/ssa_liveness_analysis_test.cc b/compiler/optimizing/ssa_liveness_analysis_test.cc new file mode 100644 index 0000000000..cc48d3196b --- /dev/null +++ b/compiler/optimizing/ssa_liveness_analysis_test.cc @@ -0,0 +1,230 @@ +/* + * Copyright (C) 2017 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. + */ + +#include "arch/instruction_set.h" +#include "arch/instruction_set_features.h" +#include "base/arena_allocator.h" +#include "base/arena_containers.h" +#include "driver/compiler_options.h" +#include "code_generator.h" +#include "nodes.h" +#include "optimizing_unit_test.h" +#include "ssa_liveness_analysis.h" + +namespace art { + +class SsaLivenessAnalysisTest : public testing::Test { + public: + SsaLivenessAnalysisTest() + : pool_(), + allocator_(&pool_), + graph_(CreateGraph(&allocator_)), + instruction_set_(kRuntimeISA) { + std::string error_msg; + instruction_set_features_ = + InstructionSetFeatures::FromVariant(instruction_set_, "default", &error_msg); + codegen_ = CodeGenerator::Create(graph_, + instruction_set_, + *instruction_set_features_, + CompilerOptions()); + CHECK(codegen_ != nullptr) << instruction_set_ << " is not a supported target architecture."; + // Create entry block. + entry_ = new (&allocator_) HBasicBlock(graph_); + graph_->AddBlock(entry_); + graph_->SetEntryBlock(entry_); + } + + protected: + HBasicBlock* CreateSuccessor(HBasicBlock* block) { + HGraph* graph = block->GetGraph(); + HBasicBlock* successor = new (&allocator_) HBasicBlock(graph); + graph->AddBlock(successor); + block->AddSuccessor(successor); + return successor; + } + + ArenaPool pool_; + ArenaAllocator allocator_; + HGraph* graph_; + InstructionSet instruction_set_; + std::unique_ptr<const InstructionSetFeatures> instruction_set_features_; + std::unique_ptr<CodeGenerator> codegen_; + HBasicBlock* entry_; +}; + +TEST_F(SsaLivenessAnalysisTest, TestReturnArg) { + HInstruction* arg = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt); + entry_->AddInstruction(arg); + + HBasicBlock* block = CreateSuccessor(entry_); + HInstruction* ret = new (&allocator_) HReturn(arg); + block->AddInstruction(ret); + block->AddInstruction(new (&allocator_) HExit()); + + graph_->BuildDominatorTree(); + SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get()); + ssa_analysis.Analyze(); + + std::ostringstream arg_dump; + arg->GetLiveInterval()->Dump(arg_dump); + EXPECT_STREQ("ranges: { [2,6) }, uses: { 6 }, { } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0", + arg_dump.str().c_str()); +} + +TEST_F(SsaLivenessAnalysisTest, TestAput) { + HInstruction* array = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); + HInstruction* index = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt); + HInstruction* value = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(2), 2, Primitive::kPrimInt); + HInstruction* extra_arg1 = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(3), 3, Primitive::kPrimInt); + HInstruction* extra_arg2 = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(4), 4, Primitive::kPrimNot); + ArenaVector<HInstruction*> args({ array, index, value, extra_arg1, extra_arg2 }, + allocator_.Adapter()); + for (HInstruction* insn : args) { + entry_->AddInstruction(insn); + } + + HBasicBlock* block = CreateSuccessor(entry_); + HInstruction* null_check = new (&allocator_) HNullCheck(array, 0); + block->AddInstruction(null_check); + HEnvironment* null_check_env = new (&allocator_) HEnvironment(&allocator_, + /* number_of_vregs */ 5, + /* method */ nullptr, + /* dex_pc */ 0u, + null_check); + null_check_env->CopyFrom(args); + null_check->SetRawEnvironment(null_check_env); + HInstruction* length = new (&allocator_) HArrayLength(array, 0); + block->AddInstruction(length); + HInstruction* bounds_check = new (&allocator_) HBoundsCheck(index, length, /* dex_pc */ 0u); + block->AddInstruction(bounds_check); + HEnvironment* bounds_check_env = new (&allocator_) HEnvironment(&allocator_, + /* number_of_vregs */ 5, + /* method */ nullptr, + /* dex_pc */ 0u, + bounds_check); + bounds_check_env->CopyFrom(args); + bounds_check->SetRawEnvironment(bounds_check_env); + HInstruction* array_set = + new (&allocator_) HArraySet(array, index, value, Primitive::kPrimInt, /* dex_pc */ 0); + block->AddInstruction(array_set); + + graph_->BuildDominatorTree(); + SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get()); + ssa_analysis.Analyze(); + + EXPECT_FALSE(graph_->IsDebuggable()); + EXPECT_EQ(18u, bounds_check->GetLifetimePosition()); + static const char* const expected[] = { + "ranges: { [2,21) }, uses: { 15 17 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 " + "is_high: 0", + "ranges: { [4,21) }, uses: { 19 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 " + "is_high: 0", + "ranges: { [6,21) }, uses: { 21 }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 " + "is_high: 0", + // Environment uses do not keep the non-reference argument alive. + "ranges: { [8,10) }, uses: { }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0", + // Environment uses keep the reference argument alive. + "ranges: { [10,19) }, uses: { }, { 15 19 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0", + }; + ASSERT_EQ(arraysize(expected), args.size()); + size_t arg_index = 0u; + for (HInstruction* arg : args) { + std::ostringstream arg_dump; + arg->GetLiveInterval()->Dump(arg_dump); + EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index; + ++arg_index; + } +} + +TEST_F(SsaLivenessAnalysisTest, TestDeoptimize) { + HInstruction* array = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); + HInstruction* index = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt); + HInstruction* value = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(2), 2, Primitive::kPrimInt); + HInstruction* extra_arg1 = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(3), 3, Primitive::kPrimInt); + HInstruction* extra_arg2 = new (&allocator_) HParameterValue( + graph_->GetDexFile(), dex::TypeIndex(4), 4, Primitive::kPrimNot); + ArenaVector<HInstruction*> args({ array, index, value, extra_arg1, extra_arg2 }, + allocator_.Adapter()); + for (HInstruction* insn : args) { + entry_->AddInstruction(insn); + } + + HBasicBlock* block = CreateSuccessor(entry_); + HInstruction* null_check = new (&allocator_) HNullCheck(array, 0); + block->AddInstruction(null_check); + HEnvironment* null_check_env = new (&allocator_) HEnvironment(&allocator_, + /* number_of_vregs */ 5, + /* method */ nullptr, + /* dex_pc */ 0u, + null_check); + null_check_env->CopyFrom(args); + null_check->SetRawEnvironment(null_check_env); + HInstruction* length = new (&allocator_) HArrayLength(array, 0); + block->AddInstruction(length); + // Use HAboveOrEqual+HDeoptimize as the bounds check. + HInstruction* ae = new (&allocator_) HAboveOrEqual(index, length); + block->AddInstruction(ae); + HInstruction* deoptimize = new(&allocator_) HDeoptimize(ae, /* dex_pc */ 0u); + block->AddInstruction(deoptimize); + HEnvironment* deoptimize_env = new (&allocator_) HEnvironment(&allocator_, + /* number_of_vregs */ 5, + /* method */ nullptr, + /* dex_pc */ 0u, + deoptimize); + deoptimize_env->CopyFrom(args); + deoptimize->SetRawEnvironment(deoptimize_env); + HInstruction* array_set = + new (&allocator_) HArraySet(array, index, value, Primitive::kPrimInt, /* dex_pc */ 0); + block->AddInstruction(array_set); + + graph_->BuildDominatorTree(); + SsaLivenessAnalysis ssa_analysis(graph_, codegen_.get()); + ssa_analysis.Analyze(); + + EXPECT_FALSE(graph_->IsDebuggable()); + EXPECT_EQ(20u, deoptimize->GetLifetimePosition()); + static const char* const expected[] = { + "ranges: { [2,23) }, uses: { 15 17 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 " + "is_high: 0", + "ranges: { [4,23) }, uses: { 19 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 " + "is_high: 0", + "ranges: { [6,23) }, uses: { 23 }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0", + // Environment use in HDeoptimize keeps even the non-reference argument alive. + "ranges: { [8,21) }, uses: { }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0", + // Environment uses keep the reference argument alive. + "ranges: { [10,21) }, uses: { }, { 15 21 } is_fixed: 0, is_split: 0 is_low: 0 is_high: 0", + }; + ASSERT_EQ(arraysize(expected), args.size()); + size_t arg_index = 0u; + for (HInstruction* arg : args) { + std::ostringstream arg_dump; + arg->GetLiveInterval()->Dump(arg_dump); + EXPECT_STREQ(expected[arg_index], arg_dump.str().c_str()) << arg_index; + ++arg_index; + } +} + +} // namespace art |