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.h"
6
7#include "src/compiler/instruction-selector-impl.h"
8#include "src/compiler/node-matchers.h"
9#include "src/compiler/node-properties-inl.h"
10#include "src/compiler/pipeline.h"
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16InstructionSelector::InstructionSelector(InstructionSequence* sequence,
17                                         SourcePositionTable* source_positions,
18                                         Features features)
19    : zone_(sequence->isolate()),
20      sequence_(sequence),
21      source_positions_(source_positions),
22      features_(features),
23      current_block_(NULL),
24      instructions_(zone()),
25      defined_(graph()->NodeCount(), false, zone()),
26      used_(graph()->NodeCount(), false, zone()) {}
27
28
29void InstructionSelector::SelectInstructions() {
30  // Mark the inputs of all phis in loop headers as used.
31  BasicBlockVector* blocks = schedule()->rpo_order();
32  for (BasicBlockVectorIter i = blocks->begin(); i != blocks->end(); ++i) {
33    BasicBlock* block = *i;
34    if (!block->IsLoopHeader()) continue;
35    DCHECK_NE(0, block->PredecessorCount());
36    DCHECK_NE(1, block->PredecessorCount());
37    for (BasicBlock::const_iterator j = block->begin(); j != block->end();
38         ++j) {
39      Node* phi = *j;
40      if (phi->opcode() != IrOpcode::kPhi) continue;
41
42      // Mark all inputs as used.
43      Node::Inputs inputs = phi->inputs();
44      for (InputIter k = inputs.begin(); k != inputs.end(); ++k) {
45        MarkAsUsed(*k);
46      }
47    }
48  }
49
50  // Visit each basic block in post order.
51  for (BasicBlockVectorRIter i = blocks->rbegin(); i != blocks->rend(); ++i) {
52    VisitBlock(*i);
53  }
54
55  // Schedule the selected instructions.
56  for (BasicBlockVectorIter i = blocks->begin(); i != blocks->end(); ++i) {
57    BasicBlock* block = *i;
58    size_t end = block->code_end_;
59    size_t start = block->code_start_;
60    sequence()->StartBlock(block);
61    while (start-- > end) {
62      sequence()->AddInstruction(instructions_[start], block);
63    }
64    sequence()->EndBlock(block);
65  }
66}
67
68
69Instruction* InstructionSelector::Emit(InstructionCode opcode,
70                                       InstructionOperand* output,
71                                       size_t temp_count,
72                                       InstructionOperand** temps) {
73  size_t output_count = output == NULL ? 0 : 1;
74  return Emit(opcode, output_count, &output, 0, NULL, temp_count, temps);
75}
76
77
78Instruction* InstructionSelector::Emit(InstructionCode opcode,
79                                       InstructionOperand* output,
80                                       InstructionOperand* a, size_t temp_count,
81                                       InstructionOperand** temps) {
82  size_t output_count = output == NULL ? 0 : 1;
83  return Emit(opcode, output_count, &output, 1, &a, temp_count, temps);
84}
85
86
87Instruction* InstructionSelector::Emit(InstructionCode opcode,
88                                       InstructionOperand* output,
89                                       InstructionOperand* a,
90                                       InstructionOperand* b, size_t temp_count,
91                                       InstructionOperand** temps) {
92  size_t output_count = output == NULL ? 0 : 1;
93  InstructionOperand* inputs[] = {a, b};
94  size_t input_count = arraysize(inputs);
95  return Emit(opcode, output_count, &output, input_count, inputs, temp_count,
96              temps);
97}
98
99
100Instruction* InstructionSelector::Emit(InstructionCode opcode,
101                                       InstructionOperand* output,
102                                       InstructionOperand* a,
103                                       InstructionOperand* b,
104                                       InstructionOperand* c, size_t temp_count,
105                                       InstructionOperand** temps) {
106  size_t output_count = output == NULL ? 0 : 1;
107  InstructionOperand* inputs[] = {a, b, c};
108  size_t input_count = arraysize(inputs);
109  return Emit(opcode, output_count, &output, input_count, inputs, temp_count,
110              temps);
111}
112
113
114Instruction* InstructionSelector::Emit(
115    InstructionCode opcode, InstructionOperand* output, InstructionOperand* a,
116    InstructionOperand* b, InstructionOperand* c, InstructionOperand* d,
117    size_t temp_count, InstructionOperand** temps) {
118  size_t output_count = output == NULL ? 0 : 1;
119  InstructionOperand* inputs[] = {a, b, c, d};
120  size_t input_count = arraysize(inputs);
121  return Emit(opcode, output_count, &output, input_count, inputs, temp_count,
122              temps);
123}
124
125
126Instruction* InstructionSelector::Emit(
127    InstructionCode opcode, size_t output_count, InstructionOperand** outputs,
128    size_t input_count, InstructionOperand** inputs, size_t temp_count,
129    InstructionOperand** temps) {
130  Instruction* instr =
131      Instruction::New(instruction_zone(), opcode, output_count, outputs,
132                       input_count, inputs, temp_count, temps);
133  return Emit(instr);
134}
135
136
137Instruction* InstructionSelector::Emit(Instruction* instr) {
138  instructions_.push_back(instr);
139  return instr;
140}
141
142
143bool InstructionSelector::IsNextInAssemblyOrder(const BasicBlock* block) const {
144  return block->rpo_number_ == (current_block_->rpo_number_ + 1) &&
145         block->deferred_ == current_block_->deferred_;
146}
147
148
149bool InstructionSelector::CanCover(Node* user, Node* node) const {
150  return node->OwnedBy(user) &&
151         schedule()->block(node) == schedule()->block(user);
152}
153
154
155bool InstructionSelector::IsDefined(Node* node) const {
156  DCHECK_NOT_NULL(node);
157  NodeId id = node->id();
158  DCHECK(id >= 0);
159  DCHECK(id < static_cast<NodeId>(defined_.size()));
160  return defined_[id];
161}
162
163
164void InstructionSelector::MarkAsDefined(Node* node) {
165  DCHECK_NOT_NULL(node);
166  NodeId id = node->id();
167  DCHECK(id >= 0);
168  DCHECK(id < static_cast<NodeId>(defined_.size()));
169  defined_[id] = true;
170}
171
172
173bool InstructionSelector::IsUsed(Node* node) const {
174  if (!node->op()->HasProperty(Operator::kEliminatable)) return true;
175  NodeId id = node->id();
176  DCHECK(id >= 0);
177  DCHECK(id < static_cast<NodeId>(used_.size()));
178  return used_[id];
179}
180
181
182void InstructionSelector::MarkAsUsed(Node* node) {
183  DCHECK_NOT_NULL(node);
184  NodeId id = node->id();
185  DCHECK(id >= 0);
186  DCHECK(id < static_cast<NodeId>(used_.size()));
187  used_[id] = true;
188}
189
190
191bool InstructionSelector::IsDouble(const Node* node) const {
192  DCHECK_NOT_NULL(node);
193  return sequence()->IsDouble(node->id());
194}
195
196
197void InstructionSelector::MarkAsDouble(Node* node) {
198  DCHECK_NOT_NULL(node);
199  DCHECK(!IsReference(node));
200  sequence()->MarkAsDouble(node->id());
201}
202
203
204bool InstructionSelector::IsReference(const Node* node) const {
205  DCHECK_NOT_NULL(node);
206  return sequence()->IsReference(node->id());
207}
208
209
210void InstructionSelector::MarkAsReference(Node* node) {
211  DCHECK_NOT_NULL(node);
212  DCHECK(!IsDouble(node));
213  sequence()->MarkAsReference(node->id());
214}
215
216
217void InstructionSelector::MarkAsRepresentation(MachineType rep, Node* node) {
218  DCHECK_NOT_NULL(node);
219  switch (RepresentationOf(rep)) {
220    case kRepFloat32:
221    case kRepFloat64:
222      MarkAsDouble(node);
223      break;
224    case kRepTagged:
225      MarkAsReference(node);
226      break;
227    default:
228      break;
229  }
230}
231
232
233// TODO(bmeurer): Get rid of the CallBuffer business and make
234// InstructionSelector::VisitCall platform independent instead.
235CallBuffer::CallBuffer(Zone* zone, CallDescriptor* d,
236                       FrameStateDescriptor* frame_desc)
237    : descriptor(d),
238      frame_state_descriptor(frame_desc),
239      output_nodes(zone),
240      outputs(zone),
241      instruction_args(zone),
242      pushed_nodes(zone) {
243  output_nodes.reserve(d->ReturnCount());
244  outputs.reserve(d->ReturnCount());
245  pushed_nodes.reserve(input_count());
246  instruction_args.reserve(input_count() + frame_state_value_count());
247}
248
249
250// TODO(bmeurer): Get rid of the CallBuffer business and make
251// InstructionSelector::VisitCall platform independent instead.
252void InstructionSelector::InitializeCallBuffer(Node* call, CallBuffer* buffer,
253                                               bool call_code_immediate,
254                                               bool call_address_immediate) {
255  OperandGenerator g(this);
256  DCHECK_EQ(call->op()->OutputCount(), buffer->descriptor->ReturnCount());
257  DCHECK_EQ(OperatorProperties::GetValueInputCount(call->op()),
258            buffer->input_count() + buffer->frame_state_count());
259
260  if (buffer->descriptor->ReturnCount() > 0) {
261    // Collect the projections that represent multiple outputs from this call.
262    if (buffer->descriptor->ReturnCount() == 1) {
263      buffer->output_nodes.push_back(call);
264    } else {
265      buffer->output_nodes.resize(buffer->descriptor->ReturnCount(), NULL);
266      call->CollectProjections(&buffer->output_nodes);
267    }
268
269    // Filter out the outputs that aren't live because no projection uses them.
270    for (size_t i = 0; i < buffer->output_nodes.size(); i++) {
271      if (buffer->output_nodes[i] != NULL) {
272        Node* output = buffer->output_nodes[i];
273        MachineType type =
274            buffer->descriptor->GetReturnType(static_cast<int>(i));
275        LinkageLocation location =
276            buffer->descriptor->GetReturnLocation(static_cast<int>(i));
277        MarkAsRepresentation(type, output);
278        buffer->outputs.push_back(g.DefineAsLocation(output, location, type));
279      }
280    }
281  }
282
283  // The first argument is always the callee code.
284  Node* callee = call->InputAt(0);
285  switch (buffer->descriptor->kind()) {
286    case CallDescriptor::kCallCodeObject:
287      buffer->instruction_args.push_back(
288          (call_code_immediate && callee->opcode() == IrOpcode::kHeapConstant)
289              ? g.UseImmediate(callee)
290              : g.UseRegister(callee));
291      break;
292    case CallDescriptor::kCallAddress:
293      buffer->instruction_args.push_back(
294          (call_address_immediate &&
295           (callee->opcode() == IrOpcode::kInt32Constant ||
296            callee->opcode() == IrOpcode::kInt64Constant))
297              ? g.UseImmediate(callee)
298              : g.UseRegister(callee));
299      break;
300    case CallDescriptor::kCallJSFunction:
301      buffer->instruction_args.push_back(
302          g.UseLocation(callee, buffer->descriptor->GetInputLocation(0),
303                        buffer->descriptor->GetInputType(0)));
304      break;
305  }
306  DCHECK_EQ(1, buffer->instruction_args.size());
307
308  // If the call needs a frame state, we insert the state information as
309  // follows (n is the number of value inputs to the frame state):
310  // arg 1               : deoptimization id.
311  // arg 2 - arg (n + 1) : value inputs to the frame state.
312  if (buffer->frame_state_descriptor != NULL) {
313    InstructionSequence::StateId state_id =
314        sequence()->AddFrameStateDescriptor(buffer->frame_state_descriptor);
315    buffer->instruction_args.push_back(g.TempImmediate(state_id.ToInt()));
316
317    Node* frame_state =
318        call->InputAt(static_cast<int>(buffer->descriptor->InputCount()));
319    AddFrameStateInputs(frame_state, &buffer->instruction_args,
320                        buffer->frame_state_descriptor);
321  }
322  DCHECK(1 + buffer->frame_state_value_count() ==
323         buffer->instruction_args.size());
324
325  size_t input_count = static_cast<size_t>(buffer->input_count());
326
327  // Split the arguments into pushed_nodes and instruction_args. Pushed
328  // arguments require an explicit push instruction before the call and do
329  // not appear as arguments to the call. Everything else ends up
330  // as an InstructionOperand argument to the call.
331  InputIter iter(call->inputs().begin());
332  int pushed_count = 0;
333  for (size_t index = 0; index < input_count; ++iter, ++index) {
334    DCHECK(iter != call->inputs().end());
335    DCHECK(index == static_cast<size_t>(iter.index()));
336    DCHECK((*iter)->op()->opcode() != IrOpcode::kFrameState);
337    if (index == 0) continue;  // The first argument (callee) is already done.
338    InstructionOperand* op =
339        g.UseLocation(*iter, buffer->descriptor->GetInputLocation(index),
340                      buffer->descriptor->GetInputType(index));
341    if (UnallocatedOperand::cast(op)->HasFixedSlotPolicy()) {
342      int stack_index = -UnallocatedOperand::cast(op)->fixed_slot_index() - 1;
343      if (static_cast<size_t>(stack_index) >= buffer->pushed_nodes.size()) {
344        buffer->pushed_nodes.resize(stack_index + 1, NULL);
345      }
346      DCHECK_EQ(NULL, buffer->pushed_nodes[stack_index]);
347      buffer->pushed_nodes[stack_index] = *iter;
348      pushed_count++;
349    } else {
350      buffer->instruction_args.push_back(op);
351    }
352  }
353  CHECK_EQ(pushed_count, static_cast<int>(buffer->pushed_nodes.size()));
354  DCHECK(static_cast<size_t>(input_count) ==
355         (buffer->instruction_args.size() + buffer->pushed_nodes.size() -
356          buffer->frame_state_value_count()));
357}
358
359
360void InstructionSelector::VisitBlock(BasicBlock* block) {
361  DCHECK_EQ(NULL, current_block_);
362  current_block_ = block;
363  int current_block_end = static_cast<int>(instructions_.size());
364
365  // Generate code for the block control "top down", but schedule the code
366  // "bottom up".
367  VisitControl(block);
368  std::reverse(instructions_.begin() + current_block_end, instructions_.end());
369
370  // Visit code in reverse control flow order, because architecture-specific
371  // matching may cover more than one node at a time.
372  for (BasicBlock::reverse_iterator i = block->rbegin(); i != block->rend();
373       ++i) {
374    Node* node = *i;
375    // Skip nodes that are unused or already defined.
376    if (!IsUsed(node) || IsDefined(node)) continue;
377    // Generate code for this node "top down", but schedule the code "bottom
378    // up".
379    size_t current_node_end = instructions_.size();
380    VisitNode(node);
381    std::reverse(instructions_.begin() + current_node_end, instructions_.end());
382  }
383
384  // We're done with the block.
385  // TODO(bmeurer): We should not mutate the schedule.
386  block->code_end_ = current_block_end;
387  block->code_start_ = static_cast<int>(instructions_.size());
388
389  current_block_ = NULL;
390}
391
392
393static inline void CheckNoPhis(const BasicBlock* block) {
394#ifdef DEBUG
395  // Branch targets should not have phis.
396  for (BasicBlock::const_iterator i = block->begin(); i != block->end(); ++i) {
397    const Node* node = *i;
398    CHECK_NE(IrOpcode::kPhi, node->opcode());
399  }
400#endif
401}
402
403
404void InstructionSelector::VisitControl(BasicBlock* block) {
405  Node* input = block->control_input_;
406  switch (block->control_) {
407    case BasicBlockData::kGoto:
408      return VisitGoto(block->SuccessorAt(0));
409    case BasicBlockData::kBranch: {
410      DCHECK_EQ(IrOpcode::kBranch, input->opcode());
411      BasicBlock* tbranch = block->SuccessorAt(0);
412      BasicBlock* fbranch = block->SuccessorAt(1);
413      // SSA deconstruction requires targets of branches not to have phis.
414      // Edge split form guarantees this property, but is more strict.
415      CheckNoPhis(tbranch);
416      CheckNoPhis(fbranch);
417      if (tbranch == fbranch) return VisitGoto(tbranch);
418      return VisitBranch(input, tbranch, fbranch);
419    }
420    case BasicBlockData::kReturn: {
421      // If the result itself is a return, return its input.
422      Node* value = (input != NULL && input->opcode() == IrOpcode::kReturn)
423                        ? input->InputAt(0)
424                        : input;
425      return VisitReturn(value);
426    }
427    case BasicBlockData::kThrow:
428      return VisitThrow(input);
429    case BasicBlockData::kNone: {
430      // TODO(titzer): exit block doesn't have control.
431      DCHECK(input == NULL);
432      break;
433    }
434    default:
435      UNREACHABLE();
436      break;
437  }
438}
439
440
441void InstructionSelector::VisitNode(Node* node) {
442  DCHECK_NOT_NULL(schedule()->block(node));  // should only use scheduled nodes.
443  SourcePosition source_position = source_positions_->GetSourcePosition(node);
444  if (!source_position.IsUnknown()) {
445    DCHECK(!source_position.IsInvalid());
446    if (FLAG_turbo_source_positions || node->opcode() == IrOpcode::kCall) {
447      Emit(SourcePositionInstruction::New(instruction_zone(), source_position));
448    }
449  }
450  switch (node->opcode()) {
451    case IrOpcode::kStart:
452    case IrOpcode::kLoop:
453    case IrOpcode::kEnd:
454    case IrOpcode::kBranch:
455    case IrOpcode::kIfTrue:
456    case IrOpcode::kIfFalse:
457    case IrOpcode::kEffectPhi:
458    case IrOpcode::kMerge:
459      // No code needed for these graph artifacts.
460      return;
461    case IrOpcode::kFinish:
462      return MarkAsReference(node), VisitFinish(node);
463    case IrOpcode::kParameter: {
464      MachineType type = linkage()->GetParameterType(OpParameter<int>(node));
465      MarkAsRepresentation(type, node);
466      return VisitParameter(node);
467    }
468    case IrOpcode::kPhi: {
469      MachineType type = OpParameter<MachineType>(node);
470      MarkAsRepresentation(type, node);
471      return VisitPhi(node);
472    }
473    case IrOpcode::kProjection:
474      return VisitProjection(node);
475    case IrOpcode::kInt32Constant:
476    case IrOpcode::kInt64Constant:
477    case IrOpcode::kExternalConstant:
478      return VisitConstant(node);
479    case IrOpcode::kFloat64Constant:
480      return MarkAsDouble(node), VisitConstant(node);
481    case IrOpcode::kHeapConstant:
482    case IrOpcode::kNumberConstant:
483      // TODO(turbofan): only mark non-smis as references.
484      return MarkAsReference(node), VisitConstant(node);
485    case IrOpcode::kCall:
486      return VisitCall(node, NULL, NULL);
487    case IrOpcode::kFrameState:
488    case IrOpcode::kStateValues:
489      return;
490    case IrOpcode::kLoad: {
491      LoadRepresentation rep = OpParameter<LoadRepresentation>(node);
492      MarkAsRepresentation(rep, node);
493      return VisitLoad(node);
494    }
495    case IrOpcode::kStore:
496      return VisitStore(node);
497    case IrOpcode::kWord32And:
498      return VisitWord32And(node);
499    case IrOpcode::kWord32Or:
500      return VisitWord32Or(node);
501    case IrOpcode::kWord32Xor:
502      return VisitWord32Xor(node);
503    case IrOpcode::kWord32Shl:
504      return VisitWord32Shl(node);
505    case IrOpcode::kWord32Shr:
506      return VisitWord32Shr(node);
507    case IrOpcode::kWord32Sar:
508      return VisitWord32Sar(node);
509    case IrOpcode::kWord32Ror:
510      return VisitWord32Ror(node);
511    case IrOpcode::kWord32Equal:
512      return VisitWord32Equal(node);
513    case IrOpcode::kWord64And:
514      return VisitWord64And(node);
515    case IrOpcode::kWord64Or:
516      return VisitWord64Or(node);
517    case IrOpcode::kWord64Xor:
518      return VisitWord64Xor(node);
519    case IrOpcode::kWord64Shl:
520      return VisitWord64Shl(node);
521    case IrOpcode::kWord64Shr:
522      return VisitWord64Shr(node);
523    case IrOpcode::kWord64Sar:
524      return VisitWord64Sar(node);
525    case IrOpcode::kWord64Ror:
526      return VisitWord64Ror(node);
527    case IrOpcode::kWord64Equal:
528      return VisitWord64Equal(node);
529    case IrOpcode::kInt32Add:
530      return VisitInt32Add(node);
531    case IrOpcode::kInt32AddWithOverflow:
532      return VisitInt32AddWithOverflow(node);
533    case IrOpcode::kInt32Sub:
534      return VisitInt32Sub(node);
535    case IrOpcode::kInt32SubWithOverflow:
536      return VisitInt32SubWithOverflow(node);
537    case IrOpcode::kInt32Mul:
538      return VisitInt32Mul(node);
539    case IrOpcode::kInt32Div:
540      return VisitInt32Div(node);
541    case IrOpcode::kInt32UDiv:
542      return VisitInt32UDiv(node);
543    case IrOpcode::kInt32Mod:
544      return VisitInt32Mod(node);
545    case IrOpcode::kInt32UMod:
546      return VisitInt32UMod(node);
547    case IrOpcode::kInt32LessThan:
548      return VisitInt32LessThan(node);
549    case IrOpcode::kInt32LessThanOrEqual:
550      return VisitInt32LessThanOrEqual(node);
551    case IrOpcode::kUint32LessThan:
552      return VisitUint32LessThan(node);
553    case IrOpcode::kUint32LessThanOrEqual:
554      return VisitUint32LessThanOrEqual(node);
555    case IrOpcode::kInt64Add:
556      return VisitInt64Add(node);
557    case IrOpcode::kInt64Sub:
558      return VisitInt64Sub(node);
559    case IrOpcode::kInt64Mul:
560      return VisitInt64Mul(node);
561    case IrOpcode::kInt64Div:
562      return VisitInt64Div(node);
563    case IrOpcode::kInt64UDiv:
564      return VisitInt64UDiv(node);
565    case IrOpcode::kInt64Mod:
566      return VisitInt64Mod(node);
567    case IrOpcode::kInt64UMod:
568      return VisitInt64UMod(node);
569    case IrOpcode::kInt64LessThan:
570      return VisitInt64LessThan(node);
571    case IrOpcode::kInt64LessThanOrEqual:
572      return VisitInt64LessThanOrEqual(node);
573    case IrOpcode::kChangeInt32ToFloat64:
574      return MarkAsDouble(node), VisitChangeInt32ToFloat64(node);
575    case IrOpcode::kChangeUint32ToFloat64:
576      return MarkAsDouble(node), VisitChangeUint32ToFloat64(node);
577    case IrOpcode::kChangeFloat64ToInt32:
578      return VisitChangeFloat64ToInt32(node);
579    case IrOpcode::kChangeFloat64ToUint32:
580      return VisitChangeFloat64ToUint32(node);
581    case IrOpcode::kChangeInt32ToInt64:
582      return VisitChangeInt32ToInt64(node);
583    case IrOpcode::kChangeUint32ToUint64:
584      return VisitChangeUint32ToUint64(node);
585    case IrOpcode::kTruncateFloat64ToInt32:
586      return VisitTruncateFloat64ToInt32(node);
587    case IrOpcode::kTruncateInt64ToInt32:
588      return VisitTruncateInt64ToInt32(node);
589    case IrOpcode::kFloat64Add:
590      return MarkAsDouble(node), VisitFloat64Add(node);
591    case IrOpcode::kFloat64Sub:
592      return MarkAsDouble(node), VisitFloat64Sub(node);
593    case IrOpcode::kFloat64Mul:
594      return MarkAsDouble(node), VisitFloat64Mul(node);
595    case IrOpcode::kFloat64Div:
596      return MarkAsDouble(node), VisitFloat64Div(node);
597    case IrOpcode::kFloat64Mod:
598      return MarkAsDouble(node), VisitFloat64Mod(node);
599    case IrOpcode::kFloat64Sqrt:
600      return MarkAsDouble(node), VisitFloat64Sqrt(node);
601    case IrOpcode::kFloat64Equal:
602      return VisitFloat64Equal(node);
603    case IrOpcode::kFloat64LessThan:
604      return VisitFloat64LessThan(node);
605    case IrOpcode::kFloat64LessThanOrEqual:
606      return VisitFloat64LessThanOrEqual(node);
607    default:
608      V8_Fatal(__FILE__, __LINE__, "Unexpected operator #%d:%s @ node #%d",
609               node->opcode(), node->op()->mnemonic(), node->id());
610  }
611}
612
613
614#if V8_TURBOFAN_BACKEND
615
616void InstructionSelector::VisitWord32Equal(Node* node) {
617  FlagsContinuation cont(kEqual, node);
618  Int32BinopMatcher m(node);
619  if (m.right().Is(0)) {
620    return VisitWord32Test(m.left().node(), &cont);
621  }
622  VisitWord32Compare(node, &cont);
623}
624
625
626void InstructionSelector::VisitInt32LessThan(Node* node) {
627  FlagsContinuation cont(kSignedLessThan, node);
628  VisitWord32Compare(node, &cont);
629}
630
631
632void InstructionSelector::VisitInt32LessThanOrEqual(Node* node) {
633  FlagsContinuation cont(kSignedLessThanOrEqual, node);
634  VisitWord32Compare(node, &cont);
635}
636
637
638void InstructionSelector::VisitUint32LessThan(Node* node) {
639  FlagsContinuation cont(kUnsignedLessThan, node);
640  VisitWord32Compare(node, &cont);
641}
642
643
644void InstructionSelector::VisitUint32LessThanOrEqual(Node* node) {
645  FlagsContinuation cont(kUnsignedLessThanOrEqual, node);
646  VisitWord32Compare(node, &cont);
647}
648
649
650void InstructionSelector::VisitWord64Equal(Node* node) {
651  FlagsContinuation cont(kEqual, node);
652  Int64BinopMatcher m(node);
653  if (m.right().Is(0)) {
654    return VisitWord64Test(m.left().node(), &cont);
655  }
656  VisitWord64Compare(node, &cont);
657}
658
659
660void InstructionSelector::VisitInt32AddWithOverflow(Node* node) {
661  if (Node* ovf = node->FindProjection(1)) {
662    FlagsContinuation cont(kOverflow, ovf);
663    return VisitInt32AddWithOverflow(node, &cont);
664  }
665  FlagsContinuation cont;
666  VisitInt32AddWithOverflow(node, &cont);
667}
668
669
670void InstructionSelector::VisitInt32SubWithOverflow(Node* node) {
671  if (Node* ovf = node->FindProjection(1)) {
672    FlagsContinuation cont(kOverflow, ovf);
673    return VisitInt32SubWithOverflow(node, &cont);
674  }
675  FlagsContinuation cont;
676  VisitInt32SubWithOverflow(node, &cont);
677}
678
679
680void InstructionSelector::VisitInt64LessThan(Node* node) {
681  FlagsContinuation cont(kSignedLessThan, node);
682  VisitWord64Compare(node, &cont);
683}
684
685
686void InstructionSelector::VisitInt64LessThanOrEqual(Node* node) {
687  FlagsContinuation cont(kSignedLessThanOrEqual, node);
688  VisitWord64Compare(node, &cont);
689}
690
691
692void InstructionSelector::VisitTruncateFloat64ToInt32(Node* node) {
693  OperandGenerator g(this);
694  Emit(kArchTruncateDoubleToI, g.DefineAsRegister(node),
695       g.UseRegister(node->InputAt(0)));
696}
697
698
699void InstructionSelector::VisitFloat64Equal(Node* node) {
700  FlagsContinuation cont(kUnorderedEqual, node);
701  VisitFloat64Compare(node, &cont);
702}
703
704
705void InstructionSelector::VisitFloat64LessThan(Node* node) {
706  FlagsContinuation cont(kUnorderedLessThan, node);
707  VisitFloat64Compare(node, &cont);
708}
709
710
711void InstructionSelector::VisitFloat64LessThanOrEqual(Node* node) {
712  FlagsContinuation cont(kUnorderedLessThanOrEqual, node);
713  VisitFloat64Compare(node, &cont);
714}
715
716#endif  // V8_TURBOFAN_BACKEND
717
718// 32 bit targets do not implement the following instructions.
719#if V8_TARGET_ARCH_32_BIT && V8_TURBOFAN_BACKEND
720
721void InstructionSelector::VisitWord64And(Node* node) { UNIMPLEMENTED(); }
722
723
724void InstructionSelector::VisitWord64Or(Node* node) { UNIMPLEMENTED(); }
725
726
727void InstructionSelector::VisitWord64Xor(Node* node) { UNIMPLEMENTED(); }
728
729
730void InstructionSelector::VisitWord64Shl(Node* node) { UNIMPLEMENTED(); }
731
732
733void InstructionSelector::VisitWord64Shr(Node* node) { UNIMPLEMENTED(); }
734
735
736void InstructionSelector::VisitWord64Sar(Node* node) { UNIMPLEMENTED(); }
737
738
739void InstructionSelector::VisitWord64Ror(Node* node) { UNIMPLEMENTED(); }
740
741
742void InstructionSelector::VisitInt64Add(Node* node) { UNIMPLEMENTED(); }
743
744
745void InstructionSelector::VisitInt64Sub(Node* node) { UNIMPLEMENTED(); }
746
747
748void InstructionSelector::VisitInt64Mul(Node* node) { UNIMPLEMENTED(); }
749
750
751void InstructionSelector::VisitInt64Div(Node* node) { UNIMPLEMENTED(); }
752
753
754void InstructionSelector::VisitInt64UDiv(Node* node) { UNIMPLEMENTED(); }
755
756
757void InstructionSelector::VisitInt64Mod(Node* node) { UNIMPLEMENTED(); }
758
759
760void InstructionSelector::VisitInt64UMod(Node* node) { UNIMPLEMENTED(); }
761
762
763void InstructionSelector::VisitChangeInt32ToInt64(Node* node) {
764  UNIMPLEMENTED();
765}
766
767
768void InstructionSelector::VisitChangeUint32ToUint64(Node* node) {
769  UNIMPLEMENTED();
770}
771
772
773void InstructionSelector::VisitTruncateInt64ToInt32(Node* node) {
774  UNIMPLEMENTED();
775}
776
777#endif  // V8_TARGET_ARCH_32_BIT && V8_TURBOFAN_BACKEND
778
779
780// 32-bit targets and unsupported architectures need dummy implementations of
781// selected 64-bit ops.
782#if V8_TARGET_ARCH_32_BIT || !V8_TURBOFAN_BACKEND
783
784void InstructionSelector::VisitWord64Test(Node* node, FlagsContinuation* cont) {
785  UNIMPLEMENTED();
786}
787
788
789void InstructionSelector::VisitWord64Compare(Node* node,
790                                             FlagsContinuation* cont) {
791  UNIMPLEMENTED();
792}
793
794#endif  // V8_TARGET_ARCH_32_BIT || !V8_TURBOFAN_BACKEND
795
796
797void InstructionSelector::VisitFinish(Node* node) {
798  OperandGenerator g(this);
799  Node* value = node->InputAt(0);
800  Emit(kArchNop, g.DefineSameAsFirst(node), g.Use(value));
801}
802
803
804void InstructionSelector::VisitParameter(Node* node) {
805  OperandGenerator g(this);
806  int index = OpParameter<int>(node);
807  Emit(kArchNop,
808       g.DefineAsLocation(node, linkage()->GetParameterLocation(index),
809                          linkage()->GetParameterType(index)));
810}
811
812
813void InstructionSelector::VisitPhi(Node* node) {
814  // TODO(bmeurer): Emit a PhiInstruction here.
815  for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) {
816    MarkAsUsed(*i);
817  }
818}
819
820
821void InstructionSelector::VisitProjection(Node* node) {
822  OperandGenerator g(this);
823  Node* value = node->InputAt(0);
824  switch (value->opcode()) {
825    case IrOpcode::kInt32AddWithOverflow:
826    case IrOpcode::kInt32SubWithOverflow:
827      if (OpParameter<size_t>(node) == 0) {
828        Emit(kArchNop, g.DefineSameAsFirst(node), g.Use(value));
829      } else {
830        DCHECK(OpParameter<size_t>(node) == 1u);
831        MarkAsUsed(value);
832      }
833      break;
834    default:
835      break;
836  }
837}
838
839
840void InstructionSelector::VisitConstant(Node* node) {
841  // We must emit a NOP here because every live range needs a defining
842  // instruction in the register allocator.
843  OperandGenerator g(this);
844  Emit(kArchNop, g.DefineAsConstant(node));
845}
846
847
848void InstructionSelector::VisitGoto(BasicBlock* target) {
849  if (IsNextInAssemblyOrder(target)) {
850    // fall through to the next block.
851    Emit(kArchNop, NULL)->MarkAsControl();
852  } else {
853    // jump to the next block.
854    OperandGenerator g(this);
855    Emit(kArchJmp, NULL, g.Label(target))->MarkAsControl();
856  }
857}
858
859
860void InstructionSelector::VisitBranch(Node* branch, BasicBlock* tbranch,
861                                      BasicBlock* fbranch) {
862  OperandGenerator g(this);
863  Node* user = branch;
864  Node* value = branch->InputAt(0);
865
866  FlagsContinuation cont(kNotEqual, tbranch, fbranch);
867
868  // If we can fall through to the true block, invert the branch.
869  if (IsNextInAssemblyOrder(tbranch)) {
870    cont.Negate();
871    cont.SwapBlocks();
872  }
873
874  // Try to combine with comparisons against 0 by simply inverting the branch.
875  while (CanCover(user, value)) {
876    if (value->opcode() == IrOpcode::kWord32Equal) {
877      Int32BinopMatcher m(value);
878      if (m.right().Is(0)) {
879        user = value;
880        value = m.left().node();
881        cont.Negate();
882      } else {
883        break;
884      }
885    } else if (value->opcode() == IrOpcode::kWord64Equal) {
886      Int64BinopMatcher m(value);
887      if (m.right().Is(0)) {
888        user = value;
889        value = m.left().node();
890        cont.Negate();
891      } else {
892        break;
893      }
894    } else {
895      break;
896    }
897  }
898
899  // Try to combine the branch with a comparison.
900  if (CanCover(user, value)) {
901    switch (value->opcode()) {
902      case IrOpcode::kWord32Equal:
903        cont.OverwriteAndNegateIfEqual(kEqual);
904        return VisitWord32Compare(value, &cont);
905      case IrOpcode::kInt32LessThan:
906        cont.OverwriteAndNegateIfEqual(kSignedLessThan);
907        return VisitWord32Compare(value, &cont);
908      case IrOpcode::kInt32LessThanOrEqual:
909        cont.OverwriteAndNegateIfEqual(kSignedLessThanOrEqual);
910        return VisitWord32Compare(value, &cont);
911      case IrOpcode::kUint32LessThan:
912        cont.OverwriteAndNegateIfEqual(kUnsignedLessThan);
913        return VisitWord32Compare(value, &cont);
914      case IrOpcode::kUint32LessThanOrEqual:
915        cont.OverwriteAndNegateIfEqual(kUnsignedLessThanOrEqual);
916        return VisitWord32Compare(value, &cont);
917      case IrOpcode::kWord64Equal:
918        cont.OverwriteAndNegateIfEqual(kEqual);
919        return VisitWord64Compare(value, &cont);
920      case IrOpcode::kInt64LessThan:
921        cont.OverwriteAndNegateIfEqual(kSignedLessThan);
922        return VisitWord64Compare(value, &cont);
923      case IrOpcode::kInt64LessThanOrEqual:
924        cont.OverwriteAndNegateIfEqual(kSignedLessThanOrEqual);
925        return VisitWord64Compare(value, &cont);
926      case IrOpcode::kFloat64Equal:
927        cont.OverwriteAndNegateIfEqual(kUnorderedEqual);
928        return VisitFloat64Compare(value, &cont);
929      case IrOpcode::kFloat64LessThan:
930        cont.OverwriteAndNegateIfEqual(kUnorderedLessThan);
931        return VisitFloat64Compare(value, &cont);
932      case IrOpcode::kFloat64LessThanOrEqual:
933        cont.OverwriteAndNegateIfEqual(kUnorderedLessThanOrEqual);
934        return VisitFloat64Compare(value, &cont);
935      case IrOpcode::kProjection:
936        // Check if this is the overflow output projection of an
937        // <Operation>WithOverflow node.
938        if (OpParameter<size_t>(value) == 1u) {
939          // We cannot combine the <Operation>WithOverflow with this branch
940          // unless the 0th projection (the use of the actual value of the
941          // <Operation> is either NULL, which means there's no use of the
942          // actual value, or was already defined, which means it is scheduled
943          // *AFTER* this branch).
944          Node* node = value->InputAt(0);
945          Node* result = node->FindProjection(0);
946          if (result == NULL || IsDefined(result)) {
947            switch (node->opcode()) {
948              case IrOpcode::kInt32AddWithOverflow:
949                cont.OverwriteAndNegateIfEqual(kOverflow);
950                return VisitInt32AddWithOverflow(node, &cont);
951              case IrOpcode::kInt32SubWithOverflow:
952                cont.OverwriteAndNegateIfEqual(kOverflow);
953                return VisitInt32SubWithOverflow(node, &cont);
954              default:
955                break;
956            }
957          }
958        }
959        break;
960      default:
961        break;
962    }
963  }
964
965  // Branch could not be combined with a compare, emit compare against 0.
966  VisitWord32Test(value, &cont);
967}
968
969
970void InstructionSelector::VisitReturn(Node* value) {
971  OperandGenerator g(this);
972  if (value != NULL) {
973    Emit(kArchRet, NULL, g.UseLocation(value, linkage()->GetReturnLocation(),
974                                       linkage()->GetReturnType()));
975  } else {
976    Emit(kArchRet, NULL);
977  }
978}
979
980
981void InstructionSelector::VisitThrow(Node* value) {
982  UNIMPLEMENTED();  // TODO(titzer)
983}
984
985
986FrameStateDescriptor* InstructionSelector::GetFrameStateDescriptor(
987    Node* state) {
988  DCHECK(state->opcode() == IrOpcode::kFrameState);
989  DCHECK_EQ(5, state->InputCount());
990  FrameStateCallInfo state_info = OpParameter<FrameStateCallInfo>(state);
991  int parameters = OpParameter<int>(state->InputAt(0));
992  int locals = OpParameter<int>(state->InputAt(1));
993  int stack = OpParameter<int>(state->InputAt(2));
994
995  FrameStateDescriptor* outer_state = NULL;
996  Node* outer_node = state->InputAt(4);
997  if (outer_node->opcode() == IrOpcode::kFrameState) {
998    outer_state = GetFrameStateDescriptor(outer_node);
999  }
1000
1001  return new (instruction_zone())
1002      FrameStateDescriptor(state_info, parameters, locals, stack, outer_state);
1003}
1004
1005
1006static InstructionOperand* UseOrImmediate(OperandGenerator* g, Node* input) {
1007  switch (input->opcode()) {
1008    case IrOpcode::kInt32Constant:
1009    case IrOpcode::kNumberConstant:
1010    case IrOpcode::kFloat64Constant:
1011    case IrOpcode::kHeapConstant:
1012      return g->UseImmediate(input);
1013    default:
1014      return g->UseUnique(input);
1015  }
1016}
1017
1018
1019void InstructionSelector::AddFrameStateInputs(
1020    Node* state, InstructionOperandVector* inputs,
1021    FrameStateDescriptor* descriptor) {
1022  DCHECK_EQ(IrOpcode::kFrameState, state->op()->opcode());
1023
1024  if (descriptor->outer_state() != NULL) {
1025    AddFrameStateInputs(state->InputAt(4), inputs, descriptor->outer_state());
1026  }
1027
1028  Node* parameters = state->InputAt(0);
1029  Node* locals = state->InputAt(1);
1030  Node* stack = state->InputAt(2);
1031  Node* context = state->InputAt(3);
1032
1033  DCHECK_EQ(IrOpcode::kStateValues, parameters->op()->opcode());
1034  DCHECK_EQ(IrOpcode::kStateValues, locals->op()->opcode());
1035  DCHECK_EQ(IrOpcode::kStateValues, stack->op()->opcode());
1036
1037  DCHECK_EQ(descriptor->parameters_count(), parameters->InputCount());
1038  DCHECK_EQ(descriptor->locals_count(), locals->InputCount());
1039  DCHECK_EQ(descriptor->stack_count(), stack->InputCount());
1040
1041  OperandGenerator g(this);
1042  for (int i = 0; i < static_cast<int>(descriptor->parameters_count()); i++) {
1043    inputs->push_back(UseOrImmediate(&g, parameters->InputAt(i)));
1044  }
1045  if (descriptor->HasContext()) {
1046    inputs->push_back(UseOrImmediate(&g, context));
1047  }
1048  for (int i = 0; i < static_cast<int>(descriptor->locals_count()); i++) {
1049    inputs->push_back(UseOrImmediate(&g, locals->InputAt(i)));
1050  }
1051  for (int i = 0; i < static_cast<int>(descriptor->stack_count()); i++) {
1052    inputs->push_back(UseOrImmediate(&g, stack->InputAt(i)));
1053  }
1054}
1055
1056
1057#if !V8_TURBOFAN_BACKEND
1058
1059#define DECLARE_UNIMPLEMENTED_SELECTOR(x) \
1060  void InstructionSelector::Visit##x(Node* node) { UNIMPLEMENTED(); }
1061MACHINE_OP_LIST(DECLARE_UNIMPLEMENTED_SELECTOR)
1062#undef DECLARE_UNIMPLEMENTED_SELECTOR
1063
1064
1065void InstructionSelector::VisitInt32AddWithOverflow(Node* node,
1066                                                    FlagsContinuation* cont) {
1067  UNIMPLEMENTED();
1068}
1069
1070
1071void InstructionSelector::VisitInt32SubWithOverflow(Node* node,
1072                                                    FlagsContinuation* cont) {
1073  UNIMPLEMENTED();
1074}
1075
1076
1077void InstructionSelector::VisitWord32Test(Node* node, FlagsContinuation* cont) {
1078  UNIMPLEMENTED();
1079}
1080
1081
1082void InstructionSelector::VisitWord32Compare(Node* node,
1083                                             FlagsContinuation* cont) {
1084  UNIMPLEMENTED();
1085}
1086
1087
1088void InstructionSelector::VisitFloat64Compare(Node* node,
1089                                              FlagsContinuation* cont) {
1090  UNIMPLEMENTED();
1091}
1092
1093
1094void InstructionSelector::VisitCall(Node* call, BasicBlock* continuation,
1095                                    BasicBlock* deoptimization) {}
1096
1097#endif  // !V8_TURBOFAN_BACKEND
1098
1099}  // namespace compiler
1100}  // namespace internal
1101}  // namespace v8
1102