src/v8/src/compiler/instruction-selector-unittest.cc

   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
  21 InstructionSelectorTest::InstructionSelectorTest() : rng_(FLAG_random_seed) {}
  22
  23
  24 InstructionSelectorTest::~InstructionSelectorTest() {}
  25
  26
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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.
 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
 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
 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