Revision: 25178
Author: [email protected]
Date: Thu Nov 6 08:28:15 2014 UTC
Log: [turbofan] extend register allocator testing with control flow
[email protected], [email protected]
BUG=
Review URL: https://codereview.chromium.org/699083003
https://code.google.com/p/v8/source/detail?r=25178
Modified:
/branches/bleeding_edge/src/compiler/instruction-selector.cc
/branches/bleeding_edge/src/compiler/instruction.cc
/branches/bleeding_edge/src/compiler/instruction.h
/branches/bleeding_edge/test/cctest/compiler/test-instruction.cc
/branches/bleeding_edge/test/unittests/compiler/register-allocator-unittest.cc
=======================================
--- /branches/bleeding_edge/src/compiler/instruction-selector.cc Wed Nov 5
09:02:51 2014 UTC
+++ /branches/bleeding_edge/src/compiler/instruction-selector.cc Thu Nov 6
08:28:15 2014 UTC
@@ -66,11 +66,11 @@
sequence()->InstructionBlockAt(block->GetRpoNumber());
size_t end = instruction_block->code_end();
size_t start = instruction_block->code_start();
- sequence()->StartBlock(block);
+ sequence()->StartBlock(block->GetRpoNumber());
while (start-- > end) {
sequence()->AddInstruction(instructions_[start]);
}
- sequence()->EndBlock(block);
+ sequence()->EndBlock(block->GetRpoNumber());
}
}
=======================================
--- /branches/bleeding_edge/src/compiler/instruction.cc Wed Nov 5 10:10:28
2014 UTC
+++ /branches/bleeding_edge/src/compiler/instruction.cc Thu Nov 6 08:28:15
2014 UTC
@@ -336,6 +336,36 @@
UNREACHABLE();
return os;
}
+
+
+InstructionBlock::InstructionBlock(Zone* zone, BasicBlock::Id id,
+ BasicBlock::RpoNumber ao_number,
+ BasicBlock::RpoNumber rpo_number,
+ BasicBlock::RpoNumber loop_header,
+ BasicBlock::RpoNumber loop_end,
+ bool deferred)
+ : successors_(zone),
+ predecessors_(zone),
+ phis_(zone),
+ id_(id),
+ ao_number_(ao_number),
+ rpo_number_(rpo_number),
+ loop_header_(loop_header),
+ loop_end_(loop_end),
+ code_start_(-1),
+ code_end_(-1),
+ deferred_(deferred) {}
+
+
+size_t InstructionBlock::PredecessorIndexOf(
+ BasicBlock::RpoNumber rpo_number) const {
+ size_t j = 0;
+ for (InstructionBlock::Predecessors::const_iterator i =
predecessors_.begin();
+ i != predecessors_.end(); ++i, ++j) {
+ if (*i == rpo_number) break;
+ }
+ return j;
+}
static BasicBlock::RpoNumber GetRpo(BasicBlock* block) {
@@ -350,43 +380,23 @@
}
-InstructionBlock::InstructionBlock(Zone* zone, const BasicBlock* block)
- : successors_(static_cast<int>(block->SuccessorCount()),
- BasicBlock::RpoNumber::Invalid(), zone),
- predecessors_(static_cast<int>(block->PredecessorCount()),
- BasicBlock::RpoNumber::Invalid(), zone),
- phis_(zone),
- id_(block->id()),
- ao_number_(block->GetAoNumber()),
- rpo_number_(block->GetRpoNumber()),
- loop_header_(GetRpo(block->loop_header())),
- loop_end_(GetLoopEndRpo(block)),
- code_start_(-1),
- code_end_(-1),
- deferred_(block->deferred()) {
+static InstructionBlock* InstructionBlockFor(Zone* zone,
+ const BasicBlock* block) {
+ InstructionBlock* instr_block = new (zone) InstructionBlock(
+ zone, block->id(), block->GetAoNumber(), block->GetRpoNumber(),
+ GetRpo(block->loop_header()), GetLoopEndRpo(block),
block->deferred());
// Map successors and precessors
- size_t index = 0;
- for (BasicBlock::Successors::const_iterator it =
block->successors_begin();
- it != block->successors_end(); ++it, ++index) {
- successors_[index] = (*it)->GetRpoNumber();
- }
- index = 0;
- for (BasicBlock::Predecessors::const_iterator
- it = block->predecessors_begin();
- it != block->predecessors_end(); ++it, ++index) {
- predecessors_[index] = (*it)->GetRpoNumber();
+ instr_block->successors().reserve(block->SuccessorCount());
+ for (auto it = block->successors_begin(); it != block->successors_end();
+ ++it) {
+ instr_block->successors().push_back((*it)->GetRpoNumber());
}
-}
-
-
-size_t InstructionBlock::PredecessorIndexOf(
- BasicBlock::RpoNumber rpo_number) const {
- size_t j = 0;
- for (InstructionBlock::Predecessors::const_iterator i =
predecessors_.begin();
- i != predecessors_.end(); ++i, ++j) {
- if (*i == rpo_number) break;
+ instr_block->predecessors().reserve(block->PredecessorCount());
+ for (auto it = block->predecessors_begin(); it !=
block->predecessors_end();
+ ++it) {
+ instr_block->predecessors().push_back((*it)->GetRpoNumber());
}
- return j;
+ return instr_block;
}
@@ -400,7 +410,7 @@
it != schedule->rpo_order()->end(); ++it, ++rpo_number) {
DCHECK_EQ(NULL, (*blocks)[rpo_number]);
DCHECK((*it)->GetRpoNumber().ToSize() == rpo_number);
- (*blocks)[rpo_number] = new (zone) InstructionBlock(zone, *it);
+ (*blocks)[rpo_number] = InstructionBlockFor(zone, *it);
}
return blocks;
}
@@ -436,18 +446,18 @@
}
-void InstructionSequence::StartBlock(BasicBlock* basic_block) {
- InstructionBlock* block =
InstructionBlockAt(basic_block->GetRpoNumber());
+void InstructionSequence::StartBlock(BasicBlock::RpoNumber rpo) {
+ InstructionBlock* block = InstructionBlockAt(rpo);
block->set_code_start(static_cast<int>(instructions_.size()));
BlockStartInstruction* block_start =
- BlockStartInstruction::New(zone(), basic_block);
+ BlockStartInstruction::New(zone(), block->id(), rpo);
AddInstruction(block_start);
}
-void InstructionSequence::EndBlock(BasicBlock* basic_block) {
+void InstructionSequence::EndBlock(BasicBlock::RpoNumber rpo) {
int end = static_cast<int>(instructions_.size());
- InstructionBlock* block =
InstructionBlockAt(basic_block->GetRpoNumber());
+ InstructionBlock* block = InstructionBlockAt(rpo);
DCHECK(block->code_start() >= 0 && block->code_start() < end);
block->set_code_end(end);
}
=======================================
--- /branches/bleeding_edge/src/compiler/instruction.h Tue Nov 4 09:21:12
2014 UTC
+++ /branches/bleeding_edge/src/compiler/instruction.h Thu Nov 6 08:28:15
2014 UTC
@@ -624,9 +624,10 @@
BasicBlock::RpoNumber rpo_number() const { return rpo_number_; }
BasicBlock::Id id() const { return id_; }
- static BlockStartInstruction* New(Zone* zone, BasicBlock* block) {
+ static BlockStartInstruction* New(Zone* zone, BasicBlock::Id id,
+ BasicBlock::RpoNumber rpo_number) {
void* buffer = zone->New(sizeof(BlockStartInstruction));
- return new (buffer) BlockStartInstruction(block);
+ return new (buffer) BlockStartInstruction(id, rpo_number);
}
static BlockStartInstruction* cast(Instruction* instr) {
@@ -635,10 +636,10 @@
}
private:
- explicit BlockStartInstruction(BasicBlock* block)
+ BlockStartInstruction(BasicBlock::Id id, BasicBlock::RpoNumber
rpo_number)
: GapInstruction(kBlockStartInstruction),
- id_(block->id()),
- rpo_number_(block->GetRpoNumber()) {}
+ id_(id),
+ rpo_number_(rpo_number) {}
BasicBlock::Id id_;
BasicBlock::RpoNumber rpo_number_;
@@ -799,7 +800,11 @@
// Analogue of BasicBlock for Instructions instead of Nodes.
class InstructionBlock FINAL : public ZoneObject {
public:
- explicit InstructionBlock(Zone* zone, const BasicBlock* block);
+ InstructionBlock(Zone* zone, BasicBlock::Id id,
+ BasicBlock::RpoNumber ao_number,
+ BasicBlock::RpoNumber rpo_number,
+ BasicBlock::RpoNumber loop_header,
+ BasicBlock::RpoNumber loop_end, bool deferred);
// Instruction indexes (used by the register allocator).
int first_instruction_index() const {
@@ -943,8 +948,8 @@
// Used by the instruction selector while adding instructions.
int AddInstruction(Instruction* instr);
- void StartBlock(BasicBlock* block);
- void EndBlock(BasicBlock* block);
+ void StartBlock(BasicBlock::RpoNumber rpo);
+ void EndBlock(BasicBlock::RpoNumber rpo);
int AddConstant(int virtual_register, Constant constant) {
DCHECK(virtual_register >= 0 && virtual_register <
next_virtual_register_);
=======================================
--- /branches/bleeding_edge/test/cctest/compiler/test-instruction.cc Wed
Nov 5 10:10:28 2014 UTC
+++ /branches/bleeding_edge/test/cctest/compiler/test-instruction.cc Thu
Nov 6 08:28:15 2014 UTC
@@ -158,23 +158,23 @@
R.allocCode();
- R.code->StartBlock(b0);
+ R.code->StartBlock(b0->GetRpoNumber());
int i0 = R.NewInstr();
int i1 = R.NewInstr();
- R.code->EndBlock(b0);
- R.code->StartBlock(b1);
+ R.code->EndBlock(b0->GetRpoNumber());
+ R.code->StartBlock(b1->GetRpoNumber());
int i2 = R.NewInstr();
int i3 = R.NewInstr();
int i4 = R.NewInstr();
int i5 = R.NewInstr();
- R.code->EndBlock(b1);
- R.code->StartBlock(b2);
+ R.code->EndBlock(b1->GetRpoNumber());
+ R.code->StartBlock(b2->GetRpoNumber());
int i6 = R.NewInstr();
int i7 = R.NewInstr();
int i8 = R.NewInstr();
- R.code->EndBlock(b2);
- R.code->StartBlock(b3);
- R.code->EndBlock(b3);
+ R.code->EndBlock(b2->GetRpoNumber());
+ R.code->StartBlock(b3->GetRpoNumber());
+ R.code->EndBlock(b3->GetRpoNumber());
CHECK_EQ(b0, R.GetBasicBlock(i0));
CHECK_EQ(b0, R.GetBasicBlock(i1));
@@ -211,10 +211,10 @@
R.allocCode();
TestInstr* i0 = TestInstr::New(R.zone(), 100);
TestInstr* g = TestInstr::New(R.zone(), 103)->MarkAsControl();
- R.code->StartBlock(b0);
+ R.code->StartBlock(b0->GetRpoNumber());
R.code->AddInstruction(i0);
R.code->AddInstruction(g);
- R.code->EndBlock(b0);
+ R.code->EndBlock(b0->GetRpoNumber());
CHECK_EQ(true, R.code->InstructionAt(0)->IsBlockStart());
@@ -238,17 +238,17 @@
R.allocCode();
TestInstr* i0 = TestInstr::New(R.zone(), 100);
TestInstr* g = TestInstr::New(R.zone(), 103)->MarkAsControl();
- R.code->StartBlock(b0);
+ R.code->StartBlock(b0->GetRpoNumber());
R.code->AddInstruction(i0);
R.code->AddInstruction(g);
- R.code->EndBlock(b0);
+ R.code->EndBlock(b0->GetRpoNumber());
TestInstr* i1 = TestInstr::New(R.zone(), 102);
TestInstr* g1 = TestInstr::New(R.zone(), 104)->MarkAsControl();
- R.code->StartBlock(b1);
+ R.code->StartBlock(b1->GetRpoNumber());
R.code->AddInstruction(i1);
R.code->AddInstruction(g1);
- R.code->EndBlock(b1);
+ R.code->EndBlock(b1->GetRpoNumber());
CHECK_EQ(true, R.code->InstructionAt(0)->IsBlockStart());
@@ -279,10 +279,10 @@
R.allocCode();
TestInstr* i0 = TestInstr::New(R.zone(), 100);
TestInstr* g = TestInstr::New(R.zone(), 103)->MarkAsControl();
- R.code->StartBlock(b0);
+ R.code->StartBlock(b0->GetRpoNumber());
R.code->AddInstruction(i0);
R.code->AddInstruction(g);
- R.code->EndBlock(b0);
+ R.code->EndBlock(b0->GetRpoNumber());
CHECK_EQ(true, R.code->InstructionAt(0)->IsBlockStart());
=======================================
---
/branches/bleeding_edge/test/unittests/compiler/register-allocator-unittest.cc
Wed Nov 5 10:10:28 2014 UTC
+++
/branches/bleeding_edge/test/unittests/compiler/register-allocator-unittest.cc
Thu Nov 6 08:28:15 2014 UTC
@@ -36,12 +36,38 @@
*loc++ = 0;
}
}
+
+enum BlockCompletionType { kFallThrough, kBranch, kJump };
+
+struct BlockCompletion {
+ BlockCompletionType type_;
+ int vreg_;
+ int offset_0_;
+ int offset_1_;
+};
+
+static const int kInvalidJumpOffset = kMinInt;
+
+BlockCompletion FallThrough() {
+ BlockCompletion completion = {kFallThrough, -1, 1, kInvalidJumpOffset};
+ return completion;
+}
+
+
+BlockCompletion Jump(int offset) {
+ BlockCompletion completion = {kJump, -1, offset, kInvalidJumpOffset};
+ return completion;
+}
+
+
+BlockCompletion Branch(int vreg, int left_offset, int right_offset) {
+ BlockCompletion completion = {kBranch, vreg, left_offset, right_offset};
+ return completion;
+}
} // 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;
@@ -49,11 +75,17 @@
RegisterAllocatorTest()
: num_general_registers_(kDefaultNRegs),
num_double_registers_(kDefaultNRegs),
- basic_blocks_(zone()),
instruction_blocks_(zone()),
- current_block_(NULL) {
+ current_block_(nullptr),
+ is_last_block_(false) {
InitializeRegisterNames();
}
+
+ void SetNumRegs(int num_general_registers, int num_double_registers) {
+ CHECK(instruction_blocks_.empty());
+ num_general_registers_ = num_general_registers;
+ num_double_registers_ = num_double_registers;
+ }
RegisterConfiguration* config() {
if (config_.is_empty()) {
@@ -86,42 +118,64 @@
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(basic_blocks_[loop_end.ToSize()]);
+ void StartLoop(int loop_blocks) {
+ CHECK(current_block_ == nullptr);
+ if (!loop_blocks_.empty()) {
+ CHECK(!loop_blocks_.back().loop_header_.IsValid());
}
- 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;
+ LoopData loop_data = {Rpo::Invalid(), loop_blocks};
+ loop_blocks_.push_back(loop_data);
}
- void EndBlock() {
- CHECK(current_block_ != NULL);
-
sequence()->EndBlock(basic_blocks_[current_block_->rpo_number().ToSize()]);
- current_block_ = NULL;
+ void EndLoop() {
+ CHECK(current_block_ == nullptr);
+ CHECK(!loop_blocks_.empty());
+ CHECK_EQ(0, loop_blocks_.back().expected_blocks_);
+ loop_blocks_.pop_back();
+ }
+
+ void StartLastBlock() {
+ CHECK(!is_last_block_);
+ is_last_block_ = true;
+ NewBlock();
+ }
+
+ void StartBlock() {
+ CHECK(!is_last_block_);
+ NewBlock();
+ }
+
+ void EndBlock(BlockCompletion completion = FallThrough()) {
+ completions_.push_back(completion);
+ switch (completion.type_) {
+ case kFallThrough:
+ if (is_last_block_) break;
+ // TODO(dcarney): we don't emit this after returns.
+ EmitFallThrough();
+ break;
+ case kJump:
+ EmitJump();
+ break;
+ case kBranch:
+ EmitBranch(completion.vreg_);
+ break;
+ }
+ CHECK(current_block_ != nullptr);
+ sequence()->EndBlock(current_block_->rpo_number());
+ current_block_ = nullptr;
}
void Allocate() {
- if (FLAG_trace_alloc) {
+ CHECK_EQ(nullptr, current_block_);
+ CHECK(is_last_block_);
+ WireBlocks();
+ if (FLAG_trace_alloc || FLAG_trace_turbo) {
OFStream os(stdout);
PrintableInstructionSequence printable = {config(), sequence()};
os << "Before: " << std::endl << printable << std::endl;
}
allocator()->Allocate();
- if (FLAG_trace_alloc) {
+ if (FLAG_trace_alloc || FLAG_trace_turbo) {
OFStream os(stdout);
PrintableInstructionSequence printable = {config(), sequence()};
os << "After: " << std::endl << printable << std::endl;
@@ -131,61 +185,223 @@
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));
+ InstructionOperand* outputs[1]{UseRegister(vreg)};
+ Emit(kArchNop, 1, outputs);
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* Return(int vreg) {
+ InstructionOperand* inputs[1]{UseRegister(vreg)};
+ return Emit(kArchRet, 0, nullptr, 1, inputs);
}
- Instruction* Emit(int output_vreg, int input_vreg_0, int input_vreg_1) {
+ PhiInstruction* Phi(int vreg) {
+ PhiInstruction* phi = new (zone()) PhiInstruction(zone(), NewReg());
+ phi->operands().push_back(vreg);
+ current_block_->AddPhi(phi);
+ return phi;
+ }
+
+ int DefineConstant(int32_t imm = 0) {
+ int virtual_register = NewReg();
+ sequence()->AddConstant(virtual_register, Constant(imm));
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;
+ ConstantOperand::Create(virtual_register, zone())};
+ Emit(kArchNop, 1, outputs);
+ return virtual_register;
+ }
+
+ ImmediateOperand* Immediate(int32_t imm = 0) {
+ int index = sequence()->AddImmediate(Constant(imm));
+ return ImmediateOperand::Create(index, zone());
+ }
+
+ Instruction* EmitFRI(int output_vreg, int input_vreg_0) {
+ InstructionOperand* outputs[1]{DefineSameAsFirst(output_vreg)};
+ InstructionOperand* inputs[2]{UseRegister(input_vreg_0), Immediate()};
+ return Emit(kArchNop, 1, outputs, 2, inputs);
+ }
+
+ Instruction* EmitFRU(int output_vreg, int input_vreg_0, int
input_vreg_1) {
+ InstructionOperand* outputs[1]{DefineSameAsFirst(output_vreg)};
+ InstructionOperand* inputs[2]{UseRegister(input_vreg_0),
Use(input_vreg_1)};
+ return Emit(kArchNop, 1, outputs, 2, inputs);
+ }
+
+ Instruction* EmitRRR(int output_vreg, int input_vreg_0, int
input_vreg_1) {
+ InstructionOperand* outputs[1]{UseRegister(output_vreg)};
+ InstructionOperand* inputs[2]{UseRegister(input_vreg_0),
+ UseRegister(input_vreg_1)};
+ return Emit(kArchNop, 1, outputs, 2, inputs);
}
private:
- InstructionOperand* Unallocated(UnallocatedOperand::ExtendedPolicy
policy,
- int vreg) {
- UnallocatedOperand* op =
- new (zone())
UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER);
+ InstructionOperand* Unallocated(int vreg,
+ UnallocatedOperand::ExtendedPolicy
policy) {
+ UnallocatedOperand* op = new (zone()) UnallocatedOperand(policy);
op->set_virtual_register(vreg);
return op;
}
- int num_general_registers_;
- int num_double_registers_;
+ InstructionOperand* Unallocated(int vreg,
+ UnallocatedOperand::ExtendedPolicy
policy,
+ UnallocatedOperand::Lifetime lifetime) {
+ UnallocatedOperand* op = new (zone()) UnallocatedOperand(policy,
lifetime);
+ op->set_virtual_register(vreg);
+ return op;
+ }
+
+ InstructionOperand* UseRegister(int vreg) {
+ return Unallocated(vreg, UnallocatedOperand::MUST_HAVE_REGISTER);
+ }
+
+ InstructionOperand* DefineSameAsFirst(int vreg) {
+ return Unallocated(vreg, UnallocatedOperand::SAME_AS_FIRST_INPUT);
+ }
+
+ InstructionOperand* Use(int vreg) {
+ return Unallocated(vreg, UnallocatedOperand::NONE,
+ UnallocatedOperand::USED_AT_START);
+ }
+
+ void EmitBranch(int vreg) {
+ InstructionOperand* inputs[4]{UseRegister(vreg), Immediate(),
Immediate(),
+ Immediate()};
+ InstructionCode opcode = kArchJmp |
FlagsModeField::encode(kFlags_branch) |
+ FlagsConditionField::encode(kEqual);
+ Instruction* instruction =
+ NewInstruction(opcode, 0, nullptr, 4, inputs)->MarkAsControl();
+ sequence()->AddInstruction(instruction);
+ }
+
+ void EmitFallThrough() {
+ Instruction* instruction =
+ NewInstruction(kArchNop, 0, nullptr)->MarkAsControl();
+ sequence()->AddInstruction(instruction);
+ }
+
+ void EmitJump() {
+ InstructionOperand* inputs[1]{Immediate()};
+ Instruction* instruction =
+ NewInstruction(kArchJmp, 0, nullptr, 1, inputs)->MarkAsControl();
+ sequence()->AddInstruction(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);
+ }
+
+ Instruction* Emit(InstructionCode code, size_t outputs_size,
+ InstructionOperand** outputs, size_t inputs_size = 0,
+ InstructionOperand* *inputs = nullptr,
+ size_t temps_size = 0,
+ InstructionOperand* *temps = nullptr) {
+ Instruction* instruction = NewInstruction(
+ code, outputs_size, outputs, inputs_size, inputs, temps_size,
temps);
+ sequence()->AddInstruction(instruction);
+ return instruction;
+ }
+
+ InstructionBlock* NewBlock() {
+ CHECK(current_block_ == nullptr);
+ BasicBlock::Id 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.
+ InstructionBlock* 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;
+ size_t size = instruction_blocks_.size();
+ for (const auto& completion : completions_) {
+ switch (completion.type_) {
+ case kFallThrough:
+ if (offset == size - 1) break;
+ // 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());
+ InstructionBlock* block = instruction_blocks_[block_offset];
+ InstructionBlock* target = instruction_blocks_[target_block_offset];
+ block->successors().push_back(target->rpo_number());
+ target->predecessors().push_back(block->rpo_number());
+ }
+
+ struct LoopData {
+ Rpo loop_header_;
+ int expected_blocks_;
+ };
+ typedef std::vector<LoopData> LoopBlocks;
+ typedef std::vector<BlockCompletion> Completions;
+
SmartPointer<RegisterConfiguration> config_;
- ZoneVector<BasicBlock*> basic_blocks_;
- InstructionBlocks instruction_blocks_;
- InstructionBlock* current_block_;
SmartPointer<Frame> frame_;
SmartPointer<RegisterAllocator> allocator_;
SmartPointer<InstructionSequence> sequence_;
+ int num_general_registers_;
+ int num_double_registers_;
+
+ // Block building state.
+ InstructionBlocks instruction_blocks_;
+ Completions completions_;
+ LoopBlocks loop_blocks_;
+ InstructionBlock* current_block_;
+ bool is_last_block_;
};
TEST_F(RegisterAllocatorTest, CanAllocateThreeRegisters) {
- StartBlock();
+ StartLastBlock();
int a_reg = Parameter();
int b_reg = Parameter();
int c_reg = NewReg();
- Instruction* res = Emit(c_reg, a_reg, b_reg);
+ Instruction* res = EmitRRR(c_reg, a_reg, b_reg);
Return(c_reg);
EndBlock();
@@ -193,6 +409,49 @@
ASSERT_TRUE(res->OutputAt(0)->IsRegister());
}
+
+
+TEST_F(RegisterAllocatorTest, SimpleLoop) {
+ // i = K;
+ // while(true) { i++ }
+
+ StartBlock();
+ int i_reg = DefineConstant();
+ EndBlock();
+
+ {
+ StartLoop(1);
+
+ StartLastBlock();
+ PhiInstruction* phi = Phi(i_reg);
+ int ipp = NewReg();
+ EmitFRU(ipp, phi->virtual_register(), DefineConstant());
+ phi->operands().push_back(ipp);
+ EndBlock(Jump(0));
+
+ EndLoop();
+ }
+
+ Allocate();
+}
+
+
+TEST_F(RegisterAllocatorTest, SimpleBranch) {
+ // return i ? K1 : K2
+ StartBlock();
+ int i_reg = DefineConstant();
+ EndBlock(Branch(i_reg, 1, 2));
+
+ StartBlock();
+ Return(DefineConstant());
+ EndBlock();
+
+ StartLastBlock();
+ Return(DefineConstant());
+ EndBlock();
+
+ Allocate();
+}
} // namespace compiler
} // namespace internal
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
