From e6552d49177df39fc4f806af862d722cd8d072d8 Mon Sep 17 00:00:00 2001 From: dcarney Date: Thu, 15 Jan 2015 01:05:52 -0800 Subject: [PATCH] Reland "[turbofan] simplify gap ordering" BUG= Review URL: https://codereview.chromium.org/854703002 Cr-Commit-Position: refs/heads/master@{#26069} --- src/compiler/instruction.cc | 16 ++++---- src/compiler/instruction.h | 34 ++-------------- src/compiler/register-allocator.cc | 15 ++++--- test/cctest/compiler/test-instruction.cc | 47 ++++++---------------- test/cctest/compiler/test-jump-threading.cc | 4 +- .../compiler/instruction-selector-unittest.cc | 10 ++--- test/unittests/compiler/move-optimizer-unittest.cc | 8 +--- 7 files changed, 43 insertions(+), 91 deletions(-) diff --git a/src/compiler/instruction.cc b/src/compiler/instruction.cc index 5ca0f12..9d6d5e2 100644 --- a/src/compiler/instruction.cc +++ b/src/compiler/instruction.cc @@ -279,7 +279,7 @@ std::ostream& operator<<(std::ostream& os, if (instr.IsGapMoves()) { const GapInstruction* gap = GapInstruction::cast(&instr); - os << (instr.IsBlockStart() ? " block-start" : "gap "); + os << "gap "; for (int i = GapInstruction::FIRST_INNER_POSITION; i <= GapInstruction::LAST_INNER_POSITION; i++) { os << "("; @@ -457,10 +457,10 @@ int InstructionSequence::NextVirtualRegister() { } -BlockStartInstruction* InstructionSequence::GetBlockStart( +GapInstruction* InstructionSequence::GetBlockStart( BasicBlock::RpoNumber rpo) const { const InstructionBlock* block = InstructionBlockAt(rpo); - return BlockStartInstruction::cast(InstructionAt(block->code_start())); + return GapInstruction::cast(InstructionAt(block->code_start())); } @@ -470,26 +470,26 @@ void InstructionSequence::StartBlock(BasicBlock::RpoNumber rpo) { int code_start = static_cast(instructions_.size()); block->set_code_start(code_start); block_starts_.push_back(code_start); - BlockStartInstruction* block_start = BlockStartInstruction::New(zone()); - AddInstruction(block_start); } void InstructionSequence::EndBlock(BasicBlock::RpoNumber rpo) { int end = static_cast(instructions_.size()); InstructionBlock* block = InstructionBlockAt(rpo); + if (block->code_start() == end) { // Empty block. Insert a nop. + AddInstruction(Instruction::New(zone(), kArchNop)); + end = static_cast(instructions_.size()); + } DCHECK(block->code_start() >= 0 && block->code_start() < end); block->set_code_end(end); } int InstructionSequence::AddInstruction(Instruction* instr) { - // TODO(titzer): the order of these gaps is a holdover from Lithium. GapInstruction* gap = GapInstruction::New(zone()); - if (instr->IsControl()) instructions_.push_back(gap); + instructions_.push_back(gap); int index = static_cast(instructions_.size()); instructions_.push_back(instr); - if (!instr->IsControl()) instructions_.push_back(gap); if (instr->NeedsPointerMap()) { DCHECK(instr->pointer_map() == NULL); PointerMap* pointer_map = new (zone()) PointerMap(zone()); diff --git a/src/compiler/instruction.h b/src/compiler/instruction.h index 1729d13..c1fdef4 100644 --- a/src/compiler/instruction.h +++ b/src/compiler/instruction.h @@ -25,8 +25,7 @@ namespace compiler { // A couple of reserved opcodes are used for internal use. const InstructionCode kGapInstruction = -1; -const InstructionCode kBlockStartInstruction = -2; -const InstructionCode kSourcePositionInstruction = -3; +const InstructionCode kSourcePositionInstruction = -2; #define INSTRUCTION_OPERAND_LIST(V) \ V(Constant, CONSTANT, 0) \ @@ -494,10 +493,7 @@ class Instruction : public ZoneObject { bool NeedsPointerMap() const { return IsCall(); } bool HasPointerMap() const { return pointer_map_ != NULL; } - bool IsGapMoves() const { - return opcode() == kGapInstruction || opcode() == kBlockStartInstruction; - } - bool IsBlockStart() const { return opcode() == kBlockStartInstruction; } + bool IsGapMoves() const { return opcode() == kGapInstruction; } bool IsSourcePosition() const { return opcode() == kSourcePositionInstruction; } @@ -643,30 +639,6 @@ class GapInstruction : public Instruction { }; -// This special kind of gap move instruction represents the beginning of a -// block of code. -class BlockStartInstruction FINAL : public GapInstruction { - public: - static BlockStartInstruction* New(Zone* zone) { - void* buffer = zone->New(sizeof(BlockStartInstruction)); - return new (buffer) BlockStartInstruction(); - } - - static BlockStartInstruction* cast(Instruction* instr) { - DCHECK(instr->IsBlockStart()); - return static_cast(instr); - } - - static const BlockStartInstruction* cast(const Instruction* instr) { - DCHECK(instr->IsBlockStart()); - return static_cast(instr); - } - - private: - BlockStartInstruction() : GapInstruction(kBlockStartInstruction) {} -}; - - class SourcePositionInstruction FINAL : public Instruction { public: static SourcePositionInstruction* New(Zone* zone, SourcePosition position) { @@ -983,7 +955,7 @@ class InstructionSequence FINAL : public ZoneObject { void AddGapMove(int index, InstructionOperand* from, InstructionOperand* to); - BlockStartInstruction* GetBlockStart(BasicBlock::RpoNumber rpo) const; + GapInstruction* GetBlockStart(BasicBlock::RpoNumber rpo) const; typedef InstructionDeque::const_iterator const_iterator; const_iterator begin() const { return instructions_.begin(); } diff --git a/src/compiler/register-allocator.cc b/src/compiler/register-allocator.cc index 7def50e..e0487fa 100644 --- a/src/compiler/register-allocator.cc +++ b/src/compiler/register-allocator.cc @@ -1071,7 +1071,7 @@ void RegisterAllocator::MeetRegisterConstraintsForLastInstructionInBlock( for (auto succ : block->successors()) { const InstructionBlock* successor = code()->InstructionBlockAt(succ); DCHECK(successor->PredecessorCount() == 1); - int gap_index = successor->first_instruction_index() + 1; + int gap_index = successor->first_instruction_index(); DCHECK(code()->IsGapAt(gap_index)); // Create an unconstrained operand for the same virtual register @@ -1088,7 +1088,7 @@ void RegisterAllocator::MeetRegisterConstraintsForLastInstructionInBlock( for (auto succ : block->successors()) { const InstructionBlock* successor = code()->InstructionBlockAt(succ); DCHECK(successor->PredecessorCount() == 1); - int gap_index = successor->first_instruction_index() + 1; + int gap_index = successor->first_instruction_index(); range->SpillAtDefinition(local_zone(), gap_index, output); range->SetSpillStartIndex(gap_index); } @@ -1398,7 +1398,7 @@ ParallelMove* RegisterAllocator::GetConnectingParallelMove( } int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); return code()->GapAt(gap_pos)->GetOrCreateParallelMove( - (gap_pos < index) ? GapInstruction::AFTER : GapInstruction::BEFORE, + (gap_pos < index) ? GapInstruction::AFTER : GapInstruction::START, code_zone()); } @@ -2325,7 +2325,8 @@ void RegisterAllocator::SplitAndSpillIntersecting(LiveRange* current) { bool RegisterAllocator::IsBlockBoundary(LifetimePosition pos) { return pos.IsInstructionStart() && - InstructionAt(pos.InstructionIndex())->IsBlockStart(); + code()->GetInstructionBlock(pos.InstructionIndex())->code_start() == + pos.InstructionIndex(); } @@ -2420,9 +2421,13 @@ void RegisterAllocator::SpillBetweenUntil(LiveRange* range, // The split result intersects with [start, end[. // Split it at position between ]start+1, end[, spill the middle part // and put the rest to unhandled. + auto third_part_end = end.PrevInstruction().InstructionEnd(); + if (IsBlockBoundary(end.InstructionStart())) { + third_part_end = end.InstructionStart(); + } auto third_part = SplitBetween( second_part, Max(second_part->Start().InstructionEnd(), until), - end.PrevInstruction().InstructionEnd()); + third_part_end); DCHECK(third_part != second_part); diff --git a/test/cctest/compiler/test-instruction.cc b/test/cctest/compiler/test-instruction.cc index 294812f..f1c9bcd 100644 --- a/test/cctest/compiler/test-instruction.cc +++ b/test/cctest/compiler/test-instruction.cc @@ -214,14 +214,10 @@ TEST(InstructionIsGapAt) { R.code->AddInstruction(g); R.code->EndBlock(b0->GetRpoNumber()); - CHECK_EQ(true, R.code->InstructionAt(0)->IsBlockStart()); - - CHECK_EQ(true, R.code->IsGapAt(0)); // Label - CHECK_EQ(true, R.code->IsGapAt(1)); // Gap - CHECK_EQ(false, R.code->IsGapAt(2)); // i0 - CHECK_EQ(true, R.code->IsGapAt(3)); // Gap - CHECK_EQ(true, R.code->IsGapAt(4)); // Gap - CHECK_EQ(false, R.code->IsGapAt(5)); // g + CHECK(R.code->instructions().size() == 4); + for (size_t i = 0; i < R.code->instructions().size(); ++i) { + CHECK_EQ(i % 2 == 0, R.code->instructions()[i]->IsGapMoves()); + } } @@ -248,23 +244,10 @@ TEST(InstructionIsGapAt2) { R.code->AddInstruction(g1); R.code->EndBlock(b1->GetRpoNumber()); - CHECK_EQ(true, R.code->InstructionAt(0)->IsBlockStart()); - - CHECK_EQ(true, R.code->IsGapAt(0)); // Label - CHECK_EQ(true, R.code->IsGapAt(1)); // Gap - CHECK_EQ(false, R.code->IsGapAt(2)); // i0 - CHECK_EQ(true, R.code->IsGapAt(3)); // Gap - CHECK_EQ(true, R.code->IsGapAt(4)); // Gap - CHECK_EQ(false, R.code->IsGapAt(5)); // g - - CHECK_EQ(true, R.code->InstructionAt(6)->IsBlockStart()); - - CHECK_EQ(true, R.code->IsGapAt(6)); // Label - CHECK_EQ(true, R.code->IsGapAt(7)); // Gap - CHECK_EQ(false, R.code->IsGapAt(8)); // i1 - CHECK_EQ(true, R.code->IsGapAt(9)); // Gap - CHECK_EQ(true, R.code->IsGapAt(10)); // Gap - CHECK_EQ(false, R.code->IsGapAt(11)); // g1 + CHECK(R.code->instructions().size() == 8); + for (size_t i = 0; i < R.code->instructions().size(); ++i) { + CHECK_EQ(i % 2 == 0, R.code->instructions()[i]->IsGapMoves()); + } } @@ -282,16 +265,12 @@ TEST(InstructionAddGapMove) { R.code->AddInstruction(g); R.code->EndBlock(b0->GetRpoNumber()); - CHECK_EQ(true, R.code->InstructionAt(0)->IsBlockStart()); - - CHECK_EQ(true, R.code->IsGapAt(0)); // Label - CHECK_EQ(true, R.code->IsGapAt(1)); // Gap - CHECK_EQ(false, R.code->IsGapAt(2)); // i0 - CHECK_EQ(true, R.code->IsGapAt(3)); // Gap - CHECK_EQ(true, R.code->IsGapAt(4)); // Gap - CHECK_EQ(false, R.code->IsGapAt(5)); // g + CHECK(R.code->instructions().size() == 4); + for (size_t i = 0; i < R.code->instructions().size(); ++i) { + CHECK_EQ(i % 2 == 0, R.code->instructions()[i]->IsGapMoves()); + } - int indexes[] = {0, 1, 3, 4, -1}; + int indexes[] = {0, 2, -1}; for (int i = 0; indexes[i] >= 0; i++) { int index = indexes[i]; diff --git a/test/cctest/compiler/test-jump-threading.cc b/test/cctest/compiler/test-jump-threading.cc index 74bf43d..4365170 100644 --- a/test/cctest/compiler/test-jump-threading.cc +++ b/test/cctest/compiler/test-jump-threading.cc @@ -60,14 +60,14 @@ class TestCode : public HandleAndZoneScope { void RedundantMoves() { Start(); sequence_.AddInstruction(Instruction::New(main_zone(), kArchNop)); - int index = static_cast(sequence_.instructions().size()) - 1; + int index = static_cast(sequence_.instructions().size()) - 2; sequence_.AddGapMove(index, RegisterOperand::Create(13, main_zone()), RegisterOperand::Create(13, main_zone())); } void NonRedundantMoves() { Start(); sequence_.AddInstruction(Instruction::New(main_zone(), kArchNop)); - int index = static_cast(sequence_.instructions().size()) - 1; + int index = static_cast(sequence_.instructions().size()) - 2; sequence_.AddGapMove(index, ImmediateOperand::Create(11, main_zone()), RegisterOperand::Create(11, main_zone())); } diff --git a/test/unittests/compiler/instruction-selector-unittest.cc b/test/unittests/compiler/instruction-selector-unittest.cc index 68649b7..b1c9073 100644 --- a/test/unittests/compiler/instruction-selector-unittest.cc +++ b/test/unittests/compiler/instruction-selector-unittest.cc @@ -149,7 +149,7 @@ TARGET_TEST_F(InstructionSelectorTest, ReturnFloat32Constant) { StreamBuilder m(this, kMachFloat32); m.Return(m.Float32Constant(kValue)); Stream s = m.Build(kAllInstructions); - ASSERT_EQ(2U, s.size()); + ASSERT_EQ(3U, s.size()); EXPECT_EQ(kArchNop, s[0]->arch_opcode()); ASSERT_EQ(InstructionOperand::CONSTANT, s[0]->OutputAt(0)->kind()); EXPECT_FLOAT_EQ(kValue, s.ToFloat32(s[0]->OutputAt(0))); @@ -162,7 +162,7 @@ TARGET_TEST_F(InstructionSelectorTest, ReturnParameter) { StreamBuilder m(this, kMachInt32, kMachInt32); m.Return(m.Parameter(0)); Stream s = m.Build(kAllInstructions); - ASSERT_EQ(2U, s.size()); + ASSERT_EQ(3U, s.size()); EXPECT_EQ(kArchNop, s[0]->arch_opcode()); ASSERT_EQ(1U, s[0]->OutputCount()); EXPECT_EQ(kArchRet, s[1]->arch_opcode()); @@ -174,7 +174,7 @@ TARGET_TEST_F(InstructionSelectorTest, ReturnZero) { StreamBuilder m(this, kMachInt32); m.Return(m.Int32Constant(0)); Stream s = m.Build(kAllInstructions); - ASSERT_EQ(2U, s.size()); + ASSERT_EQ(3U, s.size()); EXPECT_EQ(kArchNop, s[0]->arch_opcode()); ASSERT_EQ(1U, s[0]->OutputCount()); EXPECT_EQ(InstructionOperand::CONSTANT, s[0]->OutputAt(0)->kind()); @@ -192,7 +192,7 @@ TARGET_TEST_F(InstructionSelectorTest, TruncateFloat64ToInt32WithParameter) { StreamBuilder m(this, kMachInt32, kMachFloat64); m.Return(m.TruncateFloat64ToInt32(m.Parameter(0))); Stream s = m.Build(kAllInstructions); - ASSERT_EQ(3U, s.size()); + ASSERT_EQ(4U, s.size()); EXPECT_EQ(kArchNop, s[0]->arch_opcode()); EXPECT_EQ(kArchTruncateDoubleToI, s[1]->arch_opcode()); EXPECT_EQ(1U, s[1]->InputCount()); @@ -233,7 +233,7 @@ TARGET_TEST_F(InstructionSelectorTest, Finish) { Node* finish = m.NewNode(m.common()->Finish(1), param, m.graph()->start()); m.Return(finish); Stream s = m.Build(kAllInstructions); - ASSERT_EQ(3U, s.size()); + ASSERT_EQ(4U, s.size()); EXPECT_EQ(kArchNop, s[0]->arch_opcode()); ASSERT_EQ(1U, s[0]->OutputCount()); ASSERT_TRUE(s[0]->Output()->IsUnallocated()); diff --git a/test/unittests/compiler/move-optimizer-unittest.cc b/test/unittests/compiler/move-optimizer-unittest.cc index 5b956f0..2452d19 100644 --- a/test/unittests/compiler/move-optimizer-unittest.cc +++ b/test/unittests/compiler/move-optimizer-unittest.cc @@ -12,11 +12,7 @@ namespace compiler { class MoveOptimizerTest : public InstructionSequenceTest { public: GapInstruction* LastGap() { - auto instruction = sequence()->instructions().back(); - if (!instruction->IsGapMoves()) { - instruction = *(sequence()->instructions().rbegin() + 1); - } - return GapInstruction::cast(instruction); + return GapInstruction::cast(*(sequence()->instructions().rbegin() + 1)); } void AddMove(GapInstruction* gap, TestOperand from, TestOperand to, @@ -90,10 +86,10 @@ class MoveOptimizerTest : public InstructionSequenceTest { TEST_F(MoveOptimizerTest, RemovesRedundant) { StartBlock(); + EmitNop(); AddMove(LastGap(), Reg(0), Reg(1)); EmitNop(); AddMove(LastGap(), Reg(1), Reg(0)); - EmitNop(); EndBlock(Last()); Optimize(); -- 2.7.4