deps/v8/test/unittests/compiler/instruction-sequence-unittest.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/base/utils/random-number-generator.h"
   6 #include "src/compiler/pipeline.h"
   7 #include "test/unittests/compiler/instruction-sequence-unittest.h"
   8 #include "test/unittests/test-utils.h"
   9 #include "testing/gmock/include/gmock/gmock.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13 namespace compiler {
  14
  15 static const char*
  16     general_register_names_[RegisterConfiguration::kMaxGeneralRegisters];
  17 static const char*
  18     double_register_names_[RegisterConfiguration::kMaxDoubleRegisters];
  19 static char register_names_[10 * (RegisterConfiguration::kMaxGeneralRegisters +
  20                                   RegisterConfiguration::kMaxDoubleRegisters)];
  21
  22
  23 static void InitializeRegisterNames() {
  24   char* loc = register_names_;
  25   for (int i = 0; i < RegisterConfiguration::kMaxGeneralRegisters; ++i) {
  26     general_register_names_[i] = loc;
  27     loc += base::OS::SNPrintF(loc, 100, "gp_%d", i);
  28     *loc++ = 0;
  29   }
  30   for (int i = 0; i < RegisterConfiguration::kMaxDoubleRegisters; ++i) {
  31     double_register_names_[i] = loc;
  32     loc += base::OS::SNPrintF(loc, 100, "fp_%d", i) + 1;
  33     *loc++ = 0;
  34   }
  35 }
  36
  37
  38 InstructionSequenceTest::InstructionSequenceTest()
  39     : sequence_(nullptr),
  40       num_general_registers_(kDefaultNRegs),
  41       num_double_registers_(kDefaultNRegs),
  42       instruction_blocks_(zone()),
  43       current_block_(nullptr),
  44       block_returns_(false) {
  45   InitializeRegisterNames();
  46 }
  47
  48
  49 void InstructionSequenceTest::SetNumRegs(int num_general_registers,
  50                                          int num_double_registers) {
  51   CHECK(config_.is_empty());
  52   CHECK(instructions_.empty());
  53   CHECK(instruction_blocks_.empty());
  54   num_general_registers_ = num_general_registers;
  55   num_double_registers_ = num_double_registers;
  56 }
  57
  58
  59 RegisterConfiguration* InstructionSequenceTest::config() {
  60   if (config_.is_empty()) {
  61     config_.Reset(new RegisterConfiguration(
  62         num_general_registers_, num_double_registers_, num_double_registers_,
  63         general_register_names_, double_register_names_));
  64   }
  65   return config_.get();
  66 }
  67
  68
  69 InstructionSequence* InstructionSequenceTest::sequence() {
  70   if (sequence_ == nullptr) {
  71     sequence_ = new (zone())
  72         InstructionSequence(isolate(), zone(), &instruction_blocks_);
  73   }
  74   return sequence_;
  75 }
  76
  77
  78 void InstructionSequenceTest::StartLoop(int loop_blocks) {
  79   CHECK(current_block_ == nullptr);
  80   if (!loop_blocks_.empty()) {
  81     CHECK(!loop_blocks_.back().loop_header_.IsValid());
  82   }
  83   LoopData loop_data = {Rpo::Invalid(), loop_blocks};
  84   loop_blocks_.push_back(loop_data);
  85 }
  86
  87
  88 void InstructionSequenceTest::EndLoop() {
  89   CHECK(current_block_ == nullptr);
  90   CHECK(!loop_blocks_.empty());
  91   CHECK_EQ(0, loop_blocks_.back().expected_blocks_);
  92   loop_blocks_.pop_back();
  93 }
  94
  95
  96 void InstructionSequenceTest::StartBlock() {
  97   block_returns_ = false;
  98   NewBlock();
  99 }
 100
 101
 102 Instruction* InstructionSequenceTest::EndBlock(BlockCompletion completion) {
 103   Instruction* result = nullptr;
 104   if (block_returns_) {
 105     CHECK(completion.type_ == kBlockEnd || completion.type_ == kFallThrough);
 106     completion.type_ = kBlockEnd;
 107   }
 108   switch (completion.type_) {
 109     case kBlockEnd:
 110       break;
 111     case kFallThrough:
 112       result = EmitFallThrough();
 113       break;
 114     case kJump:
 115       CHECK(!block_returns_);
 116       result = EmitJump();
 117       break;
 118     case kBranch:
 119       CHECK(!block_returns_);
 120       result = EmitBranch(completion.op_);
 121       break;
 122   }
 123   completions_.push_back(completion);
 124   CHECK(current_block_ != nullptr);
 125   sequence()->EndBlock(current_block_->rpo_number());
 126   current_block_ = nullptr;
 127   return result;
 128 }
 129
 130
 131 InstructionSequenceTest::TestOperand InstructionSequenceTest::Imm(int32_t imm) {
 132   int index = sequence()->AddImmediate(Constant(imm));
 133   return TestOperand(kImmediate, index);
 134 }
 135
 136
 137 InstructionSequenceTest::VReg InstructionSequenceTest::Define(
 138     TestOperand output_op) {
 139   VReg vreg = NewReg();
 140   InstructionOperand outputs[1]{ConvertOutputOp(vreg, output_op)};
 141   Emit(kArchNop, 1, outputs);
 142   return vreg;
 143 }
 144
 145
 146 Instruction* InstructionSequenceTest::Return(TestOperand input_op_0) {
 147   block_returns_ = true;
 148   InstructionOperand inputs[1]{ConvertInputOp(input_op_0)};
 149   return Emit(kArchRet, 0, nullptr, 1, inputs);
 150 }
 151
 152
 153 PhiInstruction* InstructionSequenceTest::Phi(VReg incoming_vreg_0,
 154                                              VReg incoming_vreg_1,
 155                                              VReg incoming_vreg_2,
 156                                              VReg incoming_vreg_3) {
 157   VReg inputs[] = {incoming_vreg_0, incoming_vreg_1, incoming_vreg_2,
 158                    incoming_vreg_3};
 159   size_t input_count = 0;
 160   for (; input_count < arraysize(inputs); ++input_count) {
 161     if (inputs[input_count].value_ == kNoValue) break;
 162   }
 163   CHECK(input_count > 0);
 164   auto phi = new (zone()) PhiInstruction(zone(), NewReg().value_, input_count);
 165   for (size_t i = 0; i < input_count; ++i) {
 166     SetInput(phi, i, inputs[i]);
 167   }
 168   current_block_->AddPhi(phi);
 169   return phi;
 170 }
 171
 172
 173 PhiInstruction* InstructionSequenceTest::Phi(VReg incoming_vreg_0,
 174                                              size_t input_count) {
 175   auto phi = new (zone()) PhiInstruction(zone(), NewReg().value_, input_count);
 176   SetInput(phi, 0, incoming_vreg_0);
 177   current_block_->AddPhi(phi);
 178   return phi;
 179 }
 180
 181
 182 void InstructionSequenceTest::SetInput(PhiInstruction* phi, size_t input,
 183                                        VReg vreg) {
 184   CHECK(vreg.value_ != kNoValue);
 185   phi->SetInput(input, vreg.value_);
 186 }
 187
 188
 189 InstructionSequenceTest::VReg InstructionSequenceTest::DefineConstant(
 190     int32_t imm) {
 191   VReg vreg = NewReg();
 192   sequence()->AddConstant(vreg.value_, Constant(imm));
 193   InstructionOperand outputs[1]{ConstantOperand(vreg.value_)};
 194   Emit(kArchNop, 1, outputs);
 195   return vreg;
 196 }
 197
 198
 199 Instruction* InstructionSequenceTest::EmitNop() { return Emit(kArchNop); }
 200
 201
 202 static size_t CountInputs(size_t size,
 203                           InstructionSequenceTest::TestOperand* inputs) {
 204   size_t i = 0;
 205   for (; i < size; ++i) {
 206     if (inputs[i].type_ == InstructionSequenceTest::kInvalid) break;
 207   }
 208   return i;
 209 }
 210
 211
 212 Instruction* InstructionSequenceTest::EmitI(size_t input_size,
 213                                             TestOperand* inputs) {
 214   InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
 215   return Emit(kArchNop, 0, nullptr, input_size, mapped_inputs);
 216 }
 217
 218
 219 Instruction* InstructionSequenceTest::EmitI(TestOperand input_op_0,
 220                                             TestOperand input_op_1,
 221                                             TestOperand input_op_2,
 222                                             TestOperand input_op_3) {
 223   TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
 224   return EmitI(CountInputs(arraysize(inputs), inputs), inputs);
 225 }
 226
 227
 228 InstructionSequenceTest::VReg InstructionSequenceTest::EmitOI(
 229     TestOperand output_op, size_t input_size, TestOperand* inputs) {
 230   VReg output_vreg = NewReg();
 231   InstructionOperand outputs[1]{ConvertOutputOp(output_vreg, output_op)};
 232   InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
 233   Emit(kArchNop, 1, outputs, input_size, mapped_inputs);
 234   return output_vreg;
 235 }
 236
 237
 238 InstructionSequenceTest::VReg InstructionSequenceTest::EmitOI(
 239     TestOperand output_op, TestOperand input_op_0, TestOperand input_op_1,
 240     TestOperand input_op_2, TestOperand input_op_3) {
 241   TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
 242   return EmitOI(output_op, CountInputs(arraysize(inputs), inputs), inputs);
 243 }
 244
 245
 246 InstructionSequenceTest::VRegPair InstructionSequenceTest::EmitOOI(
 247     TestOperand output_op_0, TestOperand output_op_1, size_t input_size,
 248     TestOperand* inputs) {
 249   VRegPair output_vregs = std::make_pair(NewReg(), NewReg());
 250   InstructionOperand outputs[2]{
 251       ConvertOutputOp(output_vregs.first, output_op_0),
 252       ConvertOutputOp(output_vregs.second, output_op_1)};
 253   InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
 254   Emit(kArchNop, 2, outputs, input_size, mapped_inputs);
 255   return output_vregs;
 256 }
 257
 258
 259 InstructionSequenceTest::VRegPair InstructionSequenceTest::EmitOOI(
 260     TestOperand output_op_0, TestOperand output_op_1, TestOperand input_op_0,
 261     TestOperand input_op_1, TestOperand input_op_2, TestOperand input_op_3) {
 262   TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
 263   return EmitOOI(output_op_0, output_op_1,
 264                  CountInputs(arraysize(inputs), inputs), inputs);
 265 }
 266
 267
 268 InstructionSequenceTest::VReg InstructionSequenceTest::EmitCall(
 269     TestOperand output_op, size_t input_size, TestOperand* inputs) {
 270   VReg output_vreg = NewReg();
 271   InstructionOperand outputs[1]{ConvertOutputOp(output_vreg, output_op)};
 272   CHECK(UnallocatedOperand::cast(outputs[0]).HasFixedPolicy());
 273   InstructionOperand* mapped_inputs = ConvertInputs(input_size, inputs);
 274   Emit(kArchCallCodeObject, 1, outputs, input_size, mapped_inputs, 0, nullptr,
 275        true);
 276   return output_vreg;
 277 }
 278
 279
 280 InstructionSequenceTest::VReg InstructionSequenceTest::EmitCall(
 281     TestOperand output_op, TestOperand input_op_0, TestOperand input_op_1,
 282     TestOperand input_op_2, TestOperand input_op_3) {
 283   TestOperand inputs[] = {input_op_0, input_op_1, input_op_2, input_op_3};
 284   return EmitCall(output_op, CountInputs(arraysize(inputs), inputs), inputs);
 285 }
 286
 287
 288 Instruction* InstructionSequenceTest::EmitBranch(TestOperand input_op) {
 289   InstructionOperand inputs[4]{ConvertInputOp(input_op), ConvertInputOp(Imm()),
 290                                ConvertInputOp(Imm()), ConvertInputOp(Imm())};
 291   InstructionCode opcode = kArchJmp | FlagsModeField::encode(kFlags_branch) |
 292                            FlagsConditionField::encode(kEqual);
 293   auto instruction = NewInstruction(opcode, 0, nullptr, 4, inputs);
 294   return AddInstruction(instruction);
 295 }
 296
 297
 298 Instruction* InstructionSequenceTest::EmitFallThrough() {
 299   auto instruction = NewInstruction(kArchNop, 0, nullptr);
 300   return AddInstruction(instruction);
 301 }
 302
 303
 304 Instruction* InstructionSequenceTest::EmitJump() {
 305   InstructionOperand inputs[1]{ConvertInputOp(Imm())};
 306   auto instruction = NewInstruction(kArchJmp, 0, nullptr, 1, inputs);
 307   return AddInstruction(instruction);
 308 }
 309
 310
 311 Instruction* InstructionSequenceTest::NewInstruction(
 312     InstructionCode code, size_t outputs_size, InstructionOperand* outputs,
 313     size_t inputs_size, InstructionOperand* inputs, size_t temps_size,
 314     InstructionOperand* temps) {
 315   CHECK(current_block_);
 316   return Instruction::New(zone(), code, outputs_size, outputs, inputs_size,
 317                           inputs, temps_size, temps);
 318 }
 319
 320
 321 InstructionOperand InstructionSequenceTest::Unallocated(
 322     TestOperand op, UnallocatedOperand::ExtendedPolicy policy) {
 323   return UnallocatedOperand(policy, op.vreg_.value_);
 324 }
 325
 326
 327 InstructionOperand InstructionSequenceTest::Unallocated(
 328     TestOperand op, UnallocatedOperand::ExtendedPolicy policy,
 329     UnallocatedOperand::Lifetime lifetime) {
 330   return UnallocatedOperand(policy, lifetime, op.vreg_.value_);
 331 }
 332
 333
 334 InstructionOperand InstructionSequenceTest::Unallocated(
 335     TestOperand op, UnallocatedOperand::ExtendedPolicy policy, int index) {
 336   return UnallocatedOperand(policy, index, op.vreg_.value_);
 337 }
 338
 339
 340 InstructionOperand InstructionSequenceTest::Unallocated(
 341     TestOperand op, UnallocatedOperand::BasicPolicy policy, int index) {
 342   return UnallocatedOperand(policy, index, op.vreg_.value_);
 343 }
 344
 345
 346 InstructionOperand* InstructionSequenceTest::ConvertInputs(
 347     size_t input_size, TestOperand* inputs) {
 348   InstructionOperand* mapped_inputs =
 349       zone()->NewArray<InstructionOperand>(static_cast<int>(input_size));
 350   for (size_t i = 0; i < input_size; ++i) {
 351     mapped_inputs[i] = ConvertInputOp(inputs[i]);
 352   }
 353   return mapped_inputs;
 354 }
 355
 356
 357 InstructionOperand InstructionSequenceTest::ConvertInputOp(TestOperand op) {
 358   if (op.type_ == kImmediate) {
 359     CHECK_EQ(op.vreg_.value_, kNoValue);
 360     return ImmediateOperand(op.value_);
 361   }
 362   CHECK_NE(op.vreg_.value_, kNoValue);
 363   switch (op.type_) {
 364     case kNone:
 365       return Unallocated(op, UnallocatedOperand::NONE,
 366                          UnallocatedOperand::USED_AT_START);
 367     case kUnique:
 368       return Unallocated(op, UnallocatedOperand::NONE);
 369     case kUniqueRegister:
 370       return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER);
 371     case kRegister:
 372       return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER,
 373                          UnallocatedOperand::USED_AT_START);
 374     case kSlot:
 375       return Unallocated(op, UnallocatedOperand::MUST_HAVE_SLOT,
 376                          UnallocatedOperand::USED_AT_START);
 377     case kFixedRegister:
 378       CHECK(0 <= op.value_ && op.value_ < num_general_registers_);
 379       return Unallocated(op, UnallocatedOperand::FIXED_REGISTER, op.value_);
 380     case kFixedSlot:
 381       return Unallocated(op, UnallocatedOperand::FIXED_SLOT, op.value_);
 382     default:
 383       break;
 384   }
 385   CHECK(false);
 386   return InstructionOperand();
 387 }
 388
 389
 390 InstructionOperand InstructionSequenceTest::ConvertOutputOp(VReg vreg,
 391                                                             TestOperand op) {
 392   CHECK_EQ(op.vreg_.value_, kNoValue);
 393   op.vreg_ = vreg;
 394   switch (op.type_) {
 395     case kSameAsFirst:
 396       return Unallocated(op, UnallocatedOperand::SAME_AS_FIRST_INPUT);
 397     case kRegister:
 398       return Unallocated(op, UnallocatedOperand::MUST_HAVE_REGISTER);
 399     case kFixedSlot:
 400       return Unallocated(op, UnallocatedOperand::FIXED_SLOT, op.value_);
 401     case kFixedRegister:
 402       CHECK(0 <= op.value_ && op.value_ < num_general_registers_);
 403       return Unallocated(op, UnallocatedOperand::FIXED_REGISTER, op.value_);
 404     default:
 405       break;
 406   }
 407   CHECK(false);
 408   return InstructionOperand();
 409 }
 410
 411
 412 InstructionBlock* InstructionSequenceTest::NewBlock() {
 413   CHECK(current_block_ == nullptr);
 414   Rpo rpo = Rpo::FromInt(static_cast<int>(instruction_blocks_.size()));
 415   Rpo loop_header = Rpo::Invalid();
 416   Rpo loop_end = Rpo::Invalid();
 417   if (!loop_blocks_.empty()) {
 418     auto& loop_data = loop_blocks_.back();
 419     // This is a loop header.
 420     if (!loop_data.loop_header_.IsValid()) {
 421       loop_end = Rpo::FromInt(rpo.ToInt() + loop_data.expected_blocks_);
 422       loop_data.expected_blocks_--;
 423       loop_data.loop_header_ = rpo;
 424     } else {
 425       // This is a loop body.
 426       CHECK_NE(0, loop_data.expected_blocks_);
 427       // TODO(dcarney): handle nested loops.
 428       loop_data.expected_blocks_--;
 429       loop_header = loop_data.loop_header_;
 430     }
 431   }
 432   // Construct instruction block.
 433   auto instruction_block =
 434       new (zone()) InstructionBlock(zone(), rpo, loop_header, loop_end, false);
 435   instruction_blocks_.push_back(instruction_block);
 436   current_block_ = instruction_block;
 437   sequence()->StartBlock(rpo);
 438   return instruction_block;
 439 }
 440
 441
 442 void InstructionSequenceTest::WireBlocks() {
 443   CHECK(!current_block());
 444   CHECK(instruction_blocks_.size() == completions_.size());
 445   size_t offset = 0;
 446   for (const auto& completion : completions_) {
 447     switch (completion.type_) {
 448       case kBlockEnd:
 449         break;
 450       case kFallThrough:  // Fallthrough.
 451       case kJump:
 452         WireBlock(offset, completion.offset_0_);
 453         break;
 454       case kBranch:
 455         WireBlock(offset, completion.offset_0_);
 456         WireBlock(offset, completion.offset_1_);
 457         break;
 458     }
 459     ++offset;
 460   }
 461 }
 462
 463
 464 void InstructionSequenceTest::WireBlock(size_t block_offset, int jump_offset) {
 465   size_t target_block_offset = block_offset + static_cast<size_t>(jump_offset);
 466   CHECK(block_offset < instruction_blocks_.size());
 467   CHECK(target_block_offset < instruction_blocks_.size());
 468   auto block = instruction_blocks_[block_offset];
 469   auto target = instruction_blocks_[target_block_offset];
 470   block->successors().push_back(target->rpo_number());
 471   target->predecessors().push_back(block->rpo_number());
 472 }
 473
 474
 475 Instruction* InstructionSequenceTest::Emit(
 476     InstructionCode code, size_t outputs_size, InstructionOperand* outputs,
 477     size_t inputs_size, InstructionOperand* inputs, size_t temps_size,
 478     InstructionOperand* temps, bool is_call) {
 479   auto instruction = NewInstruction(code, outputs_size, outputs, inputs_size,
 480                                     inputs, temps_size, temps);
 481   if (is_call) instruction->MarkAsCall();
 482   return AddInstruction(instruction);
 483 }
 484
 485
 486 Instruction* InstructionSequenceTest::AddInstruction(Instruction* instruction) {
 487   sequence()->AddInstruction(instruction);
 488   return instruction;
 489 }
 490
 491 }  // namespace compiler
 492 }  // namespace internal
 493 }  // namespace v8