From 0d1cdebad2d011ce5057adb9d52ce60002dbb694 Mon Sep 17 00:00:00 2001 From: "dcarney@chromium.org" Date: Mon, 3 Nov 2014 13:26:46 +0000 Subject: [PATCH] [turbofan] initial framework for unittesting of register allocator BUG= R=bmeurer@chromium.org Review URL: https://codereview.chromium.org/683133005 Cr-Commit-Position: refs/heads/master@{#25071} git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@25071 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/compiler/instruction.cc | 22 +- src/compiler/instruction.h | 29 +-- src/compiler/pipeline.cc | 5 +- src/compiler/register-allocator.h | 2 +- test/cctest/compiler/test-codegen-deopt.cc | 5 +- test/cctest/compiler/test-instruction.cc | 4 +- .../compiler/instruction-selector-unittest.cc | 4 +- .../compiler/register-allocator-unittest.cc | 196 ++++++++++++++++++ test/unittests/unittests.gyp | 1 + 9 files changed, 240 insertions(+), 28 deletions(-) create mode 100644 test/unittests/compiler/register-allocator-unittest.cc diff --git a/src/compiler/instruction.cc b/src/compiler/instruction.cc index 7ee5a6961..9705bea20 100644 --- a/src/compiler/instruction.cc +++ b/src/compiler/instruction.cc @@ -373,9 +373,11 @@ size_t InstructionBlock::PredecessorIndexOf( } -static void InitializeInstructionBlocks(Zone* zone, const Schedule* schedule, - InstructionBlocks* blocks) { - DCHECK(blocks->size() == schedule->rpo_order()->size()); +InstructionBlocks* InstructionSequence::InstructionBlocksFor( + Zone* zone, const Schedule* schedule) { + InstructionBlocks* blocks = zone->NewArray(1); + new (blocks) InstructionBlocks( + static_cast(schedule->rpo_order()->size()), NULL, zone); size_t rpo_number = 0; for (BasicBlockVector::const_iterator it = schedule->rpo_order()->begin(); it != schedule->rpo_order()->end(); ++it, ++rpo_number) { @@ -383,14 +385,14 @@ static void InitializeInstructionBlocks(Zone* zone, const Schedule* schedule, DCHECK((*it)->GetRpoNumber().ToSize() == rpo_number); (*blocks)[rpo_number] = new (zone) InstructionBlock(zone, *it); } + return blocks; } InstructionSequence::InstructionSequence(Zone* instruction_zone, - const Schedule* schedule) + InstructionBlocks* instruction_blocks) : zone_(instruction_zone), - instruction_blocks_(static_cast(schedule->rpo_order()->size()), NULL, - zone()), + instruction_blocks_(instruction_blocks), constants_(ConstantMap::key_compare(), ConstantMap::allocator_type(zone())), immediates_(zone()), @@ -399,9 +401,7 @@ InstructionSequence::InstructionSequence(Zone* instruction_zone, pointer_maps_(zone()), doubles_(std::less(), VirtualRegisterSet::allocator_type(zone())), references_(std::less(), VirtualRegisterSet::allocator_type(zone())), - deoptimization_entries_(zone()) { - InitializeInstructionBlocks(zone(), schedule, &instruction_blocks_); -} + deoptimization_entries_(zone()) {} Label* InstructionSequence::GetLabel(BasicBlock::RpoNumber rpo) { @@ -461,8 +461,8 @@ const InstructionBlock* InstructionSequence::GetInstructionBlock( DCHECK_LE(0, instruction_index); Instruction* instruction = InstructionAt(instruction_index--); if (instruction->IsBlockStart()) { - return instruction_blocks_ - [BlockStartInstruction::cast(instruction)->rpo_number().ToSize()]; + return instruction_blocks_->at( + BlockStartInstruction::cast(instruction)->rpo_number().ToSize()); } } } diff --git a/src/compiler/instruction.h b/src/compiler/instruction.h index 75c3e9e34..4f6649ff7 100644 --- a/src/compiler/instruction.h +++ b/src/compiler/instruction.h @@ -809,11 +809,13 @@ class InstructionBlock FINAL : public ZoneObject { inline bool IsLoopHeader() const { return loop_end_.IsValid(); } typedef ZoneVector Predecessors; + Predecessors& predecessors() { return predecessors_; } const Predecessors& predecessors() const { return predecessors_; } size_t PredecessorCount() const { return predecessors_.size(); } size_t PredecessorIndexOf(BasicBlock::RpoNumber rpo_number) const; typedef ZoneVector Successors; + Successors& successors() { return successors_; } const Successors& successors() const { return successors_; } size_t SuccessorCount() const { return successors_.size(); } @@ -825,12 +827,12 @@ class InstructionBlock FINAL : public ZoneObject { Successors successors_; Predecessors predecessors_; PhiInstructions phis_; - BasicBlock::Id id_; - BasicBlock::RpoNumber ao_number_; // Assembly order number. + const BasicBlock::Id id_; + const BasicBlock::RpoNumber ao_number_; // Assembly order number. // TODO(dcarney): probably dont't need this. - BasicBlock::RpoNumber rpo_number_; - BasicBlock::RpoNumber loop_header_; - BasicBlock::RpoNumber loop_end_; + const BasicBlock::RpoNumber rpo_number_; + const BasicBlock::RpoNumber loop_header_; + const BasicBlock::RpoNumber loop_end_; int32_t code_start_; // start index of arch-specific code. int32_t code_end_; // end index of arch-specific code. const bool deferred_; // Block contains deferred code. @@ -850,31 +852,34 @@ typedef ZoneVector InstructionBlocks; // TODO(titzer): s/IsDouble/IsFloat64/ class InstructionSequence FINAL { public: - InstructionSequence(Zone* zone, const Schedule* schedule); + static InstructionBlocks* InstructionBlocksFor(Zone* zone, + const Schedule* schedule); + + InstructionSequence(Zone* zone, InstructionBlocks* instruction_blocks); int NextVirtualRegister() { return next_virtual_register_++; } int VirtualRegisterCount() const { return next_virtual_register_; } const InstructionBlocks& instruction_blocks() const { - return instruction_blocks_; + return *instruction_blocks_; } int InstructionBlockCount() const { - return static_cast(instruction_blocks_.size()); + return static_cast(instruction_blocks_->size()); } InstructionBlock* InstructionBlockAt(BasicBlock::RpoNumber rpo_number) { - return instruction_blocks_[rpo_number.ToSize()]; + return instruction_blocks_->at(rpo_number.ToSize()); } int LastLoopInstructionIndex(const InstructionBlock* block) { - return instruction_blocks_[block->loop_end().ToSize() - 1] + return instruction_blocks_->at(block->loop_end().ToSize() - 1) ->last_instruction_index(); } const InstructionBlock* InstructionBlockAt( BasicBlock::RpoNumber rpo_number) const { - return instruction_blocks_[rpo_number.ToSize()]; + return instruction_blocks_->at(rpo_number.ToSize()); } const InstructionBlock* GetInstructionBlock(int instruction_index) const; @@ -961,7 +966,7 @@ class InstructionSequence FINAL { typedef std::set, ZoneIntAllocator> VirtualRegisterSet; Zone* const zone_; - InstructionBlocks instruction_blocks_; + InstructionBlocks* const instruction_blocks_; ConstantMap constants_; ConstantDeque immediates_; InstructionDeque instructions_; diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc index d1df84329..4dab24412 100644 --- a/src/compiler/pipeline.cc +++ b/src/compiler/pipeline.cc @@ -538,7 +538,10 @@ Handle Pipeline::GenerateCode(Linkage* linkage, PipelineData* data) { data->schedule()); } - InstructionSequence sequence(data->instruction_zone(), data->schedule()); + InstructionBlocks* instruction_blocks = + InstructionSequence::InstructionBlocksFor(data->instruction_zone(), + data->schedule()); + InstructionSequence sequence(data->instruction_zone(), instruction_blocks); // Select and schedule instructions covering the scheduled graph. { diff --git a/src/compiler/register-allocator.h b/src/compiler/register-allocator.h index 40fafb1dc..db30f96b4 100644 --- a/src/compiler/register-allocator.h +++ b/src/compiler/register-allocator.h @@ -317,7 +317,7 @@ class LiveRange FINAL : public ZoneObject { }; -class RegisterAllocator BASE_EMBEDDED { +class RegisterAllocator FINAL { public: class Config { public: diff --git a/test/cctest/compiler/test-codegen-deopt.cc b/test/cctest/compiler/test-codegen-deopt.cc index e299c3dc7..ac1d0efb6 100644 --- a/test/cctest/compiler/test-codegen-deopt.cc +++ b/test/cctest/compiler/test-codegen-deopt.cc @@ -65,8 +65,11 @@ class DeoptCodegenTester { // Initialize the codegen and generate code. Linkage* linkage = new (scope_->main_zone()) Linkage(info.zone(), &info); + InstructionBlocks* instruction_blocks = + InstructionSequence::InstructionBlocksFor(scope_->main_zone(), + schedule); code = new v8::internal::compiler::InstructionSequence(scope_->main_zone(), - schedule); + instruction_blocks); SourcePositionTable source_positions(graph); InstructionSelector selector(scope_->main_zone(), graph, linkage, code, schedule, &source_positions); diff --git a/test/cctest/compiler/test-instruction.cc b/test/cctest/compiler/test-instruction.cc index 2b41e40c6..2069c7f4f 100644 --- a/test/cctest/compiler/test-instruction.cc +++ b/test/cctest/compiler/test-instruction.cc @@ -55,7 +55,9 @@ class InstructionTester : public HandleAndZoneScope { Scheduler::ComputeSpecialRPO(&zone_pool, &schedule); DCHECK(schedule.rpo_order()->size() > 0); } - code = new TestInstrSeq(main_zone(), &schedule); + InstructionBlocks* instruction_blocks = + InstructionSequence::InstructionBlocksFor(main_zone(), &schedule); + code = new TestInstrSeq(main_zone(), instruction_blocks); } Node* Int32Constant(int32_t val) { diff --git a/test/unittests/compiler/instruction-selector-unittest.cc b/test/unittests/compiler/instruction-selector-unittest.cc index ba420f75a..57ce69083 100644 --- a/test/unittests/compiler/instruction-selector-unittest.cc +++ b/test/unittests/compiler/instruction-selector-unittest.cc @@ -37,7 +37,9 @@ InstructionSelectorTest::Stream InstructionSelectorTest::StreamBuilder::Build( EXPECT_NE(0, graph()->NodeCount()); int initial_node_count = graph()->NodeCount(); Linkage linkage(test_->zone(), call_descriptor()); - InstructionSequence sequence(test_->zone(), schedule); + InstructionBlocks* instruction_blocks = + InstructionSequence::InstructionBlocksFor(test_->zone(), schedule); + InstructionSequence sequence(test_->zone(), instruction_blocks); SourcePositionTable source_position_table(graph()); InstructionSelector selector(test_->zone(), graph(), &linkage, &sequence, schedule, &source_position_table, features); diff --git a/test/unittests/compiler/register-allocator-unittest.cc b/test/unittests/compiler/register-allocator-unittest.cc new file mode 100644 index 000000000..5c617083e --- /dev/null +++ b/test/unittests/compiler/register-allocator-unittest.cc @@ -0,0 +1,196 @@ +// Copyright 2014 the V8 project authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "src/base/utils/random-number-generator.h" +#include "src/compiler/register-allocator.h" +#include "test/unittests/test-utils.h" +#include "testing/gmock/include/gmock/gmock.h" + +namespace v8 { +namespace internal { +namespace compiler { + +typedef BasicBlock::RpoNumber Rpo; + +namespace { + +static const char* general_register_names_[kMaxGeneralRegisters]; +static const char* double_register_names_[kMaxDoubleRegisters]; +static char register_names_[10 * (kMaxGeneralRegisters + kMaxDoubleRegisters)]; + + +static const char* GeneralRegisterName(int allocation_index) { + return general_register_names_[allocation_index]; +} + + +static const char* DoubleRegisterName(int allocation_index) { + return double_register_names_[allocation_index]; +} + + +static void InitializeRegisterNames() { + char* loc = register_names_; + for (int i = 0; i < kMaxGeneralRegisters; ++i) { + general_register_names_[i] = loc; + loc += base::OS::SNPrintF(loc, 100, "gp_%d", i); + *loc++ = 0; + } + for (int i = 0; i < kMaxDoubleRegisters; ++i) { + double_register_names_[i] = loc; + loc += base::OS::SNPrintF(loc, 100, "fp_%d", i) + 1; + *loc++ = 0; + } +} + +} // namespace + + +// TODO(dcarney): fake opcodes. +// TODO(dcarney): fix printing of sequence w.r.t fake opcodes and registers. +class RegisterAllocatorTest : public TestWithZone { + public: + static const int kDefaultNRegs = 4; + + RegisterAllocatorTest() + : basic_blocks_(zone()), + instruction_blocks_(zone()), + current_block_(NULL) { + InitializeRegisterNames(); + config_.num_general_registers_ = kDefaultNRegs; + config_.num_double_registers_ = kDefaultNRegs; + config_.num_aliased_double_registers_ = kDefaultNRegs; + config_.GeneralRegisterName = GeneralRegisterName; + config_.DoubleRegisterName = DoubleRegisterName; + } + + Frame* frame() { + if (frame_.is_empty()) { + frame_.Reset(new Frame()); + } + return frame_.get(); + } + + InstructionSequence* sequence() { + if (sequence_.is_empty()) { + sequence_.Reset(new InstructionSequence(zone(), &instruction_blocks_)); + } + return sequence_.get(); + } + + RegisterAllocator* allocator() { + if (allocator_.is_empty()) { + allocator_.Reset( + new RegisterAllocator(config_, zone(), frame(), sequence())); + } + return allocator_.get(); + } + + InstructionBlock* StartBlock(Rpo loop_header = Rpo::Invalid(), + Rpo loop_end = Rpo::Invalid()) { + CHECK(current_block_ == NULL); + BasicBlock::Id block_id = + BasicBlock::Id::FromSize(instruction_blocks_.size()); + BasicBlock* basic_block = new (zone()) BasicBlock(zone(), block_id); + basic_block->set_rpo_number(block_id.ToInt()); + basic_block->set_ao_number(block_id.ToInt()); + if (loop_header.IsValid()) { + basic_block->set_loop_depth(1); + basic_block->set_loop_header(basic_blocks_[loop_header.ToSize()]); + basic_block->set_loop_end(loop_end.ToInt()); + } + InstructionBlock* instruction_block = + new (zone()) InstructionBlock(zone(), basic_block); + basic_blocks_.push_back(basic_block); + instruction_blocks_.push_back(instruction_block); + current_block_ = instruction_block; + sequence()->StartBlock(basic_block); + return instruction_block; + } + + void EndBlock() { + CHECK(current_block_ != NULL); + sequence()->EndBlock(basic_blocks_[current_block_->rpo_number().ToSize()]); + current_block_ = NULL; + } + + void Allocate() { + if (FLAG_trace_alloc) { + OFStream os(stdout); + os << "Before: " << std::endl << *sequence() << std::endl; + } + allocator()->Allocate(); + if (FLAG_trace_alloc) { + OFStream os(stdout); + os << "After: " << std::endl << *sequence() << std::endl; + } + } + + int NewReg() { return sequence()->NextVirtualRegister(); } + + int Parameter() { + // TODO(dcarney): assert parameters before other instructions. + int vreg = NewReg(); + InstructionOperand* outputs[1]{ + Unallocated(UnallocatedOperand::MUST_HAVE_REGISTER, vreg)}; + sequence()->AddInstruction( + Instruction::New(zone(), kArchNop, 1, outputs, 0, NULL, 0, NULL)); + return vreg; + } + + void Return(int vreg) { + InstructionOperand* inputs[1]{ + Unallocated(UnallocatedOperand::MUST_HAVE_REGISTER, vreg)}; + sequence()->AddInstruction( + Instruction::New(zone(), kArchNop, 0, NULL, 1, inputs, 0, NULL)); + } + + Instruction* Emit(int output_vreg, int input_vreg_0, int input_vreg_1) { + InstructionOperand* outputs[1]{ + Unallocated(UnallocatedOperand::MUST_HAVE_REGISTER, output_vreg)}; + InstructionOperand* inputs[2]{ + Unallocated(UnallocatedOperand::MUST_HAVE_REGISTER, input_vreg_0), + Unallocated(UnallocatedOperand::MUST_HAVE_REGISTER, input_vreg_1)}; + Instruction* instruction = + Instruction::New(zone(), kArchNop, 1, outputs, 2, inputs, 0, NULL); + sequence()->AddInstruction(instruction); + return instruction; + } + + private: + InstructionOperand* Unallocated(UnallocatedOperand::ExtendedPolicy policy, + int vreg) { + UnallocatedOperand* op = + new (zone()) UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER); + op->set_virtual_register(vreg); + return op; + } + + RegisterAllocator::Config config_; + ZoneVector basic_blocks_; + InstructionBlocks instruction_blocks_; + InstructionBlock* current_block_; + SmartPointer frame_; + SmartPointer allocator_; + SmartPointer sequence_; +}; + + +TEST_F(RegisterAllocatorTest, CanAllocateThreeRegisters) { + StartBlock(); + int a_reg = Parameter(); + int b_reg = Parameter(); + int c_reg = NewReg(); + Instruction* res = Emit(c_reg, a_reg, b_reg); + Return(c_reg); + EndBlock(); + + Allocate(); + + ASSERT_TRUE(res->OutputAt(0)->IsRegister()); +} + +} // namespace compiler +} // namespace internal +} // namespace v8 diff --git a/test/unittests/unittests.gyp b/test/unittests/unittests.gyp index 5253746f2..c8deca5b1 100644 --- a/test/unittests/unittests.gyp +++ b/test/unittests/unittests.gyp @@ -51,6 +51,7 @@ 'compiler/machine-operator-unittest.cc', 'compiler/node-test-utils.cc', 'compiler/node-test-utils.h', + 'compiler/register-allocator-unittest.cc', 'compiler/simplified-operator-reducer-unittest.cc', 'compiler/simplified-operator-unittest.cc', 'compiler/value-numbering-reducer-unittest.cc', -- 2.34.1