Home | History | Annotate | Download | only in compiler 
      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 
     12 namespace v8 {
     13 namespace internal {
     14 namespace compiler {
     15 
     16 InstructionSelector::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 
     29 void 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 
     69 Instruction* 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 
     78 Instruction* 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 
     87 Instruction* 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 
    100 Instruction* 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 
    114 Instruction* 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 
    126 Instruction* 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 
    137 Instruction* InstructionSelector::Emit(Instruction* instr) {
    138   instructions_.push_back(instr);
    139   return instr;
    140 }
    141 
    142 
    143 bool 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 
    149 bool InstructionSelector::CanCover(Node* user, Node* node) const {
    150   return node->OwnedBy(user) &&
    151          schedule()->block(node) == schedule()->block(user);
    152 }
    153 
    154 
    155 bool 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 
    164 void 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 
    173 bool 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 
    182 void 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 
    191 bool InstructionSelector::IsDouble(const Node* node) const {
    192   DCHECK_NOT_NULL(node);
    193   return sequence()->IsDouble(node->id());
    194 }
    195 
    196 
    197 void InstructionSelector::MarkAsDouble(Node* node) {
    198   DCHECK_NOT_NULL(node);
    199   DCHECK(!IsReference(node));
    200   sequence()->MarkAsDouble(node->id());
    201 }
    202 
    203 
    204 bool InstructionSelector::IsReference(const Node* node) const {
    205   DCHECK_NOT_NULL(node);
    206   return sequence()->IsReference(node->id());
    207 }
    208 
    209 
    210 void InstructionSelector::MarkAsReference(Node* node) {
    211   DCHECK_NOT_NULL(node);
    212   DCHECK(!IsDouble(node));
    213   sequence()->MarkAsReference(node->id());
    214 }
    215 
    216 
    217 void 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.
    235 CallBuffer::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.
    252 void 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 
    360 void 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 
    393 static 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 
    404 void 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 
    441 void 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 
    616 void 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 
    626 void InstructionSelector::VisitInt32LessThan(Node* node) {
    627   FlagsContinuation cont(kSignedLessThan, node);
    628   VisitWord32Compare(node, &cont);
    629 }
    630 
    631 
    632 void InstructionSelector::VisitInt32LessThanOrEqual(Node* node) {
    633   FlagsContinuation cont(kSignedLessThanOrEqual, node);
    634   VisitWord32Compare(node, &cont);
    635 }
    636 
    637 
    638 void InstructionSelector::VisitUint32LessThan(Node* node) {
    639   FlagsContinuation cont(kUnsignedLessThan, node);
    640   VisitWord32Compare(node, &cont);
    641 }
    642 
    643 
    644 void InstructionSelector::VisitUint32LessThanOrEqual(Node* node) {
    645   FlagsContinuation cont(kUnsignedLessThanOrEqual, node);
    646   VisitWord32Compare(node, &cont);
    647 }
    648 
    649 
    650 void 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 
    660 void 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 
    670 void 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 
    680 void InstructionSelector::VisitInt64LessThan(Node* node) {
    681   FlagsContinuation cont(kSignedLessThan, node);
    682   VisitWord64Compare(node, &cont);
    683 }
    684 
    685 
    686 void InstructionSelector::VisitInt64LessThanOrEqual(Node* node) {
    687   FlagsContinuation cont(kSignedLessThanOrEqual, node);
    688   VisitWord64Compare(node, &cont);
    689 }
    690 
    691 
    692 void InstructionSelector::VisitTruncateFloat64ToInt32(Node* node) {
    693   OperandGenerator g(this);
    694   Emit(kArchTruncateDoubleToI, g.DefineAsRegister(node),
    695        g.UseRegister(node->InputAt(0)));
    696 }
    697 
    698 
    699 void InstructionSelector::VisitFloat64Equal(Node* node) {
    700   FlagsContinuation cont(kUnorderedEqual, node);
    701   VisitFloat64Compare(node, &cont);
    702 }
    703 
    704 
    705 void InstructionSelector::VisitFloat64LessThan(Node* node) {
    706   FlagsContinuation cont(kUnorderedLessThan, node);
    707   VisitFloat64Compare(node, &cont);
    708 }
    709 
    710 
    711 void 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 
    721 void InstructionSelector::VisitWord64And(Node* node) { UNIMPLEMENTED(); }
    722 
    723 
    724 void InstructionSelector::VisitWord64Or(Node* node) { UNIMPLEMENTED(); }
    725 
    726 
    727 void InstructionSelector::VisitWord64Xor(Node* node) { UNIMPLEMENTED(); }
    728 
    729 
    730 void InstructionSelector::VisitWord64Shl(Node* node) { UNIMPLEMENTED(); }
    731 
    732 
    733 void InstructionSelector::VisitWord64Shr(Node* node) { UNIMPLEMENTED(); }
    734 
    735 
    736 void InstructionSelector::VisitWord64Sar(Node* node) { UNIMPLEMENTED(); }
    737 
    738 
    739 void InstructionSelector::VisitWord64Ror(Node* node) { UNIMPLEMENTED(); }
    740 
    741 
    742 void InstructionSelector::VisitInt64Add(Node* node) { UNIMPLEMENTED(); }
    743 
    744 
    745 void InstructionSelector::VisitInt64Sub(Node* node) { UNIMPLEMENTED(); }
    746 
    747 
    748 void InstructionSelector::VisitInt64Mul(Node* node) { UNIMPLEMENTED(); }
    749 
    750 
    751 void InstructionSelector::VisitInt64Div(Node* node) { UNIMPLEMENTED(); }
    752 
    753 
    754 void InstructionSelector::VisitInt64UDiv(Node* node) { UNIMPLEMENTED(); }
    755 
    756 
    757 void InstructionSelector::VisitInt64Mod(Node* node) { UNIMPLEMENTED(); }
    758 
    759 
    760 void InstructionSelector::VisitInt64UMod(Node* node) { UNIMPLEMENTED(); }
    761 
    762 
    763 void InstructionSelector::VisitChangeInt32ToInt64(Node* node) {
    764   UNIMPLEMENTED();
    765 }
    766 
    767 
    768 void InstructionSelector::VisitChangeUint32ToUint64(Node* node) {
    769   UNIMPLEMENTED();
    770 }
    771 
    772 
    773 void 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 
    784 void InstructionSelector::VisitWord64Test(Node* node, FlagsContinuation* cont) {
    785   UNIMPLEMENTED();
    786 }
    787 
    788 
    789 void InstructionSelector::VisitWord64Compare(Node* node,
    790                                              FlagsContinuation* cont) {
    791   UNIMPLEMENTED();
    792 }
    793 
    794 #endif  // V8_TARGET_ARCH_32_BIT || !V8_TURBOFAN_BACKEND
    795 
    796 
    797 void 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 
    804 void 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 
    813 void 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 
    821 void 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 
    840 void 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 
    848 void 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 
    860 void 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 
    970 void 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 
    981 void InstructionSelector::VisitThrow(Node* value) {
    982   UNIMPLEMENTED();  // TODO(titzer)
    983 }
    984 
    985 
    986 FrameStateDescriptor* 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 
   1006 static 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 
   1019 void 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(); }
   1061 MACHINE_OP_LIST(DECLARE_UNIMPLEMENTED_SELECTOR)
   1062 #undef DECLARE_UNIMPLEMENTED_SELECTOR
   1063 
   1064 
   1065 void InstructionSelector::VisitInt32AddWithOverflow(Node* node,
   1066                                                     FlagsContinuation* cont) {
   1067   UNIMPLEMENTED();
   1068 }
   1069 
   1070 
   1071 void InstructionSelector::VisitInt32SubWithOverflow(Node* node,
   1072                                                     FlagsContinuation* cont) {
   1073   UNIMPLEMENTED();
   1074 }
   1075 
   1076 
   1077 void InstructionSelector::VisitWord32Test(Node* node, FlagsContinuation* cont) {
   1078   UNIMPLEMENTED();
   1079 }
   1080 
   1081 
   1082 void InstructionSelector::VisitWord32Compare(Node* node,
   1083                                              FlagsContinuation* cont) {
   1084   UNIMPLEMENTED();
   1085 }
   1086 
   1087 
   1088 void InstructionSelector::VisitFloat64Compare(Node* node,
   1089                                               FlagsContinuation* cont) {
   1090   UNIMPLEMENTED();
   1091 }
   1092 
   1093 
   1094 void 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