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.
5 #include "test/unittests/compiler/instruction-selector-unittest.h"
7 #include "src/compiler/graph-inl.h"
9 #include "test/unittests/compiler/compiler-test-utils.h"
17 typedef RawMachineAssembler::Label MLabel;
22 InstructionSelectorTest::InstructionSelectorTest() : rng_(FLAG_random_seed) {}
25 InstructionSelectorTest::~InstructionSelectorTest() {}
28 InstructionSelectorTest::Stream InstructionSelectorTest::StreamBuilder::Build(
29 InstructionSelector::Features features,
30 InstructionSelectorTest::StreamBuilderMode mode) {
31 Schedule* schedule = Export();
32 if (FLAG_trace_turbo) {
34 out << "=== Schedule before instruction selection ===" << std::endl
37 size_t const node_count = graph()->NodeCount();
38 EXPECT_NE(0u, node_count);
39 Linkage linkage(call_descriptor());
40 InstructionBlocks* instruction_blocks =
41 InstructionSequence::InstructionBlocksFor(test_->zone(), schedule);
42 InstructionSequence sequence(test_->isolate(), test_->zone(),
44 SourcePositionTable source_position_table(graph());
45 InstructionSelector selector(test_->zone(), node_count, &linkage, &sequence,
46 schedule, &source_position_table, features);
47 selector.SelectInstructions();
48 if (FLAG_trace_turbo) {
50 PrintableInstructionSequence printable = {
51 RegisterConfiguration::ArchDefault(), &sequence};
52 out << "=== Code sequence after instruction selection ===" << std::endl
56 s.virtual_registers_ = selector.GetVirtualRegistersForTesting();
57 // Map virtual registers.
58 for (Instruction* const instr : sequence) {
59 if (instr->opcode() < 0) continue;
60 if (mode == kTargetInstructions) {
61 switch (instr->arch_opcode()) {
65 TARGET_ARCH_OPCODE_LIST(CASE)
71 if (mode == kAllExceptNopInstructions && instr->arch_opcode() == kArchNop) {
74 for (size_t i = 0; i < instr->OutputCount(); ++i) {
75 InstructionOperand* output = instr->OutputAt(i);
76 EXPECT_NE(InstructionOperand::IMMEDIATE, output->kind());
77 if (output->IsConstant()) {
78 s.constants_.insert(std::make_pair(
79 output->index(), sequence.GetConstant(output->index())));
82 for (size_t i = 0; i < instr->InputCount(); ++i) {
83 InstructionOperand* input = instr->InputAt(i);
84 EXPECT_NE(InstructionOperand::CONSTANT, input->kind());
85 if (input->IsImmediate()) {
86 s.immediates_.insert(std::make_pair(
87 input->index(), sequence.GetImmediate(input->index())));
90 s.instructions_.push_back(instr);
92 for (auto i : s.virtual_registers_) {
93 int const virtual_register = i.second;
94 if (sequence.IsDouble(virtual_register)) {
95 EXPECT_FALSE(sequence.IsReference(virtual_register));
96 s.doubles_.insert(virtual_register);
98 if (sequence.IsReference(virtual_register)) {
99 EXPECT_FALSE(sequence.IsDouble(virtual_register));
100 s.references_.insert(virtual_register);
103 for (int i = 0; i < sequence.GetFrameStateDescriptorCount(); i++) {
104 s.deoptimization_entries_.push_back(sequence.GetFrameStateDescriptor(
105 InstructionSequence::StateId::FromInt(i)));
111 int InstructionSelectorTest::Stream::ToVreg(const Node* node) const {
112 VirtualRegisters::const_iterator i = virtual_registers_.find(node->id());
113 CHECK(i != virtual_registers_.end());
118 bool InstructionSelectorTest::Stream::IsFixed(const InstructionOperand* operand,
119 Register reg) const {
120 if (!operand->IsUnallocated()) return false;
121 const UnallocatedOperand* unallocated = UnallocatedOperand::cast(operand);
122 if (!unallocated->HasFixedRegisterPolicy()) return false;
123 const int index = Register::ToAllocationIndex(reg);
124 return unallocated->fixed_register_index() == index;
128 bool InstructionSelectorTest::Stream::IsSameAsFirst(
129 const InstructionOperand* operand) const {
130 if (!operand->IsUnallocated()) return false;
131 const UnallocatedOperand* unallocated = UnallocatedOperand::cast(operand);
132 return unallocated->HasSameAsInputPolicy();
136 bool InstructionSelectorTest::Stream::IsUsedAtStart(
137 const InstructionOperand* operand) const {
138 if (!operand->IsUnallocated()) return false;
139 const UnallocatedOperand* unallocated = UnallocatedOperand::cast(operand);
140 return unallocated->IsUsedAtStart();
144 // -----------------------------------------------------------------------------
148 TARGET_TEST_F(InstructionSelectorTest, ReturnFloat32Constant) {
149 const float kValue = 4.2f;
150 StreamBuilder m(this, kMachFloat32);
151 m.Return(m.Float32Constant(kValue));
152 Stream s = m.Build(kAllInstructions);
153 ASSERT_EQ(3U, s.size());
154 EXPECT_EQ(kArchNop, s[0]->arch_opcode());
155 ASSERT_EQ(InstructionOperand::CONSTANT, s[0]->OutputAt(0)->kind());
156 EXPECT_FLOAT_EQ(kValue, s.ToFloat32(s[0]->OutputAt(0)));
157 EXPECT_EQ(kArchRet, s[1]->arch_opcode());
158 EXPECT_EQ(1U, s[1]->InputCount());
162 TARGET_TEST_F(InstructionSelectorTest, ReturnParameter) {
163 StreamBuilder m(this, kMachInt32, kMachInt32);
164 m.Return(m.Parameter(0));
165 Stream s = m.Build(kAllInstructions);
166 ASSERT_EQ(3U, s.size());
167 EXPECT_EQ(kArchNop, s[0]->arch_opcode());
168 ASSERT_EQ(1U, s[0]->OutputCount());
169 EXPECT_EQ(kArchRet, s[1]->arch_opcode());
170 EXPECT_EQ(1U, s[1]->InputCount());
174 TARGET_TEST_F(InstructionSelectorTest, ReturnZero) {
175 StreamBuilder m(this, kMachInt32);
176 m.Return(m.Int32Constant(0));
177 Stream s = m.Build(kAllInstructions);
178 ASSERT_EQ(3U, s.size());
179 EXPECT_EQ(kArchNop, s[0]->arch_opcode());
180 ASSERT_EQ(1U, s[0]->OutputCount());
181 EXPECT_EQ(InstructionOperand::CONSTANT, s[0]->OutputAt(0)->kind());
182 EXPECT_EQ(0, s.ToInt32(s[0]->OutputAt(0)));
183 EXPECT_EQ(kArchRet, s[1]->arch_opcode());
184 EXPECT_EQ(1U, s[1]->InputCount());
188 // -----------------------------------------------------------------------------
192 TARGET_TEST_F(InstructionSelectorTest, TruncateFloat64ToInt32WithParameter) {
193 StreamBuilder m(this, kMachInt32, kMachFloat64);
194 m.Return(m.TruncateFloat64ToInt32(m.Parameter(0)));
195 Stream s = m.Build(kAllInstructions);
196 ASSERT_EQ(4U, s.size());
197 EXPECT_EQ(kArchNop, s[0]->arch_opcode());
198 EXPECT_EQ(kArchTruncateDoubleToI, s[1]->arch_opcode());
199 EXPECT_EQ(1U, s[1]->InputCount());
200 EXPECT_EQ(1U, s[1]->OutputCount());
201 EXPECT_EQ(kArchRet, s[2]->arch_opcode());
205 // -----------------------------------------------------------------------------
209 TARGET_TEST_F(InstructionSelectorTest, DoubleParameter) {
210 StreamBuilder m(this, kMachFloat64, kMachFloat64);
211 Node* param = m.Parameter(0);
213 Stream s = m.Build(kAllInstructions);
214 EXPECT_TRUE(s.IsDouble(param));
218 TARGET_TEST_F(InstructionSelectorTest, ReferenceParameter) {
219 StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged);
220 Node* param = m.Parameter(0);
222 Stream s = m.Build(kAllInstructions);
223 EXPECT_TRUE(s.IsReference(param));
227 // -----------------------------------------------------------------------------
231 TARGET_TEST_F(InstructionSelectorTest, Finish) {
232 StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged);
233 Node* param = m.Parameter(0);
234 Node* finish = m.NewNode(m.common()->Finish(1), param, m.graph()->start());
236 Stream s = m.Build(kAllInstructions);
237 ASSERT_EQ(4U, s.size());
238 EXPECT_EQ(kArchNop, s[0]->arch_opcode());
239 ASSERT_EQ(1U, s[0]->OutputCount());
240 ASSERT_TRUE(s[0]->Output()->IsUnallocated());
241 EXPECT_EQ(s.ToVreg(param), s.ToVreg(s[0]->Output()));
242 EXPECT_EQ(kArchNop, s[1]->arch_opcode());
243 ASSERT_EQ(1U, s[1]->InputCount());
244 ASSERT_TRUE(s[1]->InputAt(0)->IsUnallocated());
245 EXPECT_EQ(s.ToVreg(param), s.ToVreg(s[1]->InputAt(0)));
246 ASSERT_EQ(1U, s[1]->OutputCount());
247 ASSERT_TRUE(s[1]->Output()->IsUnallocated());
248 EXPECT_TRUE(UnallocatedOperand::cast(s[1]->Output())->HasSameAsInputPolicy());
249 EXPECT_EQ(s.ToVreg(finish), s.ToVreg(s[1]->Output()));
250 EXPECT_TRUE(s.IsReference(finish));
254 // -----------------------------------------------------------------------------
258 typedef InstructionSelectorTestWithParam<MachineType>
259 InstructionSelectorPhiTest;
262 TARGET_TEST_P(InstructionSelectorPhiTest, Doubleness) {
263 const MachineType type = GetParam();
264 StreamBuilder m(this, type, type, type);
265 Node* param0 = m.Parameter(0);
266 Node* param1 = m.Parameter(1);
268 m.Branch(m.Int32Constant(0), &a, &b);
274 Node* phi = m.Phi(type, param0, param1);
276 Stream s = m.Build(kAllInstructions);
277 EXPECT_EQ(s.IsDouble(phi), s.IsDouble(param0));
278 EXPECT_EQ(s.IsDouble(phi), s.IsDouble(param1));
282 TARGET_TEST_P(InstructionSelectorPhiTest, Referenceness) {
283 const MachineType type = GetParam();
284 StreamBuilder m(this, type, type, type);
285 Node* param0 = m.Parameter(0);
286 Node* param1 = m.Parameter(1);
288 m.Branch(m.Int32Constant(1), &a, &b);
294 Node* phi = m.Phi(type, param0, param1);
296 Stream s = m.Build(kAllInstructions);
297 EXPECT_EQ(s.IsReference(phi), s.IsReference(param0));
298 EXPECT_EQ(s.IsReference(phi), s.IsReference(param1));
302 INSTANTIATE_TEST_CASE_P(InstructionSelectorTest, InstructionSelectorPhiTest,
303 ::testing::Values(kMachFloat64, kMachInt8, kMachUint8,
304 kMachInt16, kMachUint16, kMachInt32,
305 kMachUint32, kMachInt64, kMachUint64,
306 kMachPtr, kMachAnyTagged));
309 // -----------------------------------------------------------------------------
313 TARGET_TEST_F(InstructionSelectorTest, ValueEffect) {
314 StreamBuilder m1(this, kMachInt32, kMachPtr);
315 Node* p1 = m1.Parameter(0);
316 m1.Return(m1.Load(kMachInt32, p1, m1.Int32Constant(0)));
317 Stream s1 = m1.Build(kAllInstructions);
318 StreamBuilder m2(this, kMachInt32, kMachPtr);
319 Node* p2 = m2.Parameter(0);
320 m2.Return(m2.NewNode(m2.machine()->Load(kMachInt32), p2, m2.Int32Constant(0),
321 m2.NewNode(m2.common()->ValueEffect(1), p2)));
322 Stream s2 = m2.Build(kAllInstructions);
323 EXPECT_LE(3U, s1.size());
324 ASSERT_EQ(s1.size(), s2.size());
325 TRACED_FORRANGE(size_t, i, 0, s1.size() - 1) {
326 const Instruction* i1 = s1[i];
327 const Instruction* i2 = s2[i];
328 EXPECT_EQ(i1->arch_opcode(), i2->arch_opcode());
329 EXPECT_EQ(i1->InputCount(), i2->InputCount());
330 EXPECT_EQ(i1->OutputCount(), i2->OutputCount());
335 // -----------------------------------------------------------------------------
336 // Calls with deoptimization.
339 TARGET_TEST_F(InstructionSelectorTest, CallJSFunctionWithDeopt) {
340 StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged, kMachAnyTagged,
343 BailoutId bailout_id(42);
345 Node* function_node = m.Parameter(0);
346 Node* receiver = m.Parameter(1);
347 Node* context = m.Parameter(2);
349 Node* parameters = m.NewNode(m.common()->StateValues(1), m.Int32Constant(1));
350 Node* locals = m.NewNode(m.common()->StateValues(0));
351 Node* stack = m.NewNode(m.common()->StateValues(0));
352 Node* context_dummy = m.Int32Constant(0);
354 Node* state_node = m.NewNode(
355 m.common()->FrameState(JS_FRAME, bailout_id,
356 OutputFrameStateCombine::Push()),
357 parameters, locals, stack, context_dummy, m.UndefinedConstant());
358 Node* call = m.CallJS0(function_node, receiver, context, state_node);
361 Stream s = m.Build(kAllExceptNopInstructions);
363 // Skip until kArchCallJSFunction.
365 for (; index < s.size() && s[index]->arch_opcode() != kArchCallJSFunction;
368 // Now we should have two instructions: call and return.
369 ASSERT_EQ(index + 2, s.size());
371 EXPECT_EQ(kArchCallJSFunction, s[index++]->arch_opcode());
372 EXPECT_EQ(kArchRet, s[index++]->arch_opcode());
374 // TODO(jarin) Check deoptimization table.
378 TARGET_TEST_F(InstructionSelectorTest, CallFunctionStubWithDeopt) {
379 StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged, kMachAnyTagged,
382 BailoutId bailout_id_before(42);
384 // Some arguments for the call node.
385 Node* function_node = m.Parameter(0);
386 Node* receiver = m.Parameter(1);
387 Node* context = m.Int32Constant(1); // Context is ignored.
389 // Build frame state for the state before the call.
390 Node* parameters = m.NewNode(m.common()->StateValues(1), m.Int32Constant(43));
391 Node* locals = m.NewNode(m.common()->StateValues(1), m.Float64Constant(0.5));
392 Node* stack = m.NewNode(m.common()->StateValues(1), m.UndefinedConstant());
394 Node* context_sentinel = m.Int32Constant(0);
395 Node* frame_state_before = m.NewNode(
396 m.common()->FrameState(JS_FRAME, bailout_id_before,
397 OutputFrameStateCombine::Push()),
398 parameters, locals, stack, context_sentinel, m.UndefinedConstant());
401 Node* call = m.CallFunctionStub0(function_node, receiver, context,
402 frame_state_before, CALL_AS_METHOD);
406 Stream s = m.Build(kAllExceptNopInstructions);
408 // Skip until kArchCallJSFunction.
410 for (; index < s.size() && s[index]->arch_opcode() != kArchCallCodeObject;
413 // Now we should have two instructions: call, return.
414 ASSERT_EQ(index + 2, s.size());
416 // Check the call instruction
417 const Instruction* call_instr = s[index++];
418 EXPECT_EQ(kArchCallCodeObject, call_instr->arch_opcode());
419 size_t num_operands =
422 4 + // Frame state deopt id + one input for each value in frame state.
425 ASSERT_EQ(num_operands, call_instr->InputCount());
428 EXPECT_TRUE(call_instr->InputAt(0)->IsImmediate());
430 // Deoptimization id.
431 int32_t deopt_id_before = s.ToInt32(call_instr->InputAt(1));
432 FrameStateDescriptor* desc_before =
433 s.GetFrameStateDescriptor(deopt_id_before);
434 EXPECT_EQ(bailout_id_before, desc_before->bailout_id());
435 EXPECT_EQ(OutputFrameStateCombine::kPushOutput,
436 desc_before->state_combine().kind());
437 EXPECT_EQ(1u, desc_before->parameters_count());
438 EXPECT_EQ(1u, desc_before->locals_count());
439 EXPECT_EQ(1u, desc_before->stack_count());
440 EXPECT_EQ(43, s.ToInt32(call_instr->InputAt(2)));
441 EXPECT_EQ(0, s.ToInt32(call_instr->InputAt(3))); // This should be a context.
442 // We inserted 0 here.
443 EXPECT_EQ(0.5, s.ToFloat64(call_instr->InputAt(4)));
444 EXPECT_TRUE(s.ToHeapObject(call_instr->InputAt(5))->IsUndefined());
445 EXPECT_EQ(kMachInt32, desc_before->GetType(0));
446 EXPECT_EQ(kMachAnyTagged, desc_before->GetType(1)); // context is always
448 EXPECT_EQ(kMachFloat64, desc_before->GetType(2));
449 EXPECT_EQ(kMachAnyTagged, desc_before->GetType(3));
452 EXPECT_EQ(s.ToVreg(function_node), s.ToVreg(call_instr->InputAt(6)));
454 EXPECT_EQ(s.ToVreg(context), s.ToVreg(call_instr->InputAt(7)));
456 EXPECT_EQ(kArchRet, s[index++]->arch_opcode());
458 EXPECT_EQ(index, s.size());
462 TARGET_TEST_F(InstructionSelectorTest,
463 CallFunctionStubDeoptRecursiveFrameState) {
464 StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged, kMachAnyTagged,
467 BailoutId bailout_id_before(42);
468 BailoutId bailout_id_parent(62);
470 // Some arguments for the call node.
471 Node* function_node = m.Parameter(0);
472 Node* receiver = m.Parameter(1);
473 Node* context = m.Int32Constant(66);
475 // Build frame state for the state before the call.
476 Node* parameters = m.NewNode(m.common()->StateValues(1), m.Int32Constant(63));
477 Node* locals = m.NewNode(m.common()->StateValues(1), m.Int32Constant(64));
478 Node* stack = m.NewNode(m.common()->StateValues(1), m.Int32Constant(65));
479 Node* frame_state_parent =
480 m.NewNode(m.common()->FrameState(JS_FRAME, bailout_id_parent,
481 OutputFrameStateCombine::Ignore()),
482 parameters, locals, stack, context, m.UndefinedConstant());
484 Node* context2 = m.Int32Constant(46);
486 m.NewNode(m.common()->StateValues(1), m.Int32Constant(43));
488 m.NewNode(m.common()->StateValues(1), m.Float64Constant(0.25));
489 Node* stack2 = m.NewNode(m.common()->StateValues(2), m.Int32Constant(44),
490 m.Int32Constant(45));
491 Node* frame_state_before =
492 m.NewNode(m.common()->FrameState(JS_FRAME, bailout_id_before,
493 OutputFrameStateCombine::Push()),
494 parameters2, locals2, stack2, context2, frame_state_parent);
497 Node* call = m.CallFunctionStub0(function_node, receiver, context2,
498 frame_state_before, CALL_AS_METHOD);
502 Stream s = m.Build(kAllExceptNopInstructions);
504 // Skip until kArchCallJSFunction.
506 for (; index < s.size() && s[index]->arch_opcode() != kArchCallCodeObject;
509 // Now we should have three instructions: call, return.
510 EXPECT_EQ(index + 2, s.size());
512 // Check the call instruction
513 const Instruction* call_instr = s[index++];
514 EXPECT_EQ(kArchCallCodeObject, call_instr->arch_opcode());
515 size_t num_operands =
517 1 + // Frame state deopt id
518 5 + // One input for each value in frame state + context.
519 4 + // One input for each value in the parent frame state + context.
522 EXPECT_EQ(num_operands, call_instr->InputCount());
524 EXPECT_TRUE(call_instr->InputAt(0)->IsImmediate());
526 // Deoptimization id.
527 int32_t deopt_id_before = s.ToInt32(call_instr->InputAt(1));
528 FrameStateDescriptor* desc_before =
529 s.GetFrameStateDescriptor(deopt_id_before);
530 FrameStateDescriptor* desc_before_outer = desc_before->outer_state();
531 EXPECT_EQ(bailout_id_before, desc_before->bailout_id());
532 EXPECT_EQ(1u, desc_before_outer->parameters_count());
533 EXPECT_EQ(1u, desc_before_outer->locals_count());
534 EXPECT_EQ(1u, desc_before_outer->stack_count());
535 // Values from parent environment.
536 EXPECT_EQ(63, s.ToInt32(call_instr->InputAt(2)));
537 EXPECT_EQ(kMachInt32, desc_before_outer->GetType(0));
539 EXPECT_EQ(66, s.ToInt32(call_instr->InputAt(3)));
540 EXPECT_EQ(kMachAnyTagged, desc_before_outer->GetType(1));
541 EXPECT_EQ(64, s.ToInt32(call_instr->InputAt(4)));
542 EXPECT_EQ(kMachInt32, desc_before_outer->GetType(2));
543 EXPECT_EQ(65, s.ToInt32(call_instr->InputAt(5)));
544 EXPECT_EQ(kMachInt32, desc_before_outer->GetType(3));
545 // Values from the nested frame.
546 EXPECT_EQ(1u, desc_before->parameters_count());
547 EXPECT_EQ(1u, desc_before->locals_count());
548 EXPECT_EQ(2u, desc_before->stack_count());
549 EXPECT_EQ(43, s.ToInt32(call_instr->InputAt(6)));
550 EXPECT_EQ(kMachInt32, desc_before->GetType(0));
551 EXPECT_EQ(46, s.ToInt32(call_instr->InputAt(7)));
552 EXPECT_EQ(kMachAnyTagged, desc_before->GetType(1));
553 EXPECT_EQ(0.25, s.ToFloat64(call_instr->InputAt(8)));
554 EXPECT_EQ(kMachFloat64, desc_before->GetType(2));
555 EXPECT_EQ(44, s.ToInt32(call_instr->InputAt(9)));
556 EXPECT_EQ(kMachInt32, desc_before->GetType(3));
557 EXPECT_EQ(45, s.ToInt32(call_instr->InputAt(10)));
558 EXPECT_EQ(kMachInt32, desc_before->GetType(4));
561 EXPECT_EQ(s.ToVreg(function_node), s.ToVreg(call_instr->InputAt(11)));
563 EXPECT_EQ(s.ToVreg(context2), s.ToVreg(call_instr->InputAt(12)));
566 EXPECT_EQ(kArchRet, s[index++]->arch_opcode());
567 EXPECT_EQ(index, s.size());
570 } // namespace compiler
571 } // namespace internal