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 
10 namespace v8 {
11 namespace internal {
12 namespace compiler {
13 
14 namespace {
15 
16 typedef RawMachineAssembler::Label MLabel;
17 
18 }  // namespace
19 
20 
InstructionSelectorTest()21 InstructionSelectorTest::InstructionSelectorTest() : rng_(FLAG_random_seed) {}
22 
23 
~InstructionSelectorTest()24 InstructionSelectorTest::~InstructionSelectorTest() {}
25 
26 
Build(InstructionSelector::Features features,InstructionSelectorTest::StreamBuilderMode mode)27 InstructionSelectorTest::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 
TARGET_TEST_F(InstructionSelectorTest,ReturnParameter)116 TARGET_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 
TARGET_TEST_F(InstructionSelectorTest,ReturnZero)128 TARGET_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 
TARGET_TEST_F(InstructionSelectorTest,TruncateFloat64ToInt32WithParameter)146 TARGET_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 
TARGET_TEST_F(InstructionSelectorTest,DoubleParameter)163 TARGET_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 
TARGET_TEST_F(InstructionSelectorTest,ReferenceParameter)172 TARGET_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 
TARGET_TEST_F(InstructionSelectorTest,Finish)185 TARGET_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 
212 typedef InstructionSelectorTestWithParam<MachineType>
213     InstructionSelectorPhiTest;
214 
215 
TARGET_TEST_P(InstructionSelectorPhiTest,Doubleness)216 TARGET_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 
TARGET_TEST_P(InstructionSelectorPhiTest,Referenceness)236 TARGET_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 
256 INSTANTIATE_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 
TARGET_TEST_F(InstructionSelectorTest,ValueEffect)267 TARGET_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.
TARGET_TEST_F(InstructionSelectorTest,CallJSFunctionWithDeopt)291 TARGET_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 
TARGET_TEST_F(InstructionSelectorTest,CallFunctionStubWithDeopt)329 TARGET_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 
TARGET_TEST_F(InstructionSelectorTest,CallFunctionStubDeoptRecursiveFrameState)405 TARGET_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