instruction-sequence-unittest.cc 17.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// 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/pipeline.h"
#include "test/unittests/compiler/instruction-sequence-unittest.h"
#include "test/unittests/test-utils.h"
#include "testing/gmock/include/gmock/gmock.h"

namespace v8 {
namespace internal {
namespace compiler {

static const char*
    general_register_names_[RegisterConfiguration::kMaxGeneralRegisters];
static const char*
18
    double_register_names_[RegisterConfiguration::kMaxFPRegisters];
19
static char register_names_[10 * (RegisterConfiguration::kMaxGeneralRegisters +
20
                                  RegisterConfiguration::kMaxFPRegisters)];
21

22 23 24 25 26 27 28 29
namespace {
static int allocatable_codes[InstructionSequenceTest::kDefaultNRegs] = {
    0, 1, 2, 3, 4, 5, 6, 7};
static int allocatable_double_codes[InstructionSequenceTest::kDefaultNRegs] = {
    0, 1, 2, 3, 4, 5, 6, 7};
}


30 31 32 33 34 35 36
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;
  }
37
  for (int i = 0; i < RegisterConfiguration::kMaxFPRegisters; ++i) {
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
    double_register_names_[i] = loc;
    loc += base::OS::SNPrintF(loc, 100, "fp_%d", i) + 1;
    *loc++ = 0;
  }
}


InstructionSequenceTest::InstructionSequenceTest()
    : sequence_(nullptr),
      num_general_registers_(kDefaultNRegs),
      num_double_registers_(kDefaultNRegs),
      instruction_blocks_(zone()),
      current_block_(nullptr),
      block_returns_(false) {
  InitializeRegisterNames();
}


void InstructionSequenceTest::SetNumRegs(int num_general_registers,
                                         int num_double_registers) {
58
  CHECK(!config_);
59 60 61 62 63 64 65 66
  CHECK(instructions_.empty());
  CHECK(instruction_blocks_.empty());
  num_general_registers_ = num_general_registers;
  num_double_registers_ = num_double_registers;
}


RegisterConfiguration* InstructionSequenceTest::config() {
67 68
  if (!config_) {
    config_.reset(new RegisterConfiguration(
69
        num_general_registers_, num_double_registers_, num_general_registers_,
70 71
        num_double_registers_, num_double_registers_, allocatable_codes,
        allocatable_double_codes,
72 73 74
        kSimpleFPAliasing ? RegisterConfiguration::OVERLAP
                          : RegisterConfiguration::COMBINE,
        general_register_names_,
75
        double_register_names_,  // float register names
76 77
        double_register_names_,
        double_register_names_));  // SIMD 128 register names
78 79 80 81 82 83 84
  }
  return config_.get();
}


InstructionSequence* InstructionSequenceTest::sequence() {
  if (sequence_ == nullptr) {
85 86
    sequence_ = new (zone())
        InstructionSequence(isolate(), zone(), &instruction_blocks_);
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
  }
  return sequence_;
}


void InstructionSequenceTest::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 InstructionSequenceTest::EndLoop() {
  CHECK(current_block_ == nullptr);
  CHECK(!loop_blocks_.empty());
  CHECK_EQ(0, loop_blocks_.back().expected_blocks_);
  loop_blocks_.pop_back();
}


110
void InstructionSequenceTest::StartBlock(bool deferred) {
111
  block_returns_ = false;
112
  NewBlock(deferred);
113 114 115
}


dcarney's avatar
dcarney committed
116 117
Instruction* InstructionSequenceTest::EndBlock(BlockCompletion completion) {
  Instruction* result = nullptr;
118 119 120 121 122 123 124 125
  if (block_returns_) {
    CHECK(completion.type_ == kBlockEnd || completion.type_ == kFallThrough);
    completion.type_ = kBlockEnd;
  }
  switch (completion.type_) {
    case kBlockEnd:
      break;
    case kFallThrough:
126
      result = EmitJump();
127 128 129
      break;
    case kJump:
      CHECK(!block_returns_);
dcarney's avatar
dcarney committed
130
      result = EmitJump();
131 132 133
      break;
    case kBranch:
      CHECK(!block_returns_);
dcarney's avatar
dcarney committed
134
      result = EmitBranch(completion.op_);
135 136 137 138 139 140
      break;
  }
  completions_.push_back(completion);
  CHECK(current_block_ != nullptr);
  sequence()->EndBlock(current_block_->rpo_number());
  current_block_ = nullptr;
dcarney's avatar
dcarney committed
141
  return result;
142 143 144 145
}


InstructionSequenceTest::TestOperand InstructionSequenceTest::Imm(int32_t imm) {
146
  return TestOperand(kImmediate, imm);
147 148 149 150 151 152
}


InstructionSequenceTest::VReg InstructionSequenceTest::Define(
    TestOperand output_op) {
  VReg vreg = NewReg();
153
  InstructionOperand outputs[1]{ConvertOutputOp(vreg, output_op)};
dcarney's avatar
dcarney committed
154
  Emit(kArchNop, 1, outputs);
155 156 157 158
  return vreg;
}


dcarney's avatar
dcarney committed
159
Instruction* InstructionSequenceTest::Return(TestOperand input_op_0) {
160
  block_returns_ = true;
161
  InstructionOperand inputs[1]{ConvertInputOp(input_op_0)};
dcarney's avatar
dcarney committed
162
  return Emit(kArchRet, 0, nullptr, 1, inputs);
163 164 165 166 167 168 169 170 171
}


PhiInstruction* InstructionSequenceTest::Phi(VReg incoming_vreg_0,
                                             VReg incoming_vreg_1,
                                             VReg incoming_vreg_2,
                                             VReg incoming_vreg_3) {
  VReg inputs[] = {incoming_vreg_0, incoming_vreg_1, incoming_vreg_2,
                   incoming_vreg_3};
172 173 174
  size_t input_count = 0;
  for (; input_count < arraysize(inputs); ++input_count) {
    if (inputs[input_count].value_ == kNoValue) break;
175
  }
176 177 178 179 180 181 182 183 184 185 186 187 188 189
  CHECK(input_count > 0);
  auto phi = new (zone()) PhiInstruction(zone(), NewReg().value_, input_count);
  for (size_t i = 0; i < input_count; ++i) {
    SetInput(phi, i, inputs[i]);
  }
  current_block_->AddPhi(phi);
  return phi;
}


PhiInstruction* InstructionSequenceTest::Phi(VReg incoming_vreg_0,
                                             size_t input_count) {
  auto phi = new (zone()) PhiInstruction(zone(), NewReg().value_, input_count);
  SetInput(phi, 0, incoming_vreg_0);
190 191 192 193 194
  current_block_->AddPhi(phi);
  return phi;
}


195 196 197 198
void InstructionSequenceTest::SetInput(PhiInstruction* phi, size_t input,
                                       VReg vreg) {
  CHECK(vreg.value_ != kNoValue);
  phi->SetInput(input, vreg.value_);
199 200 201 202 203 204 205
}


InstructionSequenceTest::VReg InstructionSequenceTest::DefineConstant(
    int32_t imm) {
  VReg vreg = NewReg();
  sequence()->AddConstant(vreg.value_, Constant(imm));
206
  InstructionOperand outputs[1]{ConstantOperand(vreg.value_)};
dcarney's avatar
dcarney committed
207
  Emit(kArchNop, 1, outputs);
208 209 210 211
  return vreg;
}


dcarney's avatar
dcarney committed
212
Instruction* InstructionSequenceTest::EmitNop() { return Emit(kArchNop); }
213 214


215 216 217 218 219 220 221 222 223 224
static size_t CountInputs(size_t size,
                          InstructionSequenceTest::TestOperand* inputs) {
  size_t i = 0;
  for (; i < size; ++i) {
    if (inputs[i].type_ == InstructionSequenceTest::kInvalid) break;
  }
  return i;
}


dcarney's avatar
dcarney committed
225 226
Instruction* InstructionSequenceTest::EmitI(size_t input_size,
                                            TestOperand* inputs) {
227
  InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
dcarney's avatar
dcarney committed
228
  return Emit(kArchNop, 0, nullptr, input_size, mapped_inputs);
229 230 231
}


dcarney's avatar
dcarney committed
232 233 234 235
Instruction* InstructionSequenceTest::EmitI(TestOperand input_op_0,
                                            TestOperand input_op_1,
                                            TestOperand input_op_2,
                                            TestOperand input_op_3) {
236 237
  TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
  return EmitI(CountInputs(arraysize(inputs), inputs), inputs);
238 239 240 241
}


InstructionSequenceTest::VReg InstructionSequenceTest::EmitOI(
242
    TestOperand output_op, size_t input_size, TestOperand* inputs) {
243
  VReg output_vreg = NewReg();
244 245
  InstructionOperand outputs[1]{ConvertOutputOp(output_vreg, output_op)};
  InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
dcarney's avatar
dcarney committed
246
  Emit(kArchNop, 1, outputs, input_size, mapped_inputs);
247 248 249 250
  return output_vreg;
}


251 252 253 254 255
InstructionSequenceTest::VReg InstructionSequenceTest::EmitOI(
    TestOperand output_op, TestOperand input_op_0, TestOperand input_op_1,
    TestOperand input_op_2, TestOperand input_op_3) {
  TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
  return EmitOI(output_op, CountInputs(arraysize(inputs), inputs), inputs);
256 257 258
}


dcarney's avatar
dcarney committed
259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
InstructionSequenceTest::VRegPair InstructionSequenceTest::EmitOOI(
    TestOperand output_op_0, TestOperand output_op_1, size_t input_size,
    TestOperand* inputs) {
  VRegPair output_vregs = std::make_pair(NewReg(), NewReg());
  InstructionOperand outputs[2]{
      ConvertOutputOp(output_vregs.first, output_op_0),
      ConvertOutputOp(output_vregs.second, output_op_1)};
  InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
  Emit(kArchNop, 2, outputs, input_size, mapped_inputs);
  return output_vregs;
}


InstructionSequenceTest::VRegPair InstructionSequenceTest::EmitOOI(
    TestOperand output_op_0, TestOperand output_op_1, TestOperand input_op_0,
    TestOperand input_op_1, TestOperand input_op_2, TestOperand input_op_3) {
  TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
  return EmitOOI(output_op_0, output_op_1,
                 CountInputs(arraysize(inputs), inputs), inputs);
}


281 282 283
InstructionSequenceTest::VReg InstructionSequenceTest::EmitCall(
    TestOperand output_op, size_t input_size, TestOperand* inputs) {
  VReg output_vreg = NewReg();
284 285 286
  InstructionOperand outputs[1]{ConvertOutputOp(output_vreg, output_op)};
  CHECK(UnallocatedOperand::cast(outputs[0]).HasFixedPolicy());
  InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
dcarney's avatar
dcarney committed
287 288
  Emit(kArchCallCodeObject, 1, outputs, input_size, mapped_inputs, 0, nullptr,
       true);
289 290 291 292 293 294 295 296
  return output_vreg;
}


InstructionSequenceTest::VReg InstructionSequenceTest::EmitCall(
    TestOperand output_op, TestOperand input_op_0, TestOperand input_op_1,
    TestOperand input_op_2, TestOperand input_op_3) {
  TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
297
  return EmitCall(output_op, CountInputs(arraysize(inputs), inputs), inputs);
298 299 300
}


dcarney's avatar
dcarney committed
301
Instruction* InstructionSequenceTest::EmitBranch(TestOperand input_op) {
302 303
  InstructionOperand inputs[4]{ConvertInputOp(input_op), ConvertInputOp(Imm()),
                               ConvertInputOp(Imm()), ConvertInputOp(Imm())};
304 305
  InstructionCode opcode = kArchJmp | FlagsModeField::encode(kFlags_branch) |
                           FlagsConditionField::encode(kEqual);
306
  auto instruction = NewInstruction(opcode, 0, nullptr, 4, inputs);
dcarney's avatar
dcarney committed
307
  return AddInstruction(instruction);
308 309 310
}


dcarney's avatar
dcarney committed
311
Instruction* InstructionSequenceTest::EmitFallThrough() {
312
  auto instruction = NewInstruction(kArchNop, 0, nullptr);
dcarney's avatar
dcarney committed
313
  return AddInstruction(instruction);
314 315 316
}


dcarney's avatar
dcarney committed
317
Instruction* InstructionSequenceTest::EmitJump() {
318
  InstructionOperand inputs[1]{ConvertInputOp(Imm())};
319
  auto instruction = NewInstruction(kArchJmp, 0, nullptr, 1, inputs);
dcarney's avatar
dcarney committed
320
  return AddInstruction(instruction);
321 322 323 324
}


Instruction* InstructionSequenceTest::NewInstruction(
325 326 327
    InstructionCode code, size_t outputs_size, InstructionOperand* outputs,
    size_t inputs_size, InstructionOperand* inputs, size_t temps_size,
    InstructionOperand* temps) {
328
  CHECK(current_block_);
329 330 331 332 333
  return Instruction::New(zone(), code, outputs_size, outputs, inputs_size,
                          inputs, temps_size, temps);
}


334
InstructionOperand InstructionSequenceTest::Unallocated(
335
    TestOperand op, UnallocatedOperand::ExtendedPolicy policy) {
336
  return UnallocatedOperand(policy, op.vreg_.value_);
337 338 339
}


340
InstructionOperand InstructionSequenceTest::Unallocated(
341 342
    TestOperand op, UnallocatedOperand::ExtendedPolicy policy,
    UnallocatedOperand::Lifetime lifetime) {
343
  return UnallocatedOperand(policy, lifetime, op.vreg_.value_);
344 345 346
}


347
InstructionOperand InstructionSequenceTest::Unallocated(
348
    TestOperand op, UnallocatedOperand::ExtendedPolicy policy, int index) {
349
  return UnallocatedOperand(policy, index, op.vreg_.value_);
350 351 352
}


353
InstructionOperand InstructionSequenceTest::Unallocated(
354
    TestOperand op, UnallocatedOperand::BasicPolicy policy, int index) {
355
  return UnallocatedOperand(policy, index, op.vreg_.value_);
356 357 358
}


359
InstructionOperand* InstructionSequenceTest::ConvertInputs(
360
    size_t input_size, TestOperand* inputs) {
361 362
  InstructionOperand* mapped_inputs =
      zone()->NewArray<InstructionOperand>(static_cast<int>(input_size));
363 364 365 366 367 368 369
  for (size_t i = 0; i < input_size; ++i) {
    mapped_inputs[i] = ConvertInputOp(inputs[i]);
  }
  return mapped_inputs;
}


370
InstructionOperand InstructionSequenceTest::ConvertInputOp(TestOperand op) {
371 372
  if (op.type_ == kImmediate) {
    CHECK_EQ(op.vreg_.value_, kNoValue);
373
    return ImmediateOperand(ImmediateOperand::INLINE, op.value_);
374 375 376 377 378 379
  }
  CHECK_NE(op.vreg_.value_, kNoValue);
  switch (op.type_) {
    case kNone:
      return Unallocated(op, UnallocatedOperand::NONE,
                         UnallocatedOperand::USED_AT_START);
380 381 382 383
    case kUnique:
      return Unallocated(op, UnallocatedOperand::NONE);
    case kUniqueRegister:
      return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER);
384 385 386
    case kRegister:
      return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER,
                         UnallocatedOperand::USED_AT_START);
387 388 389
    case kSlot:
      return Unallocated(op, UnallocatedOperand::MUST_HAVE_SLOT,
                         UnallocatedOperand::USED_AT_START);
390 391 392 393 394 395 396 397 398
    case kFixedRegister:
      CHECK(0 <= op.value_ && op.value_ < num_general_registers_);
      return Unallocated(op, UnallocatedOperand::FIXED_REGISTER, op.value_);
    case kFixedSlot:
      return Unallocated(op, UnallocatedOperand::FIXED_SLOT, op.value_);
    default:
      break;
  }
  CHECK(false);
