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