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