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