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