399
  return InstructionOperand();
400 401 402
}


403 404
InstructionOperand InstructionSequenceTest::ConvertOutputOp(VReg vreg,
                                                            TestOperand op) {
405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
  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);
421
  return InstructionOperand();
422 423 424
}


425
InstructionBlock* InstructionSequenceTest::NewBlock(bool deferred) {
426
  CHECK(current_block_ == nullptr);
427
  Rpo rpo = Rpo::FromInt(static_cast<int>(instruction_blocks_.size()));
428 429 430 431 432 433
  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()) {
434
      loop_end = Rpo::FromInt(rpo.ToInt() + loop_data.expected_blocks_);
435 436 437 438 439 440 441 442 443 444 445
      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.
446
  auto instruction_block = new (zone())
447
      InstructionBlock(zone(), rpo, loop_header, loop_end, deferred, false);
448 449 450 451 452 453 454 455
  instruction_blocks_.push_back(instruction_block);
  current_block_ = instruction_block;
  sequence()->StartBlock(rpo);
  return instruction_block;
}


void InstructionSequenceTest::WireBlocks() {
456
  CHECK(!current_block());
457
  CHECK(instruction_blocks_.size() == completions_.size());
458 459 460 461 462
  CHECK(loop_blocks_.empty());
  // Wire in end block to look like a scheduler produced cfg.
  auto end_block = NewBlock();
  current_block_ = nullptr;
  sequence()->EndBlock(end_block->rpo_number());
463 464 465
  size_t offset = 0;
  for (const auto& completion : completions_) {
    switch (completion.type_) {
466 467 468 469
      case kBlockEnd: {
        auto block = instruction_blocks_[offset];
        block->successors().push_back(end_block->rpo_number());
        end_block->predecessors().push_back(block->rpo_number());
470
        break;
471
      }
472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496
      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 InstructionSequenceTest::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());
}


dcarney's avatar
dcarney committed
497 498 499 500
Instruction* InstructionSequenceTest::Emit(
    InstructionCode code, size_t outputs_size, InstructionOperand* outputs,
    size_t inputs_size, InstructionOperand* inputs, size_t temps_size,
    InstructionOperand* temps, bool is_call) {
501 502 503
  auto instruction = NewInstruction(code, outputs_size, outputs, inputs_size,
                                    inputs, temps_size, temps);
  if (is_call) instruction->MarkAsCall();
dcarney's avatar
dcarney committed
504
  return AddInstruction(instruction);
505 506 507
}


dcarney's avatar
dcarney committed
508
Instruction* InstructionSequenceTest::AddInstruction(Instruction* instruction) {
509
  sequence()->AddInstruction(instruction);
dcarney's avatar
dcarney committed
510
  return instruction;
511 512 513 514 515
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8