Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(31)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: test/unittests/compiler/register-allocator-unittest.cc

Issue 750813004: [turbofan] add initial move optimizer (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: rebase Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « test/unittests/compiler/move-optimizer-unittest.cc ('k') | test/unittests/unittests.gyp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: test/unittests/compiler/register-allocator-unittest.cc
diff --git a/test/unittests/compiler/register-allocator-unittest.cc b/test/unittests/compiler/register-allocator-unittest.cc
index d4dd49fa3f712c21d90a9bdbb972abf077c8d292..038a016ffde8ec102cf2c97e275d98881448e1f0 100644
--- a/test/unittests/compiler/register-allocator-unittest.cc
+++ b/test/unittests/compiler/register-allocator-unittest.cc
@@ -2,516 +2,19 @@
// 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/instruction.h"
#include "src/compiler/pipeline.h"
-#include "test/unittests/test-utils.h"
-#include "testing/gmock/include/gmock/gmock.h"
+#include "test/unittests/compiler/instruction-sequence-unittest.h"
namespace v8 {
namespace internal {
namespace compiler {
-typedef BasicBlock::RpoNumber Rpo;
-
-static const char*
- general_register_names_[RegisterConfiguration::kMaxGeneralRegisters];
-static const char*
- double_register_names_[RegisterConfiguration::kMaxDoubleRegisters];
-static char register_names_[10 * (RegisterConfiguration::kMaxGeneralRegisters +
- RegisterConfiguration::kMaxDoubleRegisters)];
-
-static void InitializeRegisterNames() {
- char* loc = register_names_;
- for (int i = 0; i < RegisterConfiguration::kMaxGeneralRegisters; ++i) {
- general_register_names_[i] = loc;
- loc += base::OS::SNPrintF(loc, 100, "gp_%d", i);
- *loc++ = 0;
- }
- for (int i = 0; i < RegisterConfiguration::kMaxDoubleRegisters; ++i) {
- double_register_names_[i] = loc;
- loc += base::OS::SNPrintF(loc, 100, "fp_%d", i) + 1;
- *loc++ = 0;
- }
-}
-
-
-class RegisterAllocatorTest : public TestWithZone {
+class RegisterAllocatorTest : public InstructionSequenceTest {
public:
- static const int kDefaultNRegs = 4;
- static const int kNoValue = kMinInt;
-
- struct VReg {
- VReg() : value_(kNoValue) {}
- VReg(PhiInstruction* phi) : value_(phi->virtual_register()) {} // NOLINT
- explicit VReg(int value) : value_(value) {}
- int value_;
- };
-
- enum TestOperandType {
- kInvalid,
- kSameAsFirst,
- kRegister,
- kFixedRegister,
- kSlot,
- kFixedSlot,
- kImmediate,
- kNone
- };
-
- struct TestOperand {
- TestOperand() : type_(kInvalid), vreg_(), value_(kNoValue) {}
- TestOperand(TestOperandType type, int imm)
- : type_(type), vreg_(), value_(imm) {}
- TestOperand(TestOperandType type, VReg vreg, int value = kNoValue)
- : type_(type), vreg_(vreg), value_(value) {}
-
- TestOperandType type_;
- VReg vreg_;
- int value_;
- };
-
- static TestOperand Same() { return TestOperand(kSameAsFirst, VReg()); }
-
- static TestOperand Reg(VReg vreg, int index = kNoValue) {
- TestOperandType type = kRegister;
- if (index != kNoValue) type = kFixedRegister;
- return TestOperand(type, vreg, index);
- }
-
- static TestOperand Reg(int index = kNoValue) { return Reg(VReg(), index); }
-
- static TestOperand Slot(VReg vreg, int index = kNoValue) {
- TestOperandType type = kSlot;
- if (index != kNoValue) type = kFixedSlot;
- return TestOperand(type, vreg, index);
- }
-
- static TestOperand Slot(int index = kNoValue) { return Slot(VReg(), index); }
-
- static TestOperand Use(VReg vreg) { return TestOperand(kNone, vreg); }
-
- static TestOperand Use() { return Use(VReg()); }
-
- enum BlockCompletionType { kBlockEnd, kFallThrough, kBranch, kJump };
-
- struct BlockCompletion {
- BlockCompletionType type_;
- TestOperand op_;
- int offset_0_;
- int offset_1_;
- };
-
- static BlockCompletion FallThrough() {
- BlockCompletion completion = {kFallThrough, TestOperand(), 1, kNoValue};
- return completion;
- }
-
- static BlockCompletion Jump(int offset) {
- BlockCompletion completion = {kJump, TestOperand(), offset, kNoValue};
- return completion;
- }
-
- static BlockCompletion Branch(TestOperand op, int left_offset,
- int right_offset) {
- BlockCompletion completion = {kBranch, op, left_offset, right_offset};
- return completion;
- }
-
- static BlockCompletion Last() {
- BlockCompletion completion = {kBlockEnd, TestOperand(), kNoValue, kNoValue};
- return completion;
- }
-
- RegisterAllocatorTest()
- : frame_(nullptr),
- sequence_(nullptr),
- num_general_registers_(kDefaultNRegs),
- num_double_registers_(kDefaultNRegs),
- instruction_blocks_(zone()),
- current_instruction_index_(-1),
- current_block_(nullptr),
- block_returns_(false) {
- InitializeRegisterNames();
- }
-
- void SetNumRegs(int num_general_registers, int num_double_registers) {
- CHECK(config_.is_empty());
- CHECK(instructions_.empty());
- CHECK(instruction_blocks_.empty());
- num_general_registers_ = num_general_registers;
- num_double_registers_ = num_double_registers;
- }
-
- RegisterConfiguration* config() {
- if (config_.is_empty()) {
- config_.Reset(new RegisterConfiguration(
- num_general_registers_, num_double_registers_, num_double_registers_,
- general_register_names_, double_register_names_));
- }
- return config_.get();
- }
-
- Frame* frame() {
- if (frame_ == nullptr) {
- frame_ = new (zone()) Frame();
- }
- return frame_;
- }
-
- InstructionSequence* sequence() {
- if (sequence_ == nullptr) {
- sequence_ =
- new (zone()) InstructionSequence(zone(), &instruction_blocks_);
- }
- return sequence_;
- }
-
- void StartLoop(int loop_blocks) {
- CHECK(current_block_ == nullptr);
- if (!loop_blocks_.empty()) {
- CHECK(!loop_blocks_.back().loop_header_.IsValid());
- }
- LoopData loop_data = {Rpo::Invalid(), loop_blocks};
- loop_blocks_.push_back(loop_data);
- }
-
- void EndLoop() {
- CHECK(current_block_ == nullptr);
- CHECK(!loop_blocks_.empty());
- CHECK_EQ(0, loop_blocks_.back().expected_blocks_);
- loop_blocks_.pop_back();
- }
-
- void StartBlock() {
- block_returns_ = false;
- NewBlock();
- }
-
- int EndBlock(BlockCompletion completion = FallThrough()) {
- int instruction_index = kMinInt;
- if (block_returns_) {
- CHECK(completion.type_ == kBlockEnd || completion.type_ == kFallThrough);
- completion.type_ = kBlockEnd;
- }
- switch (completion.type_) {
- case kBlockEnd:
- break;
- case kFallThrough:
- instruction_index = EmitFallThrough();
- break;
- case kJump:
- CHECK(!block_returns_);
- instruction_index = EmitJump();
- break;
- case kBranch:
- CHECK(!block_returns_);
- instruction_index = EmitBranch(completion.op_);
- break;
- }
- completions_.push_back(completion);
- CHECK(current_block_ != nullptr);
- sequence()->EndBlock(current_block_->rpo_number());
- current_block_ = nullptr;
- return instruction_index;
- }
-
void Allocate() {
- CHECK_EQ(nullptr, current_block_);
WireBlocks();
Pipeline::AllocateRegistersForTesting(config(), sequence(), true);
}
-
- TestOperand Imm(int32_t imm = 0) {
- int index = sequence()->AddImmediate(Constant(imm));
- return TestOperand(kImmediate, index);
- }
-
- VReg Parameter(TestOperand output_op = Reg()) {
- VReg vreg = NewReg();
- InstructionOperand* outputs[1]{ConvertOutputOp(vreg, output_op)};
- Emit(vreg.value_, kArchNop, 1, outputs);
- return vreg;
- }
-
- int Return(TestOperand input_op_0) {
- block_returns_ = true;
- InstructionOperand* inputs[1]{ConvertInputOp(input_op_0)};
- return Emit(NewIndex(), kArchRet, 0, nullptr, 1, inputs);
- }
-
- int Return(VReg vreg) { return Return(Reg(vreg, 0)); }
-
- PhiInstruction* Phi(VReg incoming_vreg) {
- PhiInstruction* phi =
- new (zone()) PhiInstruction(zone(), NewReg().value_, 10);
- phi->Extend(zone(), incoming_vreg.value_);
- current_block_->AddPhi(phi);
- return phi;
- }
-
- PhiInstruction* Phi(VReg incoming_vreg_0, VReg incoming_vreg_1) {
- auto phi = Phi(incoming_vreg_0);
- Extend(phi, incoming_vreg_1);
- return phi;
- }
-
- void Extend(PhiInstruction* phi, VReg vreg) {
- phi->Extend(zone(), vreg.value_);
- }
-
- VReg DefineConstant(int32_t imm = 0) {
- VReg vreg = NewReg();
- sequence()->AddConstant(vreg.value_, Constant(imm));
- InstructionOperand* outputs[1]{
- ConstantOperand::Create(vreg.value_, zone())};
- Emit(vreg.value_, kArchNop, 1, outputs);
- return vreg;
- }
-
- VReg EmitOII(TestOperand output_op, TestOperand input_op_0,
- TestOperand input_op_1) {
- VReg output_vreg = NewReg();
- InstructionOperand* outputs[1]{ConvertOutputOp(output_vreg, output_op)};
- InstructionOperand* inputs[2]{ConvertInputOp(input_op_0),
- ConvertInputOp(input_op_1)};
- Emit(output_vreg.value_, kArchNop, 1, outputs, 2, inputs);
- return output_vreg;
- }
-
- VReg EmitCall(TestOperand output_op, size_t input_size, TestOperand* inputs) {
- VReg output_vreg = NewReg();
- InstructionOperand* outputs[1]{ConvertOutputOp(output_vreg, output_op)};
- InstructionOperand** mapped_inputs =
- zone()->NewArray<InstructionOperand*>(static_cast<int>(input_size));
- for (size_t i = 0; i < input_size; ++i) {
- mapped_inputs[i] = ConvertInputOp(inputs[i]);
- }
- Emit(output_vreg.value_, kArchCallCodeObject, 1, outputs, input_size,
- mapped_inputs);
- return output_vreg;
- }
-
- // Get defining instruction vreg or value returned at instruction creation
- // time when there is no return value.
- const Instruction* GetInstruction(int instruction_index) {
- auto it = instructions_.find(instruction_index);
- CHECK(it != instructions_.end());
- return it->second;
- }
-
- private:
- VReg NewReg() { return VReg(sequence()->NextVirtualRegister()); }
- int NewIndex() { return current_instruction_index_--; }
-
- static TestOperand Invalid() { return TestOperand(kInvalid, VReg()); }
-
- int EmitBranch(TestOperand input_op) {
- InstructionOperand* inputs[4]{ConvertInputOp(input_op),
- ConvertInputOp(Imm()), ConvertInputOp(Imm()),
- ConvertInputOp(Imm())};
- InstructionCode opcode = kArchJmp | FlagsModeField::encode(kFlags_branch) |
- FlagsConditionField::encode(kEqual);
- auto instruction =
- NewInstruction(opcode, 0, nullptr, 4, inputs)->MarkAsControl();
- return AddInstruction(NewIndex(), instruction);
- }
-
- int EmitFallThrough() {
- auto instruction = NewInstruction(kArchNop, 0, nullptr)->MarkAsControl();
- return AddInstruction(NewIndex(), instruction);
- }
-
- int EmitJump() {
- InstructionOperand* inputs[1]{ConvertInputOp(Imm())};
- auto instruction =
- NewInstruction(kArchJmp, 0, nullptr, 1, inputs)->MarkAsControl();
- return AddInstruction(NewIndex(), instruction);
- }
-
- Instruction* NewInstruction(InstructionCode code, size_t outputs_size,
- InstructionOperand** outputs,
- size_t inputs_size = 0,
- InstructionOperand* *inputs = nullptr,
- size_t temps_size = 0,
- InstructionOperand* *temps = nullptr) {
- CHECK_NE(nullptr, current_block_);
- return Instruction::New(zone(), code, outputs_size, outputs, inputs_size,
- inputs, temps_size, temps);
- }
-
- InstructionOperand* Unallocated(TestOperand op,
- UnallocatedOperand::ExtendedPolicy policy) {
- auto unallocated = new (zone()) UnallocatedOperand(policy);
- unallocated->set_virtual_register(op.vreg_.value_);
- return unallocated;
- }
-
- InstructionOperand* Unallocated(TestOperand op,
- UnallocatedOperand::ExtendedPolicy policy,
- UnallocatedOperand::Lifetime lifetime) {
- auto unallocated = new (zone()) UnallocatedOperand(policy, lifetime);
- unallocated->set_virtual_register(op.vreg_.value_);
- return unallocated;
- }
-
- InstructionOperand* Unallocated(TestOperand op,
- UnallocatedOperand::ExtendedPolicy policy,
- int index) {
- auto unallocated = new (zone()) UnallocatedOperand(policy, index);
- unallocated->set_virtual_register(op.vreg_.value_);
- return unallocated;
- }
-
- InstructionOperand* Unallocated(TestOperand op,
- UnallocatedOperand::BasicPolicy policy,
- int index) {
- auto unallocated = new (zone()) UnallocatedOperand(policy, index);
- unallocated->set_virtual_register(op.vreg_.value_);
- return unallocated;
- }
-
- InstructionOperand* ConvertInputOp(TestOperand op) {
- if (op.type_ == kImmediate) {
- CHECK_EQ(op.vreg_.value_, kNoValue);
- return ImmediateOperand::Create(op.value_, zone());
- }
- CHECK_NE(op.vreg_.value_, kNoValue);
- switch (op.type_) {
- case kNone:
- return Unallocated(op, UnallocatedOperand::NONE,
- UnallocatedOperand::USED_AT_START);
- case kRegister:
- return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER,
- UnallocatedOperand::USED_AT_START);
- case kFixedRegister:
- CHECK(0 <= op.value_ && op.value_ < num_general_registers_);
- return Unallocated(op, UnallocatedOperand::FIXED_REGISTER, op.value_);
- default:
- break;
- }
- CHECK(false);
- return NULL;
- }
-
- InstructionOperand* ConvertOutputOp(VReg vreg, TestOperand op) {
- CHECK_EQ(op.vreg_.value_, kNoValue);
- op.vreg_ = vreg;
- switch (op.type_) {
- case kSameAsFirst:
- return Unallocated(op, UnallocatedOperand::SAME_AS_FIRST_INPUT);
- case kRegister:
- return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER);
- case kFixedSlot:
- return Unallocated(op, UnallocatedOperand::FIXED_SLOT, op.value_);
- case kFixedRegister:
- CHECK(0 <= op.value_ && op.value_ < num_general_registers_);
- return Unallocated(op, UnallocatedOperand::FIXED_REGISTER, op.value_);
- default:
- break;
- }
- CHECK(false);
- return NULL;
- }
-
- InstructionBlock* NewBlock() {
- CHECK(current_block_ == nullptr);
- auto block_id = BasicBlock::Id::FromSize(instruction_blocks_.size());
- Rpo rpo = Rpo::FromInt(block_id.ToInt());
- Rpo loop_header = Rpo::Invalid();
- Rpo loop_end = Rpo::Invalid();
- if (!loop_blocks_.empty()) {
- auto& loop_data = loop_blocks_.back();
- // This is a loop header.
- if (!loop_data.loop_header_.IsValid()) {
- loop_end = Rpo::FromInt(block_id.ToInt() + loop_data.expected_blocks_);
- loop_data.expected_blocks_--;
- loop_data.loop_header_ = rpo;
- } else {
- // This is a loop body.
- CHECK_NE(0, loop_data.expected_blocks_);
- // TODO(dcarney): handle nested loops.
- loop_data.expected_blocks_--;
- loop_header = loop_data.loop_header_;
- }
- }
- // Construct instruction block.
- auto instruction_block = new (zone()) InstructionBlock(
- zone(), block_id, rpo, rpo, loop_header, loop_end, false);
- instruction_blocks_.push_back(instruction_block);
- current_block_ = instruction_block;
- sequence()->StartBlock(rpo);
- return instruction_block;
- }
-
- void WireBlocks() {
- CHECK(instruction_blocks_.size() == completions_.size());
- size_t offset = 0;
- for (const auto& completion : completions_) {
- switch (completion.type_) {
- case kBlockEnd:
- break;
- case kFallThrough: // Fallthrough.
- case kJump:
- WireBlock(offset, completion.offset_0_);
- break;
- case kBranch:
- WireBlock(offset, completion.offset_0_);
- WireBlock(offset, completion.offset_1_);
- break;
- }
- ++offset;
- }
- }
-
- void WireBlock(size_t block_offset, int jump_offset) {
- size_t target_block_offset =
- block_offset + static_cast<size_t>(jump_offset);
- CHECK(block_offset < instruction_blocks_.size());
- CHECK(target_block_offset < instruction_blocks_.size());
- auto block = instruction_blocks_[block_offset];
- auto target = instruction_blocks_[target_block_offset];
- block->successors().push_back(target->rpo_number());
- target->predecessors().push_back(block->rpo_number());
- }
-
- int Emit(int instruction_index, InstructionCode code, size_t outputs_size,
- InstructionOperand** outputs, size_t inputs_size = 0,
- InstructionOperand* *inputs = nullptr, size_t temps_size = 0,
- InstructionOperand* *temps = nullptr) {
- auto instruction = NewInstruction(code, outputs_size, outputs, inputs_size,
- inputs, temps_size, temps);
- return AddInstruction(instruction_index, instruction);
- }
-
- int AddInstruction(int instruction_index, Instruction* instruction) {
- sequence()->AddInstruction(instruction);
- return instruction_index;
- }
-
- struct LoopData {
- Rpo loop_header_;
- int expected_blocks_;
- };
-
- typedef std::vector<LoopData> LoopBlocks;
- typedef std::map<int, const Instruction*> Instructions;
- typedef std::vector<BlockCompletion> Completions;
-
- SmartPointer<RegisterConfiguration> config_;
- Frame* frame_;
- InstructionSequence* sequence_;
- int num_general_registers_;
- int num_double_registers_;
-
- // Block building state.
- InstructionBlocks instruction_blocks_;
- Instructions instructions_;
- int current_instruction_index_;
- Completions completions_;
- LoopBlocks loop_blocks_;
- InstructionBlock* current_block_;
- bool block_returns_;
};
@@ -635,7 +138,7 @@ TEST_F(RegisterAllocatorTest, DiamondManyPhis) {
for (int i = 0; i < kPhis; ++i) {
merged[i] = Use(Phi(t_vals[i], f_vals[i]));
}
- Return(EmitCall(Reg(), kPhis, merged));
+ Return(EmitCall(Slot(-1), kPhis, merged));
EndBlock();
Allocate();
@@ -674,7 +177,7 @@ TEST_F(RegisterAllocatorTest, DoubleDiamondManyRedundantPhis) {
for (int i = 0; i < kPhis; ++i) {
merged[i] = Use(Phi(vals[i], vals[i]));
}
- Return(EmitCall(Reg(), kPhis, merged));
+ Return(EmitCall(Reg(0), kPhis, merged));
EndBlock();
Allocate();
@@ -729,6 +232,48 @@ TEST_F(RegisterAllocatorTest, RegressionPhisNeedTooManyRegisters) {
Allocate();
}
+
+TEST_F(RegisterAllocatorTest, SpillPhi) {
+ StartBlock();
+ EndBlock(Branch(Imm(), 1, 2));
+
+ StartBlock();
+ auto left = Define(Reg(0));
+ EndBlock(Jump(2));
+
+ StartBlock();
+ auto right = Define(Reg(0));
+ EndBlock();
+
+ StartBlock();
+ auto phi = Phi(left, right);
+ EmitCall(Slot(-1));
+ Return(Reg(phi));
+ EndBlock();
+
+ Allocate();
+}
+
+
+TEST_F(RegisterAllocatorTest, MoveLotsOfConstants) {
+ StartBlock();
+ VReg constants[kDefaultNRegs];
+ for (size_t i = 0; i < arraysize(constants); ++i) {
+ constants[i] = DefineConstant();
+ }
+ TestOperand call_ops[kDefaultNRegs * 2];
+ for (int i = 0; i < kDefaultNRegs; ++i) {
+ call_ops[i] = Reg(constants[i], i);
+ }
+ for (int i = 0; i < kDefaultNRegs; ++i) {
+ call_ops[i + kDefaultNRegs] = Slot(constants[i], i);
+ }
+ EmitCall(Slot(-1), arraysize(call_ops), call_ops);
+ EndBlock(Last());
+
+ Allocate();
+}
+
} // namespace compiler
} // namespace internal
} // namespace v8
« no previous file with comments | « test/unittests/compiler/move-optimizer-unittest.cc ('k') | test/unittests/unittests.gyp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698