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