[turbofan] add gap move verifier

test/unittests/compiler/register-allocator-unittest.cc

 // 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 "src/compiler/register-allocator-verifier.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 {
@@ skipping 13 matching lines @@
     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;
   }
 }
 
-enum BlockCompletionType { kFallThrough, kBranch, kJump };
+enum BlockCompletionType { kBlockEnd, kFallThrough, kBranch, kJump };
 
 struct BlockCompletion {
   BlockCompletionType type_;
   int vreg_;
   int offset_0_;
   int offset_1_;
 };
 
 static const int kInvalidJumpOffset = kMinInt;
 
@@ skipping 19 matching lines @@
 
 class RegisterAllocatorTest : public TestWithZone {
  public:
   static const int kDefaultNRegs = 4;
 
   RegisterAllocatorTest()
       : num_general_registers_(kDefaultNRegs),
         num_double_registers_(kDefaultNRegs),
         instruction_blocks_(zone()),
         current_block_(nullptr),
-        is_last_block_(false) {
+        is_last_block_(false),
+        block_returns_(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() {
@@ skipping 44 matching lines @@
   }
 
   void StartLastBlock() {
     CHECK(!is_last_block_);
     is_last_block_ = true;
     NewBlock();
   }
 
   void StartBlock() {
     CHECK(!is_last_block_);
+    block_returns_ = false;
     NewBlock();
   }
 
   void EndBlock(BlockCompletion completion = FallThrough()) {
     completions_.push_back(completion);
     switch (completion.type_) {
+      case kBlockEnd:
+        CHECK(false);  // unreachable;
+        break;
       case kFallThrough:
-        if (is_last_block_) break;
-        // TODO(dcarney): we don't emit this after returns.
+        if (is_last_block_ || block_returns_) {
+          completions_.back().type_ = kBlockEnd;
+          break;
+        }
         EmitFallThrough();
         break;
       case kJump:
+        CHECK(!block_returns_);
         EmitJump();
         break;
       case kBranch:
+        CHECK(!block_returns_);
         EmitBranch(completion.vreg_);
         break;
     }
     CHECK(current_block_ != nullptr);
     sequence()->EndBlock(current_block_->rpo_number());
     current_block_ = nullptr;
   }
 
   void Allocate() {
     CHECK_EQ(nullptr, current_block_);
     CHECK(is_last_block_);
     WireBlocks();
+    RegisterAllocatorVerifier verifier(zone(), config(), sequence());
     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 || FLAG_trace_turbo) {
       OFStream os(stdout);
       PrintableInstructionSequence printable = {config(), sequence()};
       os << "After: " << std::endl << printable << std::endl;
     }
+    verifier.VerifyAssignment();
+    verifier.VerifyGapMoves();
   }
 
   int NewReg() { return sequence()->NextVirtualRegister(); }
 
   int Parameter() {
     int vreg = NewReg();
     InstructionOperand* outputs[1]{UseRegister(vreg)};
     Emit(kArchNop, 1, outputs);
     return vreg;
   }
 
   Instruction* Return(int vreg) {
+    block_returns_ = true;
     InstructionOperand* inputs[1]{UseRegister(vreg)};
     return Emit(kArchRet, 0, nullptr, 1, inputs);
   }
 
   PhiInstruction* Phi(int vreg) {
     PhiInstruction* phi = new (zone()) PhiInstruction(zone(), NewReg());
     phi->operands().push_back(vreg);
     current_block_->AddPhi(phi);
     return phi;
   }
@@ skipping 132 matching lines @@
         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 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;
     }
@@ skipping 23 matching lines @@
   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_;
+  bool block_returns_;
 };
 
 
 TEST_F(RegisterAllocatorTest, CanAllocateThreeRegisters) {
   StartLastBlock();
   int a_reg = Parameter();
   int b_reg = Parameter();
   int c_reg = NewReg();
   Instruction* res = EmitRRR(c_reg, a_reg, b_reg);
   Return(c_reg);
@@ skipping 98 matching lines @@
   // Return sum.
   Return(DefineConstant());
   EndBlock();
 
   Allocate();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8