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/compiler/instruction-selector-unittest.h"
6
7#include "src/compiler/compiler-test-utils.h"
8#include "src/flags.h"
9
10namespace v8 {
11namespace internal {
12namespace compiler {
13
14namespace {
15
16typedef RawMachineAssembler::Label MLabel;
17
18}  // namespace
19
20
21InstructionSelectorTest::InstructionSelectorTest() : rng_(FLAG_random_seed) {}
22
23
24InstructionSelectorTest::~InstructionSelectorTest() {}
25
26
27InstructionSelectorTest::Stream InstructionSelectorTest::StreamBuilder::Build(
28    InstructionSelector::Features features,
29    InstructionSelectorTest::StreamBuilderMode mode) {
30  Schedule* schedule = Export();
31  if (FLAG_trace_turbo) {
32    OFStream out(stdout);
33    out << "=== Schedule before instruction selection ===" << endl << *schedule;
34  }
35  EXPECT_NE(0, graph()->NodeCount());
36  CompilationInfo info(test_->isolate(), test_->zone());
37  Linkage linkage(&info, call_descriptor());
38  InstructionSequence sequence(&linkage, graph(), schedule);
39  SourcePositionTable source_position_table(graph());
40  InstructionSelector selector(&sequence, &source_position_table, features);
41  selector.SelectInstructions();
42  if (FLAG_trace_turbo) {
43    OFStream out(stdout);
44    out << "=== Code sequence after instruction selection ===" << endl
45        << sequence;
46  }
47  Stream s;
48  std::set<int> virtual_registers;
49  for (InstructionSequence::const_iterator i = sequence.begin();
50       i != sequence.end(); ++i) {
51    Instruction* instr = *i;
52    if (instr->opcode() < 0) continue;
53    if (mode == kTargetInstructions) {
54      switch (instr->arch_opcode()) {
55#define CASE(Name) \
56  case k##Name:    \
57    break;
58        TARGET_ARCH_OPCODE_LIST(CASE)
59#undef CASE
60        default:
61          continue;
62      }
63    }
64    if (mode == kAllExceptNopInstructions && instr->arch_opcode() == kArchNop) {
65      continue;
66    }
67    for (size_t i = 0; i < instr->OutputCount(); ++i) {
68      InstructionOperand* output = instr->OutputAt(i);
69      EXPECT_NE(InstructionOperand::IMMEDIATE, output->kind());
70      if (output->IsConstant()) {
71        s.constants_.insert(std::make_pair(
72            output->index(), sequence.GetConstant(output->index())));
73        virtual_registers.insert(output->index());
74      } else if (output->IsUnallocated()) {
75        virtual_registers.insert(
76            UnallocatedOperand::cast(output)->virtual_register());
77      }
78    }
79    for (size_t i = 0; i < instr->InputCount(); ++i) {
80      InstructionOperand* input = instr->InputAt(i);
81      EXPECT_NE(InstructionOperand::CONSTANT, input->kind());
82      if (input->IsImmediate()) {
83        s.immediates_.insert(std::make_pair(
84            input->index(), sequence.GetImmediate(input->index())));
85      } else if (input->IsUnallocated()) {
86        virtual_registers.insert(
87            UnallocatedOperand::cast(input)->virtual_register());
88      }
89    }
90    s.instructions_.push_back(instr);
91  }
92  for (std::set<int>::const_iterator i = virtual_registers.begin();
93       i != virtual_registers.end(); ++i) {
94    int virtual_register = *i;
95    if (sequence.IsDouble(virtual_register)) {
96      EXPECT_FALSE(sequence.IsReference(virtual_register));
97      s.doubles_.insert(virtual_register);
98    }
99    if (sequence.IsReference(virtual_register)) {
100      EXPECT_FALSE(sequence.IsDouble(virtual_register));
101      s.references_.insert(virtual_register);
102    }
103  }
104  for (int i = 0; i < sequence.GetFrameStateDescriptorCount(); i++) {
105    s.deoptimization_entries_.push_back(sequence.GetFrameStateDescriptor(
106        InstructionSequence::StateId::FromInt(i)));
107  }
108  return s;
109}
110
111
112// -----------------------------------------------------------------------------
113// Return.
114
115
116TARGET_TEST_F(InstructionSelectorTest, ReturnParameter) {
117  StreamBuilder m(this, kMachInt32, kMachInt32);
118  m.Return(m.Parameter(0));
119  Stream s = m.Build(kAllInstructions);
120  ASSERT_EQ(2U, s.size());
121  EXPECT_EQ(kArchNop, s[0]->arch_opcode());
122  ASSERT_EQ(1U, s[0]->OutputCount());
123  EXPECT_EQ(kArchRet, s[1]->arch_opcode());
124  EXPECT_EQ(1U, s[1]->InputCount());
125}
126
127
128TARGET_TEST_F(InstructionSelectorTest, ReturnZero) {
129  StreamBuilder m(this, kMachInt32);
130  m.Return(m.Int32Constant(0));
131  Stream s = m.Build(kAllInstructions);
132  ASSERT_EQ(2U, s.size());
133  EXPECT_EQ(kArchNop, s[0]->arch_opcode());
134  ASSERT_EQ(1U, s[0]->OutputCount());
135  EXPECT_EQ(InstructionOperand::CONSTANT, s[0]->OutputAt(0)->kind());
136  EXPECT_EQ(0, s.ToInt32(s[0]->OutputAt(0)));
137  EXPECT_EQ(kArchRet, s[1]->arch_opcode());
138  EXPECT_EQ(1U, s[1]->InputCount());
139}
140
141
142// -----------------------------------------------------------------------------
143// Conversions.
144
145
146TARGET_TEST_F(InstructionSelectorTest, TruncateFloat64ToInt32WithParameter) {
147  StreamBuilder m(this, kMachInt32, kMachFloat64);
148  m.Return(m.TruncateFloat64ToInt32(m.Parameter(0)));
149  Stream s = m.Build(kAllInstructions);
150  ASSERT_EQ(3U, s.size());
151  EXPECT_EQ(kArchNop, s[0]->arch_opcode());
152  EXPECT_EQ(kArchTruncateDoubleToI, s[1]->arch_opcode());
153  EXPECT_EQ(1U, s[1]->InputCount());
154  EXPECT_EQ(1U, s[1]->OutputCount());
155  EXPECT_EQ(kArchRet, s[2]->arch_opcode());
156}
157
158
159// -----------------------------------------------------------------------------
160// Parameters.
161
162
163TARGET_TEST_F(InstructionSelectorTest, DoubleParameter) {
164  StreamBuilder m(this, kMachFloat64, kMachFloat64);
165  Node* param = m.Parameter(0);
166  m.Return(param);
167  Stream s = m.Build(kAllInstructions);
168  EXPECT_TRUE(s.IsDouble(param->id()));
169}
170
171
172TARGET_TEST_F(InstructionSelectorTest, ReferenceParameter) {
173  StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged);
174  Node* param = m.Parameter(0);
175  m.Return(param);
176  Stream s = m.Build(kAllInstructions);
177  EXPECT_TRUE(s.IsReference(param->id()));
178}
179
180
181// -----------------------------------------------------------------------------
182// Finish.
183
184
185TARGET_TEST_F(InstructionSelectorTest, Finish) {
186  StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged);
187  Node* param = m.Parameter(0);
188  Node* finish = m.NewNode(m.common()->Finish(1), param, m.graph()->start());
189  m.Return(finish);
190  Stream s = m.Build(kAllInstructions);
191  ASSERT_EQ(3U, s.size());
192  EXPECT_EQ(kArchNop, s[0]->arch_opcode());
193  ASSERT_EQ(1U, s[0]->OutputCount());
194  ASSERT_TRUE(s[0]->Output()->IsUnallocated());
195  EXPECT_EQ(param->id(), s.ToVreg(s[0]->Output()));
196  EXPECT_EQ(kArchNop, s[1]->arch_opcode());
197  ASSERT_EQ(1U, s[1]->InputCount());
198  ASSERT_TRUE(s[1]->InputAt(0)->IsUnallocated());
199  EXPECT_EQ(param->id(), s.ToVreg(s[1]->InputAt(0)));
200  ASSERT_EQ(1U, s[1]->OutputCount());
201  ASSERT_TRUE(s[1]->Output()->IsUnallocated());
202  EXPECT_TRUE(UnallocatedOperand::cast(s[1]->Output())->HasSameAsInputPolicy());
203  EXPECT_EQ(finish->id(), s.ToVreg(s[1]->Output()));
204  EXPECT_TRUE(s.IsReference(finish->id()));
205}
206
207
208// -----------------------------------------------------------------------------
209// Phi.
210
211
212typedef InstructionSelectorTestWithParam<MachineType>
213    InstructionSelectorPhiTest;
214
215
216TARGET_TEST_P(InstructionSelectorPhiTest, Doubleness) {
217  const MachineType type = GetParam();
218  StreamBuilder m(this, type, type, type);
219  Node* param0 = m.Parameter(0);
220  Node* param1 = m.Parameter(1);
221  MLabel a, b, c;
222  m.Branch(m.Int32Constant(0), &a, &b);
223  m.Bind(&a);
224  m.Goto(&c);
225  m.Bind(&b);
226  m.Goto(&c);
227  m.Bind(&c);
228  Node* phi = m.Phi(type, param0, param1);
229  m.Return(phi);
230  Stream s = m.Build(kAllInstructions);
231  EXPECT_EQ(s.IsDouble(phi->id()), s.IsDouble(param0->id()));
232  EXPECT_EQ(s.IsDouble(phi->id()), s.IsDouble(param1->id()));
233}
234
235
236TARGET_TEST_P(InstructionSelectorPhiTest, Referenceness) {
237  const MachineType type = GetParam();
238  StreamBuilder m(this, type, type, type);
239  Node* param0 = m.Parameter(0);
240  Node* param1 = m.Parameter(1);
241  MLabel a, b, c;
242  m.Branch(m.Int32Constant(1), &a, &b);
243  m.Bind(&a);
244  m.Goto(&c);
245  m.Bind(&b);
246  m.Goto(&c);
247  m.Bind(&c);
248  Node* phi = m.Phi(type, param0, param1);
249  m.Return(phi);
250  Stream s = m.Build(kAllInstructions);
251  EXPECT_EQ(s.IsReference(phi->id()), s.IsReference(param0->id()));
252  EXPECT_EQ(s.IsReference(phi->id()), s.IsReference(param1->id()));
253}
254
255
256INSTANTIATE_TEST_CASE_P(InstructionSelectorTest, InstructionSelectorPhiTest,
257                        ::testing::Values(kMachFloat64, kMachInt8, kMachUint8,
258                                          kMachInt16, kMachUint16, kMachInt32,
259                                          kMachUint32, kMachInt64, kMachUint64,
260                                          kMachPtr, kMachAnyTagged));
261
262
263// -----------------------------------------------------------------------------
264// ValueEffect.
265
266
267TARGET_TEST_F(InstructionSelectorTest, ValueEffect) {
268  StreamBuilder m1(this, kMachInt32, kMachPtr);
269  Node* p1 = m1.Parameter(0);
270  m1.Return(m1.Load(kMachInt32, p1, m1.Int32Constant(0)));
271  Stream s1 = m1.Build(kAllInstructions);
272  StreamBuilder m2(this, kMachInt32, kMachPtr);
273  Node* p2 = m2.Parameter(0);
274  m2.Return(m2.NewNode(m2.machine()->Load(kMachInt32), p2, m2.Int32Constant(0),
275                       m2.NewNode(m2.common()->ValueEffect(1), p2)));
276  Stream s2 = m2.Build(kAllInstructions);
277  EXPECT_LE(3U, s1.size());
278  ASSERT_EQ(s1.size(), s2.size());
279  TRACED_FORRANGE(size_t, i, 0, s1.size() - 1) {
280    const Instruction* i1 = s1[i];
281    const Instruction* i2 = s2[i];
282    EXPECT_EQ(i1->arch_opcode(), i2->arch_opcode());
283    EXPECT_EQ(i1->InputCount(), i2->InputCount());
284    EXPECT_EQ(i1->OutputCount(), i2->OutputCount());
285  }
286}
287
288
289// -----------------------------------------------------------------------------
290// Calls with deoptimization.
291TARGET_TEST_F(InstructionSelectorTest, CallJSFunctionWithDeopt) {
292  StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged, kMachAnyTagged,
293                  kMachAnyTagged);
294
295  BailoutId bailout_id(42);
296
297  Node* function_node = m.Parameter(0);
298  Node* receiver = m.Parameter(1);
299  Node* context = m.Parameter(2);
300
301  Node* parameters = m.NewNode(m.common()->StateValues(1), m.Int32Constant(1));
302  Node* locals = m.NewNode(m.common()->StateValues(0));
303  Node* stack = m.NewNode(m.common()->StateValues(0));
304  Node* context_dummy = m.Int32Constant(0);
305
306  Node* state_node = m.NewNode(
307      m.common()->FrameState(JS_FRAME, bailout_id, kPushOutput), parameters,
308      locals, stack, context_dummy, m.UndefinedConstant());
309  Node* call = m.CallJS0(function_node, receiver, context, state_node);
310  m.Return(call);
311
312  Stream s = m.Build(kAllExceptNopInstructions);
313
314  // Skip until kArchCallJSFunction.
315  size_t index = 0;
316  for (; index < s.size() && s[index]->arch_opcode() != kArchCallJSFunction;
317       index++) {
318  }
319  // Now we should have two instructions: call and return.
320  ASSERT_EQ(index + 2, s.size());
321
322  EXPECT_EQ(kArchCallJSFunction, s[index++]->arch_opcode());
323  EXPECT_EQ(kArchRet, s[index++]->arch_opcode());
324
325  // TODO(jarin) Check deoptimization table.
326}
327
328
329TARGET_TEST_F(InstructionSelectorTest, CallFunctionStubWithDeopt) {
330  StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged, kMachAnyTagged,
331                  kMachAnyTagged);
332
333  BailoutId bailout_id_before(42);
334
335  // Some arguments for the call node.
336  Node* function_node = m.Parameter(0);
337  Node* receiver = m.Parameter(1);
338  Node* context = m.Int32Constant(1);  // Context is ignored.
339
340  // Build frame state for the state before the call.
341  Node* parameters = m.NewNode(m.common()->StateValues(1), m.Int32Constant(43));
342  Node* locals = m.NewNode(m.common()->StateValues(1), m.Int32Constant(44));
343  Node* stack = m.NewNode(m.common()->StateValues(1), m.Int32Constant(45));
344
345  Node* context_sentinel = m.Int32Constant(0);
346  Node* frame_state_before = m.NewNode(
347      m.common()->FrameState(JS_FRAME, bailout_id_before, kPushOutput),
348      parameters, locals, stack, context_sentinel, m.UndefinedConstant());
349
350  // Build the call.
351  Node* call = m.CallFunctionStub0(function_node, receiver, context,
352                                   frame_state_before, CALL_AS_METHOD);
353
354  m.Return(call);
355
356  Stream s = m.Build(kAllExceptNopInstructions);
357
358  // Skip until kArchCallJSFunction.
359  size_t index = 0;
360  for (; index < s.size() && s[index]->arch_opcode() != kArchCallCodeObject;
361       index++) {
362  }
363  // Now we should have two instructions: call, return.
364  ASSERT_EQ(index + 2, s.size());
365
366  // Check the call instruction
367  const Instruction* call_instr = s[index++];
368  EXPECT_EQ(kArchCallCodeObject, call_instr->arch_opcode());
369  size_t num_operands =
370      1 +  // Code object.
371      1 +
372      4 +  // Frame state deopt id + one input for each value in frame state.
373      1 +  // Function.
374      1;   // Context.
375  ASSERT_EQ(num_operands, call_instr->InputCount());
376
377  // Code object.
378  EXPECT_TRUE(call_instr->InputAt(0)->IsImmediate());
379
380  // Deoptimization id.
381  int32_t deopt_id_before = s.ToInt32(call_instr->InputAt(1));
382  FrameStateDescriptor* desc_before =
383      s.GetFrameStateDescriptor(deopt_id_before);
384  EXPECT_EQ(bailout_id_before, desc_before->bailout_id());
385  EXPECT_EQ(kPushOutput, desc_before->state_combine());
386  EXPECT_EQ(1u, desc_before->parameters_count());
387  EXPECT_EQ(1u, desc_before->locals_count());
388  EXPECT_EQ(1u, desc_before->stack_count());
389  EXPECT_EQ(43, s.ToInt32(call_instr->InputAt(2)));
390  EXPECT_EQ(0, s.ToInt32(call_instr->InputAt(3)));
391  EXPECT_EQ(44, s.ToInt32(call_instr->InputAt(4)));
392  EXPECT_EQ(45, s.ToInt32(call_instr->InputAt(5)));
393
394  // Function.
395  EXPECT_EQ(function_node->id(), s.ToVreg(call_instr->InputAt(6)));
396  // Context.
397  EXPECT_EQ(context->id(), s.ToVreg(call_instr->InputAt(7)));
398
399  EXPECT_EQ(kArchRet, s[index++]->arch_opcode());
400
401  EXPECT_EQ(index, s.size());
402}
403
404
405TARGET_TEST_F(InstructionSelectorTest,
406              CallFunctionStubDeoptRecursiveFrameState) {
407  StreamBuilder m(this, kMachAnyTagged, kMachAnyTagged, kMachAnyTagged,
408                  kMachAnyTagged);
409
410  BailoutId bailout_id_before(42);
411  BailoutId bailout_id_parent(62);
412
413  // Some arguments for the call node.
414  Node* function_node = m.Parameter(0);
415  Node* receiver = m.Parameter(1);
416  Node* context = m.Int32Constant(66);
417
418  // Build frame state for the state before the call.
419  Node* parameters = m.NewNode(m.common()->StateValues(1), m.Int32Constant(63));
420  Node* locals = m.NewNode(m.common()->StateValues(1), m.Int32Constant(64));
421  Node* stack = m.NewNode(m.common()->StateValues(1), m.Int32Constant(65));
422  Node* frame_state_parent = m.NewNode(
423      m.common()->FrameState(JS_FRAME, bailout_id_parent, kIgnoreOutput),
424      parameters, locals, stack, context, m.UndefinedConstant());
425
426  Node* context2 = m.Int32Constant(46);
427  Node* parameters2 =
428      m.NewNode(m.common()->StateValues(1), m.Int32Constant(43));
429  Node* locals2 = m.NewNode(m.common()->StateValues(1), m.Int32Constant(44));
430  Node* stack2 = m.NewNode(m.common()->StateValues(1), m.Int32Constant(45));
431  Node* frame_state_before = m.NewNode(
432      m.common()->FrameState(JS_FRAME, bailout_id_before, kPushOutput),
433      parameters2, locals2, stack2, context2, frame_state_parent);
434
435  // Build the call.
436  Node* call = m.CallFunctionStub0(function_node, receiver, context2,
437                                   frame_state_before, CALL_AS_METHOD);
438
439  m.Return(call);
440
441  Stream s = m.Build(kAllExceptNopInstructions);
442
443  // Skip until kArchCallJSFunction.
444  size_t index = 0;
445  for (; index < s.size() && s[index]->arch_opcode() != kArchCallCodeObject;
446       index++) {
447  }
448  // Now we should have three instructions: call, return.
449  EXPECT_EQ(index + 2, s.size());
450
451  // Check the call instruction
452  const Instruction* call_instr = s[index++];
453  EXPECT_EQ(kArchCallCodeObject, call_instr->arch_opcode());
454  size_t num_operands =
455      1 +  // Code object.
456      1 +  // Frame state deopt id
457      4 +  // One input for each value in frame state + context.
458      4 +  // One input for each value in the parent frame state + context.
459      1 +  // Function.
460      1;   // Context.
461  EXPECT_EQ(num_operands, call_instr->InputCount());
462  // Code object.
463  EXPECT_TRUE(call_instr->InputAt(0)->IsImmediate());
464
465  // Deoptimization id.
466  int32_t deopt_id_before = s.ToInt32(call_instr->InputAt(1));
467  FrameStateDescriptor* desc_before =
468      s.GetFrameStateDescriptor(deopt_id_before);
469  EXPECT_EQ(bailout_id_before, desc_before->bailout_id());
470  EXPECT_EQ(1u, desc_before->parameters_count());
471  EXPECT_EQ(1u, desc_before->locals_count());
472  EXPECT_EQ(1u, desc_before->stack_count());
473  EXPECT_EQ(63, s.ToInt32(call_instr->InputAt(2)));
474  // Context:
475  EXPECT_EQ(66, s.ToInt32(call_instr->InputAt(3)));
476  EXPECT_EQ(64, s.ToInt32(call_instr->InputAt(4)));
477  EXPECT_EQ(65, s.ToInt32(call_instr->InputAt(5)));
478  // Values from parent environment should follow.
479  EXPECT_EQ(43, s.ToInt32(call_instr->InputAt(6)));
480  EXPECT_EQ(46, s.ToInt32(call_instr->InputAt(7)));
481  EXPECT_EQ(44, s.ToInt32(call_instr->InputAt(8)));
482  EXPECT_EQ(45, s.ToInt32(call_instr->InputAt(9)));
483
484  // Function.
485  EXPECT_EQ(function_node->id(), s.ToVreg(call_instr->InputAt(10)));
486  // Context.
487  EXPECT_EQ(context2->id(), s.ToVreg(call_instr->InputAt(11)));
488  // Continuation.
489
490  EXPECT_EQ(kArchRet, s[index++]->arch_opcode());
491  EXPECT_EQ(index, s.size());
492}
493
494}  // namespace compiler
495}  // namespace internal
496}  // namespace v8
497