diff options
author | Nicolas Geoffray <ngeoffray@google.com> | 2014-06-09 15:02:22 +0100 |
---|---|---|
committer | Nicolas Geoffray <ngeoffray@google.com> | 2014-06-10 10:48:50 +0100 |
commit | 31d76b42ef5165351499da3f8ee0ac147428c5ed (patch) | |
tree | 4f9cf307923c72f73e4a814662a26406f155c38c | |
parent | 7eb3fa1e03b070c55ecbc814e2e3ae4409cf7b1e (diff) | |
download | art-31d76b42ef5165351499da3f8ee0ac147428c5ed.zip art-31d76b42ef5165351499da3f8ee0ac147428c5ed.tar.gz art-31d76b42ef5165351499da3f8ee0ac147428c5ed.tar.bz2 |
Plug code generator into liveness analysis.
Also implement spill slot support.
Change-Id: If5e28811e9fbbf3842a258772c633318a2f4fafc
-rw-r--r-- | compiler/optimizing/code_generator_arm.cc | 17 | ||||
-rw-r--r-- | compiler/optimizing/code_generator_x86.cc | 17 | ||||
-rw-r--r-- | compiler/optimizing/linearize_test.cc | 6 | ||||
-rw-r--r-- | compiler/optimizing/live_ranges_test.cc | 24 | ||||
-rw-r--r-- | compiler/optimizing/liveness_test.cc | 22 | ||||
-rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 2 | ||||
-rw-r--r-- | compiler/optimizing/register_allocator.cc | 121 | ||||
-rw-r--r-- | compiler/optimizing/register_allocator.h | 7 | ||||
-rw-r--r-- | compiler/optimizing/register_allocator_test.cc | 41 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.cc | 66 | ||||
-rw-r--r-- | compiler/optimizing/ssa_liveness_analysis.h | 199 |
11 files changed, 376 insertions, 146 deletions
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index ed3f43c..e888cc1 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -484,7 +484,10 @@ void InstructionCodeGeneratorARM::VisitStoreLocal(HStoreLocal* store) { } void LocationsBuilderARM::VisitIntConstant(HIntConstant* constant) { - constant->SetLocations(nullptr); + // TODO: Support constant locations. + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant); + locations->SetOut(Location::RequiresRegister()); + constant->SetLocations(locations); } void InstructionCodeGeneratorARM::VisitIntConstant(HIntConstant* constant) { @@ -492,7 +495,10 @@ void InstructionCodeGeneratorARM::VisitIntConstant(HIntConstant* constant) { } void LocationsBuilderARM::VisitLongConstant(HLongConstant* constant) { - constant->SetLocations(nullptr); + // TODO: Support constant locations. + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant); + locations->SetOut(Location::RequiresRegister()); + constant->SetLocations(locations); } void InstructionCodeGeneratorARM::VisitLongConstant(HLongConstant* constant) { @@ -794,7 +800,12 @@ void InstructionCodeGeneratorARM::VisitNot(HNot* instruction) { } void LocationsBuilderARM::VisitPhi(HPhi* instruction) { - LOG(FATAL) << "Unimplemented"; + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction); + for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { + locations->SetInAt(i, Location::Any()); + } + locations->SetOut(Location::Any()); + instruction->SetLocations(locations); } void InstructionCodeGeneratorARM::VisitPhi(HPhi* instruction) { diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index 8bfd8d6..72c697f 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -494,7 +494,10 @@ void InstructionCodeGeneratorX86::VisitEqual(HEqual* equal) { } void LocationsBuilderX86::VisitIntConstant(HIntConstant* constant) { - constant->SetLocations(nullptr); + // TODO: Support constant locations. + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant); + locations->SetOut(Location::RequiresRegister()); + constant->SetLocations(locations); } void InstructionCodeGeneratorX86::VisitIntConstant(HIntConstant* constant) { @@ -502,7 +505,10 @@ void InstructionCodeGeneratorX86::VisitIntConstant(HIntConstant* constant) { } void LocationsBuilderX86::VisitLongConstant(HLongConstant* constant) { - constant->SetLocations(nullptr); + // TODO: Support constant locations. + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(constant); + locations->SetOut(Location::RequiresRegister()); + constant->SetLocations(locations); } void InstructionCodeGeneratorX86::VisitLongConstant(HLongConstant* constant) { @@ -814,7 +820,12 @@ void InstructionCodeGeneratorX86::VisitNot(HNot* instruction) { } void LocationsBuilderX86::VisitPhi(HPhi* instruction) { - LOG(FATAL) << "Unimplemented"; + LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction); + for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) { + locations->SetInAt(i, Location::Any()); + } + locations->SetOut(Location::Any()); + instruction->SetLocations(locations); } void InstructionCodeGeneratorX86::VisitPhi(HPhi* instruction) { diff --git a/compiler/optimizing/linearize_test.cc b/compiler/optimizing/linearize_test.cc index f9ae529..e4f9371 100644 --- a/compiler/optimizing/linearize_test.cc +++ b/compiler/optimizing/linearize_test.cc @@ -18,6 +18,7 @@ #include "base/stringprintf.h" #include "builder.h" +#include "code_generator.h" #include "dex_file.h" #include "dex_instruction.h" #include "graph_visualizer.h" @@ -41,8 +42,11 @@ static void TestCode(const uint16_t* data, const int* expected_order, size_t num ASSERT_NE(graph, nullptr); graph->BuildDominatorTree(); + graph->TransformToSSA(); graph->FindNaturalLoops(); - SsaLivenessAnalysis liveness(*graph); + + CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); + SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks); diff --git a/compiler/optimizing/live_ranges_test.cc b/compiler/optimizing/live_ranges_test.cc index 017117a..987c5f2 100644 --- a/compiler/optimizing/live_ranges_test.cc +++ b/compiler/optimizing/live_ranges_test.cc @@ -15,6 +15,7 @@ */ #include "builder.h" +#include "code_generator.h" #include "dex_file.h" #include "dex_instruction.h" #include "nodes.h" @@ -56,14 +57,16 @@ TEST(LiveRangesTest, CFG1) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = BuildGraph(data, &allocator); - SsaLivenessAnalysis liveness(*graph); + + CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); + SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); LiveRange* range = interval->GetFirstRange(); ASSERT_EQ(2u, range->GetStart()); // Last use is the return instruction. - ASSERT_EQ(8u, range->GetEnd()); + ASSERT_EQ(9u, range->GetEnd()); HBasicBlock* block = graph->GetBlocks().Get(1); ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr); ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition()); @@ -101,14 +104,15 @@ TEST(LiveRangesTest, CFG2) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = BuildGraph(data, &allocator); - SsaLivenessAnalysis liveness(*graph); + CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); + SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); LiveRange* range = interval->GetFirstRange(); ASSERT_EQ(2u, range->GetStart()); // Last use is the return instruction. - ASSERT_EQ(22u, range->GetEnd()); + ASSERT_EQ(23u, range->GetEnd()); HBasicBlock* block = graph->GetBlocks().Get(3); ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr); ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition()); @@ -149,7 +153,8 @@ TEST(LiveRangesTest, CFG3) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = BuildGraph(data, &allocator); - SsaLivenessAnalysis liveness(*graph); + CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); + SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); // Test for the 4 constant. @@ -181,7 +186,7 @@ TEST(LiveRangesTest, CFG3) { range = interval->GetFirstRange(); ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(3)->GetLifetimePosition()); ASSERT_EQ(22u, range->GetStart()); - ASSERT_EQ(24u, range->GetEnd()); + ASSERT_EQ(25u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); } @@ -224,7 +229,8 @@ TEST(LiveRangesTest, Loop) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = BuildGraph(data, &allocator); - SsaLivenessAnalysis liveness(*graph); + CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); + SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); // Test for the 0 constant. @@ -249,7 +255,7 @@ TEST(LiveRangesTest, Loop) { range = interval->GetFirstRange(); // The instruction is live until the return instruction after the loop. ASSERT_EQ(6u, range->GetStart()); - ASSERT_EQ(26u, range->GetEnd()); + ASSERT_EQ(27u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); // Test for the phi. @@ -257,7 +263,7 @@ TEST(LiveRangesTest, Loop) { range = interval->GetFirstRange(); // Instruction is consumed by the if. ASSERT_EQ(14u, range->GetStart()); - ASSERT_EQ(16u, range->GetEnd()); + ASSERT_EQ(17u, range->GetEnd()); ASSERT_TRUE(range->GetNext() == nullptr); } diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc index 7a33620..2d0bc39 100644 --- a/compiler/optimizing/liveness_test.cc +++ b/compiler/optimizing/liveness_test.cc @@ -15,6 +15,7 @@ */ #include "builder.h" +#include "code_generator.h" #include "dex_file.h" #include "dex_instruction.h" #include "nodes.h" @@ -48,7 +49,8 @@ static void TestCode(const uint16_t* data, const char* expected) { graph->BuildDominatorTree(); graph->TransformToSSA(); graph->FindNaturalLoops(); - SsaLivenessAnalysis liveness(*graph); + CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); + SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); std::ostringstream buffer; @@ -69,17 +71,17 @@ static void TestCode(const uint16_t* data, const char* expected) { TEST(LivenessTest, CFG1) { const char* expected = "Block 0\n" - " live in: ()\n" - " live out: ()\n" - " kill: ()\n" + " live in: (0)\n" + " live out: (0)\n" + " kill: (1)\n" "Block 1\n" - " live in: ()\n" - " live out: ()\n" - " kill: ()\n" + " live in: (0)\n" + " live out: (0)\n" + " kill: (0)\n" "Block 2\n" - " live in: ()\n" - " live out: ()\n" - " kill: ()\n"; + " live in: (0)\n" + " live out: (0)\n" + " kill: (0)\n"; // Constant is not used. const uint16_t data[] = ONE_REGISTER_CODE_ITEM( diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index dfbb488..3dc0928 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -131,7 +131,7 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite visualizer.DumpGraph("ssa"); graph->FindNaturalLoops(); - SsaLivenessAnalysis liveness(*graph); + SsaLivenessAnalysis liveness(*graph, codegen); liveness.Analyze(); visualizer.DumpGraph("liveness"); diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index dd175d2..8c6eb2a 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -22,6 +22,7 @@ namespace art { static constexpr size_t kMaxLifetimePosition = -1; +static constexpr size_t kDefaultNumberOfSpillSlots = 4; RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen) : allocator_(allocator), @@ -30,6 +31,7 @@ RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenera handled_(allocator, 0), active_(allocator, 0), inactive_(allocator, 0), + spill_slots_(allocator, kDefaultNumberOfSpillSlots), processing_core_registers_(false), number_of_registers_(-1), registers_array_(nullptr), @@ -78,11 +80,39 @@ bool RegisterAllocator::ValidateInternal(const SsaLivenessAnalysis& liveness, intervals.Add(instruction->GetLiveInterval()); } } - return ValidateIntervals(intervals, codegen_, allocator_, processing_core_registers_, - log_fatal_on_failure); + return ValidateIntervals(intervals, spill_slots_.Size(), codegen_, allocator_, + processing_core_registers_, log_fatal_on_failure); } -bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ranges, +class AllRangesIterator : public ValueObject { + public: + explicit AllRangesIterator(LiveInterval* interval) + : current_interval_(interval), + current_range_(interval->GetFirstRange()) {} + + bool Done() const { return current_interval_ == nullptr; } + LiveRange* CurrentRange() const { return current_range_; } + LiveInterval* CurrentInterval() const { return current_interval_; } + + void Advance() { + current_range_ = current_range_->GetNext(); + if (current_range_ == nullptr) { + current_interval_ = current_interval_->GetNextSibling(); + if (current_interval_ != nullptr) { + current_range_ = current_interval_->GetFirstRange(); + } + } + } + + private: + LiveInterval* current_interval_; + LiveRange* current_range_; + + DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); +}; + +bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, + size_t number_of_spill_slots, const CodeGenerator& codegen, ArenaAllocator* allocator, bool processing_core_registers, @@ -90,25 +120,40 @@ bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ra size_t number_of_registers = processing_core_registers ? codegen.GetNumberOfCoreRegisters() : codegen.GetNumberOfFloatingPointRegisters(); - GrowableArray<ArenaBitVector*> bit_vectors(allocator, number_of_registers); + GrowableArray<ArenaBitVector*> liveness_of_values( + allocator, number_of_registers + number_of_spill_slots); // Allocate a bit vector per register. A live interval that has a register // allocated will populate the associated bit vector based on its live ranges. - for (size_t i = 0; i < number_of_registers; i++) { - bit_vectors.Add(new (allocator) ArenaBitVector(allocator, 0, true)); + for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { + liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); } - for (size_t i = 0, e = ranges.Size(); i < e; ++i) { - LiveInterval* current = ranges.Get(i); - do { - if (!current->HasRegister()) { - continue; + for (size_t i = 0, e = intervals.Size(); i < e; ++i) { + for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { + LiveInterval* current = it.CurrentInterval(); + if (current->GetParent()->HasSpillSlot()) { + BitVector* liveness_of_spill_slot = liveness_of_values.Get( + number_of_registers + current->GetParent()->GetSpillSlot() / kVRegSize); + for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { + if (liveness_of_spill_slot->IsBitSet(j)) { + if (log_fatal_on_failure) { + std::ostringstream message; + message << "Spill slot conflict at " << j; + LOG(FATAL) << message.str(); + } else { + return false; + } + } else { + liveness_of_spill_slot->SetBit(j); + } + } } - BitVector* vector = bit_vectors.Get(current->GetRegister()); - LiveRange* range = current->GetFirstRange(); - do { - for (size_t j = range->GetStart(); j < range->GetEnd(); ++j) { - if (vector->IsBitSet(j)) { + + if (current->HasRegister()) { + BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); + for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { + if (liveness_of_register->IsBitSet(j)) { if (log_fatal_on_failure) { std::ostringstream message; message << "Register conflict at " << j << " for "; @@ -122,11 +167,11 @@ bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ra return false; } } else { - vector->SetBit(j); + liveness_of_register->SetBit(j); } } - } while ((range = range->GetNext()) != nullptr); - } while ((current = current->GetNextSibling()) != nullptr); + } + } } return true; } @@ -270,7 +315,7 @@ bool RegisterAllocator::IsBlocked(int reg) const { bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { size_t first_register_use = current->FirstRegisterUse(); if (current->FirstRegisterUse() == kNoLifetime) { - // TODO: Allocate spill slot for `current`. + AllocateSpillSlotFor(current); return false; } @@ -317,6 +362,7 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { if (first_register_use >= next_use[reg]) { // If the first use of that instruction is after the last use of the found // register, we split this interval just before its first register use. + AllocateSpillSlotFor(current); LiveInterval* split = Split(current, first_register_use - 1); AddToUnhandled(split); return false; @@ -370,9 +416,42 @@ LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) return interval; } else { LiveInterval* new_interval = interval->SplitAt(position); - // TODO: Allocate spill slot for `interval`. return new_interval; } } +void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { + LiveInterval* parent = interval->GetParent(); + + // An instruction gets a spill slot for its entire lifetime. If the parent + // of this interval already has a spill slot, there is nothing to do. + if (parent->HasSpillSlot()) { + return; + } + + // Find when this instruction dies. + LiveInterval* last_sibling = interval; + while (last_sibling->GetNextSibling() != nullptr) { + last_sibling = last_sibling->GetNextSibling(); + } + size_t end = last_sibling->GetEnd(); + + // Find an available spill slot. + size_t slot = 0; + for (size_t e = spill_slots_.Size(); slot < e; ++slot) { + if (spill_slots_.Get(slot) <= parent->GetStart()) { + break; + } + } + + if (slot == spill_slots_.Size()) { + // We need a new spill slot. + spill_slots_.Add(end); + } else { + spill_slots_.Put(slot, end); + } + + interval->GetParent()->SetSpillSlot(slot * kVRegSize); +} + } // namespace art diff --git a/compiler/optimizing/register_allocator.h b/compiler/optimizing/register_allocator.h index e575b96..3393a04 100644 --- a/compiler/optimizing/register_allocator.h +++ b/compiler/optimizing/register_allocator.h @@ -55,6 +55,7 @@ class RegisterAllocator { // Helper method for validation. Used by unit testing. static bool ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, + size_t number_of_spill_slots, const CodeGenerator& codegen, ArenaAllocator* allocator, bool processing_core_registers, @@ -75,6 +76,9 @@ class RegisterAllocator { // Returns whether `reg` is blocked by the code generator. bool IsBlocked(int reg) const; + // Allocate a spill slot for the given interval. + void AllocateSpillSlotFor(LiveInterval* interval); + // Helper methods. void AllocateRegistersInternal(const SsaLivenessAnalysis& liveness); bool ValidateInternal(const SsaLivenessAnalysis& liveness, bool log_fatal_on_failure) const; @@ -98,6 +102,9 @@ class RegisterAllocator { // That is, they have a lifetime hole that spans the start of the new interval. GrowableArray<LiveInterval*> inactive_; + // The spill slots allocated for live intervals. + GrowableArray<size_t> spill_slots_; + // True if processing core registers. False if processing floating // point registers. bool processing_core_registers_; diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc index 019d0f8..ff9b9be 100644 --- a/compiler/optimizing/register_allocator_test.cc +++ b/compiler/optimizing/register_allocator_test.cc @@ -40,9 +40,9 @@ static bool Check(const uint16_t* data) { graph->BuildDominatorTree(); graph->TransformToSSA(); graph->FindNaturalLoops(); - SsaLivenessAnalysis liveness(*graph); - liveness.Analyze(); CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); + SsaLivenessAnalysis liveness(*graph, codegen); + liveness.Analyze(); RegisterAllocator register_allocator(&allocator, *codegen); register_allocator.AllocateRegisters(liveness); return register_allocator.Validate(liveness, false); @@ -64,10 +64,12 @@ TEST(RegisterAllocatorTest, ValidateIntervals) { static constexpr size_t ranges[][2] = {{0, 42}}; intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 0)); intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 1)); - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Get(1)->SetRegister(0); - ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_FALSE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Reset(); } @@ -77,10 +79,12 @@ TEST(RegisterAllocatorTest, ValidateIntervals) { intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); static constexpr size_t ranges2[][2] = {{42, 43}}; intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Get(1)->SetRegister(0); - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Reset(); } @@ -90,10 +94,12 @@ TEST(RegisterAllocatorTest, ValidateIntervals) { intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); static constexpr size_t ranges2[][2] = {{42, 43}}; intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Get(1)->SetRegister(0); - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Reset(); } @@ -103,10 +109,12 @@ TEST(RegisterAllocatorTest, ValidateIntervals) { intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); static constexpr size_t ranges2[][2] = {{42, 47}}; intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Get(1)->SetRegister(0); - ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_FALSE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Reset(); } @@ -117,14 +125,17 @@ TEST(RegisterAllocatorTest, ValidateIntervals) { intervals.Get(0)->SplitAt(43); static constexpr size_t ranges2[][2] = {{42, 47}}; intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Get(1)->SetRegister(0); // Sibling of the first interval has no register allocated to it. - ASSERT_TRUE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_TRUE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); intervals.Get(0)->GetNextSibling()->SetRegister(0); - ASSERT_FALSE(RegisterAllocator::ValidateIntervals(intervals, *codegen, &allocator, true, false)); + ASSERT_FALSE(RegisterAllocator::ValidateIntervals( + intervals, 0, *codegen, &allocator, true, false)); } } @@ -286,9 +297,9 @@ TEST(RegisterAllocatorTest, Loop3) { ArenaPool pool; ArenaAllocator allocator(&pool); HGraph* graph = BuildSSAGraph(data, &allocator); - SsaLivenessAnalysis liveness(*graph); - liveness.Analyze(); CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86); + SsaLivenessAnalysis liveness(*graph, codegen); + liveness.Analyze(); RegisterAllocator register_allocator(&allocator, *codegen); register_allocator.AllocateRegisters(liveness); ASSERT_TRUE(register_allocator.Validate(liveness, false)); diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index c367611..50ea00f 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -15,6 +15,8 @@ */ #include "ssa_liveness_analysis.h" + +#include "code_generator.h" #include "nodes.h" namespace art { @@ -80,38 +82,6 @@ static void VisitBlockForLinearization(HBasicBlock* block, order->Add(block); } -class HLinearOrderIterator : public ValueObject { - public: - explicit HLinearOrderIterator(const GrowableArray<HBasicBlock*>& post_order) - : post_order_(post_order), index_(post_order.Size()) {} - - bool Done() const { return index_ == 0; } - HBasicBlock* Current() const { return post_order_.Get(index_ -1); } - void Advance() { --index_; DCHECK_GE(index_, 0U); } - - private: - const GrowableArray<HBasicBlock*>& post_order_; - size_t index_; - - DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); -}; - -class HLinearPostOrderIterator : public ValueObject { - public: - explicit HLinearPostOrderIterator(const GrowableArray<HBasicBlock*>& post_order) - : post_order_(post_order), index_(0) {} - - bool Done() const { return index_ == post_order_.Size(); } - HBasicBlock* Current() const { return post_order_.Get(index_); } - void Advance() { ++index_; } - - private: - const GrowableArray<HBasicBlock*>& post_order_; - size_t index_; - - DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); -}; - void SsaLivenessAnalysis::LinearizeGraph() { // For simplicity of the implementation, we create post linear order. The order for // computing live ranges is the reverse of that order. @@ -131,30 +101,38 @@ void SsaLivenessAnalysis::NumberInstructions() { // to differentiate between the start and end of an instruction. Adding 2 to // the lifetime position for each instruction ensures the start of an // instruction is different than the end of the previous instruction. - for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { + for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); block->SetLifetimeStart(lifetime_position); for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { HInstruction* current = it.Current(); - if (current->HasUses()) { + current->Accept(codegen_->GetLocationBuilder()); + LocationSummary* locations = current->GetLocations(); + if (locations != nullptr && locations->Out().IsValid()) { instructions_from_ssa_index_.Add(current); current->SetSsaIndex(ssa_index++); current->SetLiveInterval( - new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType())); + new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current)); } current->SetLifetimePosition(lifetime_position); } lifetime_position += 2; + // Add a null marker to notify we are starting a block. + instructions_from_lifetime_position_.Add(nullptr); + for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { HInstruction* current = it.Current(); - if (current->HasUses()) { + current->Accept(codegen_->GetLocationBuilder()); + LocationSummary* locations = current->GetLocations(); + if (locations != nullptr && locations->Out().IsValid()) { instructions_from_ssa_index_.Add(current); current->SetSsaIndex(ssa_index++); current->SetLiveInterval( - new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType())); + new (graph_.GetArena()) LiveInterval(graph_.GetArena(), current->GetType(), current)); } + instructions_from_lifetime_position_.Add(current); current->SetLifetimePosition(lifetime_position); lifetime_position += 2; } @@ -165,7 +143,7 @@ void SsaLivenessAnalysis::NumberInstructions() { } void SsaLivenessAnalysis::ComputeLiveness() { - for (HLinearOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { + for (HLinearOrderIterator it(*this); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); block_infos_.Put( block->GetBlockId(), @@ -186,7 +164,7 @@ void SsaLivenessAnalysis::ComputeLiveness() { void SsaLivenessAnalysis::ComputeLiveRanges() { // Do a post order visit, adding inputs of instructions live in the block where // that instruction is defined, and killing instructions that are being visited. - for (HLinearPostOrderIterator it(linear_post_order_); !it.Done(); it.Advance()) { + for (HLinearPostOrderIterator it(*this); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); BitVector* kill = GetKillSet(*block); @@ -201,7 +179,7 @@ void SsaLivenessAnalysis::ComputeLiveRanges() { for (HInstructionIterator it(successor->GetPhis()); !it.Done(); it.Advance()) { HInstruction* phi = it.Current(); HInstruction* input = phi->InputAt(phi_input_index); - input->GetLiveInterval()->AddPhiUse(phi, block); + input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block); // A phi input whose last user is the phi dies at the end of the predecessor block, // and not at the phi's lifetime position. live_in->SetBit(input->GetSsaIndex()); @@ -228,7 +206,7 @@ void SsaLivenessAnalysis::ComputeLiveRanges() { HInstruction* input = current->InputAt(i); DCHECK(input->HasSsaIndex()); live_in->SetBit(input->GetSsaIndex()); - input->GetLiveInterval()->AddUse(current); + input->GetLiveInterval()->AddUse(current, i, false); } if (current->HasEnvironment()) { @@ -239,7 +217,7 @@ void SsaLivenessAnalysis::ComputeLiveRanges() { if (instruction != nullptr) { DCHECK(instruction->HasSsaIndex()); live_in->SetBit(instruction->GetSsaIndex()); - instruction->GetLiveInterval()->AddUse(current); + instruction->GetLiveInterval()->AddUse(current, i, true); } } } @@ -251,6 +229,10 @@ void SsaLivenessAnalysis::ComputeLiveRanges() { if (current->HasSsaIndex()) { kill->SetBit(current->GetSsaIndex()); live_in->ClearBit(current->GetSsaIndex()); + LiveInterval* interval = current->GetLiveInterval(); + DCHECK((interval->GetFirstRange() == nullptr) + || (interval->GetStart() == current->GetLifetimePosition())); + interval->SetFrom(current->GetLifetimePosition()); } } diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index 733535e..7903ad6 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -21,6 +21,8 @@ namespace art { +class CodeGenerator; + class BlockInfo : public ArenaObject { public: BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values) @@ -87,9 +89,17 @@ class LiveRange : public ArenaObject { */ 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()); + UsePosition(HInstruction* user, + size_t input_index, + bool is_environment, + size_t position, + UsePosition* next) + : user_(user), + input_index_(input_index), + is_environment_(is_environment), + position_(position), + next_(next) { + DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition() + 1); DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition()); } @@ -99,12 +109,18 @@ class UsePosition : public ArenaObject { HInstruction* GetUser() const { return user_; } + bool GetIsEnvironment() const { return is_environment_; } + + size_t GetInputIndex() const { return input_index_; } + void Dump(std::ostream& stream) const { stream << position_; } private: HInstruction* const user_; + const size_t input_index_; + const bool is_environment_; const size_t position_; UsePosition* const next_; @@ -117,17 +133,33 @@ class UsePosition : public ArenaObject { */ class LiveInterval : public ArenaObject { public: - LiveInterval(ArenaAllocator* allocator, Primitive::Type type) + LiveInterval(ArenaAllocator* allocator, Primitive::Type type, HInstruction* defined_by = nullptr) : allocator_(allocator), first_range_(nullptr), last_range_(nullptr), first_use_(nullptr), type_(type), next_sibling_(nullptr), - register_(kNoRegister) {} + parent_(this), + register_(kNoRegister), + spill_slot_(kNoSpillSlot), + is_fixed_(false), + defined_by_(defined_by) {} + + static LiveInterval* MakeFixedInterval(ArenaAllocator* allocator, int reg, Primitive::Type type) { + LiveInterval* interval = new (allocator) LiveInterval(allocator, type); + interval->SetRegister(reg); + interval->is_fixed_ = true; + return interval; + } - void AddUse(HInstruction* instruction) { - size_t position = instruction->GetLifetimePosition(); + bool IsFixed() const { return is_fixed_; } + + void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) { + // Set the use within the instruction. + // TODO: Use the instruction's location to know whether the instruction can die + // at entry, or needs to say alive within the user. + size_t position = instruction->GetLifetimePosition() + 1; size_t start_block_position = instruction->GetBlock()->GetLifetimeStart(); size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd(); if (first_range_ == nullptr) { @@ -143,12 +175,14 @@ class LiveInterval : public ArenaObject { // There is a hole in the interval. Create a new range. first_range_ = new (allocator_) LiveRange(start_block_position, position, first_range_); } - first_use_ = new (allocator_) UsePosition(instruction, position, first_use_); + first_use_ = new (allocator_) UsePosition( + instruction, input_index, is_environment, position, first_use_); } - void AddPhiUse(HInstruction* instruction, HBasicBlock* block) { + void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) { DCHECK(instruction->AsPhi() != nullptr); - first_use_ = new (allocator_) UsePosition(instruction, block->GetLifetimeEnd(), first_use_); + first_use_ = new (allocator_) UsePosition( + instruction, input_index, false, block->GetLifetimeEnd(), first_use_); } void AddRange(size_t start, size_t end) { @@ -178,11 +212,23 @@ class LiveInterval : public ArenaObject { } } + bool HasSpillSlot() const { return spill_slot_ != kNoSpillSlot; } + void SetSpillSlot(int slot) { spill_slot_ = slot; } + int GetSpillSlot() const { return spill_slot_; } + void SetFrom(size_t from) { - DCHECK(first_range_ != nullptr); - first_range_->start_ = from; + if (first_range_ != nullptr) { + first_range_->start_ = from; + } else { + // Instruction without uses. + DCHECK(!defined_by_->HasUses()); + DCHECK(from == defined_by_->GetLifetimePosition()); + first_range_ = last_range_ = new (allocator_) LiveRange(from, from + 2, nullptr); + } } + LiveInterval* GetParent() const { return parent_; } + LiveRange* GetFirstRange() const { return first_range_; } int GetRegister() const { return register_; } @@ -190,11 +236,11 @@ class LiveInterval : public ArenaObject { void ClearRegister() { register_ = kNoRegister; } bool HasRegister() const { return register_ != kNoRegister; } - bool IsDeadAt(size_t position) { + bool IsDeadAt(size_t position) const { return last_range_->GetEnd() <= position; } - bool Covers(size_t position) { + bool Covers(size_t position) const { LiveRange* current = first_range_; while (current != nullptr) { if (position >= current->GetStart() && position < current->GetEnd()) { @@ -208,27 +254,10 @@ class LiveInterval : public ArenaObject { /** * 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; - } - + size_t FirstIntersectionWith(LiveInterval* other) const { // Advance both intervals and find the first matching range start in // this interval. + LiveRange* my_range = first_range_; LiveRange* other_range = other->first_range_; do { if (my_range->IntersectsWith(*other_range)) { @@ -252,16 +281,33 @@ class LiveInterval : public ArenaObject { return first_range_->GetStart(); } + size_t GetEnd() const { + return last_range_->GetEnd(); + } + size_t FirstRegisterUseAfter(size_t position) const { + if (position == GetStart() && defined_by_ != nullptr) { + Location location = defined_by_->GetLocations()->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 + && defined_by_->GetLocations()->InAt(0).GetPolicy() == Location::kRequiresRegister)) { + return position; + } + } + } + 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; + if (use_position >= position && !use->GetIsEnvironment()) { + Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex()); + if (location.IsUnallocated() && location.GetPolicy() == Location::kRequiresRegister) { + return use_position; + } } use = use->GetNext(); } @@ -272,10 +318,18 @@ class LiveInterval : public ArenaObject { return FirstRegisterUseAfter(GetStart()); } + UsePosition* GetFirstUse() const { + return first_use_; + } + Primitive::Type GetType() const { return type_; } + HInstruction* GetDefinedBy() const { + return defined_by_; + } + /** * Split this interval at `position`. This interval is changed to: * [start ... position). @@ -284,7 +338,7 @@ class LiveInterval : public ArenaObject { * [position ... end) */ LiveInterval* SplitAt(size_t position) { - DCHECK(next_sibling_ == nullptr); + DCHECK(!is_fixed_); DCHECK_GT(position, GetStart()); if (last_range_->GetEnd() <= position) { @@ -293,7 +347,9 @@ class LiveInterval : public ArenaObject { } LiveInterval* new_interval = new (allocator_) LiveInterval(allocator_, type_); + new_interval->next_sibling_ = next_sibling_; next_sibling_ = new_interval; + new_interval->parent_ = parent_; new_interval->first_use_ = first_use_; LiveRange* current = first_range_; @@ -383,21 +439,36 @@ class LiveInterval : public ArenaObject { // Live interval that is the result of a split. LiveInterval* next_sibling_; + // The first interval from which split intervals come from. + LiveInterval* parent_; + // The register allocated to this interval. int register_; + // The spill slot allocated to this interval. + int spill_slot_; + + // Whether the interval is for a fixed register. + bool is_fixed_; + + // The instruction represented by this interval. + HInstruction* const defined_by_; + static constexpr int kNoRegister = -1; + static constexpr int kNoSpillSlot = -1; DISALLOW_COPY_AND_ASSIGN(LiveInterval); }; class SsaLivenessAnalysis : public ValueObject { public: - explicit SsaLivenessAnalysis(const HGraph& graph) + SsaLivenessAnalysis(const HGraph& graph, CodeGenerator* codegen) : graph_(graph), + codegen_(codegen), linear_post_order_(graph.GetArena(), graph.GetBlocks().Size()), block_infos_(graph.GetArena(), graph.GetBlocks().Size()), instructions_from_ssa_index_(graph.GetArena(), 0), + instructions_from_lifetime_position_(graph.GetArena(), 0), number_of_ssa_values_(0) { block_infos_.SetSize(graph.GetBlocks().Size()); } @@ -424,6 +495,14 @@ class SsaLivenessAnalysis : public ValueObject { return instructions_from_ssa_index_.Get(index); } + HInstruction* GetInstructionFromPosition(size_t index) const { + return instructions_from_lifetime_position_.Get(index); + } + + size_t GetMaxLifetimePosition() const { + return instructions_from_lifetime_position_.Size() * 2 - 1; + } + size_t GetNumberOfSsaValues() const { return number_of_ssa_values_; } @@ -458,14 +537,52 @@ class SsaLivenessAnalysis : public ValueObject { bool UpdateLiveOut(const HBasicBlock& block); const HGraph& graph_; + CodeGenerator* const codegen_; GrowableArray<HBasicBlock*> linear_post_order_; GrowableArray<BlockInfo*> block_infos_; + + // Temporary array used when computing live_in, live_out, and kill sets. GrowableArray<HInstruction*> instructions_from_ssa_index_; + + // Temporary array used when inserting moves in the graph. + GrowableArray<HInstruction*> instructions_from_lifetime_position_; size_t number_of_ssa_values_; DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis); }; +class HLinearOrderIterator : public ValueObject { + public: + explicit HLinearOrderIterator(const SsaLivenessAnalysis& liveness) + : post_order_(liveness.GetLinearPostOrder()), index_(liveness.GetLinearPostOrder().Size()) {} + + bool Done() const { return index_ == 0; } + HBasicBlock* Current() const { return post_order_.Get(index_ -1); } + void Advance() { --index_; DCHECK_GE(index_, 0U); } + + private: + const GrowableArray<HBasicBlock*>& post_order_; + size_t index_; + + DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator); +}; + +class HLinearPostOrderIterator : public ValueObject { + public: + explicit HLinearPostOrderIterator(const SsaLivenessAnalysis& liveness) + : post_order_(liveness.GetLinearPostOrder()), index_(0) {} + + bool Done() const { return index_ == post_order_.Size(); } + HBasicBlock* Current() const { return post_order_.Get(index_); } + void Advance() { ++index_; } + + private: + const GrowableArray<HBasicBlock*>& post_order_; + size_t index_; + + DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator); +}; + } // namespace art #endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ |