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 #ifndef V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
      6 #define V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
      7 
      8 #include "src/compiler/instruction.h"
      9 #include "src/compiler/instruction-selector.h"
     10 #include "src/compiler/linkage.h"
     11 #include "src/compiler/schedule.h"
     12 #include "src/macro-assembler.h"
     13 
     14 namespace v8 {
     15 namespace internal {
     16 namespace compiler {
     17 
     18 // Helper struct containing data about a table or lookup switch.
     19 struct SwitchInfo {
     20   int32_t min_value;           // minimum value of {case_values}
     21   int32_t max_value;           // maximum value of {case_values}
     22   size_t value_range;          // |max_value - min_value| + 1
     23   size_t case_count;           // number of cases
     24   int32_t* case_values;        // actual case values, unsorted
     25   BasicBlock** case_branches;  // basic blocks corresponding to case values
     26   BasicBlock* default_branch;  // default branch target
     27 };
     28 
     29 // A helper class for the instruction selector that simplifies construction of
     30 // Operands. This class implements a base for architecture-specific helpers.
     31 class OperandGenerator {
     32  public:
     33   explicit OperandGenerator(InstructionSelector* selector)
     34       : selector_(selector) {}
     35 
     36   InstructionOperand NoOutput() {
     37     return InstructionOperand();  // Generates an invalid operand.
     38   }
     39 
     40   InstructionOperand DefineAsRegister(Node* node) {
     41     return Define(node,
     42                   UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
     43                                      GetVReg(node)));
     44   }
     45 
     46   InstructionOperand DefineSameAsFirst(Node* node) {
     47     return Define(node,
     48                   UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
     49                                      GetVReg(node)));
     50   }
     51 
     52   InstructionOperand DefineAsFixed(Node* node, Register reg) {
     53     return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
     54                                            reg.code(), GetVReg(node)));
     55   }
     56 
     57   InstructionOperand DefineAsFixed(Node* node, DoubleRegister reg) {
     58     return Define(node,
     59                   UnallocatedOperand(UnallocatedOperand::FIXED_DOUBLE_REGISTER,
     60                                      reg.code(), GetVReg(node)));
     61   }
     62 
     63   InstructionOperand DefineAsConstant(Node* node) {
     64     selector()->MarkAsDefined(node);
     65     int virtual_register = GetVReg(node);
     66     sequence()->AddConstant(virtual_register, ToConstant(node));
     67     return ConstantOperand(virtual_register);
     68   }
     69 
     70   InstructionOperand DefineAsLocation(Node* node, LinkageLocation location,
     71                                       MachineRepresentation rep) {
     72     return Define(node, ToUnallocatedOperand(location, rep, GetVReg(node)));
     73   }
     74 
     75   InstructionOperand DefineAsDualLocation(Node* node,
     76                                           LinkageLocation primary_location,
     77                                           LinkageLocation secondary_location) {
     78     return Define(node,
     79                   ToDualLocationUnallocatedOperand(
     80                       primary_location, secondary_location, GetVReg(node)));
     81   }
     82 
     83   InstructionOperand Use(Node* node) {
     84     return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
     85                                         UnallocatedOperand::USED_AT_START,
     86                                         GetVReg(node)));
     87   }
     88 
     89   InstructionOperand UseAny(Node* node) {
     90     return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
     91                                         UnallocatedOperand::USED_AT_START,
     92                                         GetVReg(node)));
     93   }
     94 
     95   InstructionOperand UseRegister(Node* node) {
     96     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
     97                                         UnallocatedOperand::USED_AT_START,
     98                                         GetVReg(node)));
     99   }
    100 
    101   InstructionOperand UseUniqueSlot(Node* node) {
    102     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
    103                                         GetVReg(node)));
    104   }
    105 
    106   // Use register or operand for the node. If a register is chosen, it won't
    107   // alias any temporary or output registers.
    108   InstructionOperand UseUnique(Node* node) {
    109     return Use(node,
    110                UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node)));
    111   }
    112 
    113   // Use a unique register for the node that does not alias any temporary or
    114   // output registers.
    115   InstructionOperand UseUniqueRegister(Node* node) {
    116     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    117                                         GetVReg(node)));
    118   }
    119 
    120   InstructionOperand UseFixed(Node* node, Register reg) {
    121     return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    122                                         reg.code(), GetVReg(node)));
    123   }
    124 
    125   InstructionOperand UseFixed(Node* node, DoubleRegister reg) {
    126     return Use(node,
    127                UnallocatedOperand(UnallocatedOperand::FIXED_DOUBLE_REGISTER,
    128                                   reg.code(), GetVReg(node)));
    129   }
    130 
    131   InstructionOperand UseExplicit(LinkageLocation location) {
    132     MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
    133     if (location.IsRegister()) {
    134       return ExplicitOperand(LocationOperand::REGISTER, rep,
    135                              location.AsRegister());
    136     } else {
    137       return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
    138                              location.GetLocation());
    139     }
    140   }
    141 
    142   InstructionOperand UseImmediate(Node* node) {
    143     return sequence()->AddImmediate(ToConstant(node));
    144   }
    145 
    146   InstructionOperand UseLocation(Node* node, LinkageLocation location,
    147                                  MachineRepresentation rep) {
    148     return Use(node, ToUnallocatedOperand(location, rep, GetVReg(node)));
    149   }
    150 
    151   // Used to force gap moves from the from_location to the to_location
    152   // immediately before an instruction.
    153   InstructionOperand UsePointerLocation(LinkageLocation to_location,
    154                                         LinkageLocation from_location) {
    155     MachineRepresentation rep = MachineType::PointerRepresentation();
    156     UnallocatedOperand casted_from_operand =
    157         UnallocatedOperand::cast(TempLocation(from_location, rep));
    158     selector_->Emit(kArchNop, casted_from_operand);
    159     return ToUnallocatedOperand(to_location, rep,
    160                                 casted_from_operand.virtual_register());
    161   }
    162 
    163   InstructionOperand TempRegister() {
    164     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    165                               UnallocatedOperand::USED_AT_START,
    166                               sequence()->NextVirtualRegister());
    167   }
    168 
    169   InstructionOperand TempDoubleRegister() {
    170     UnallocatedOperand op = UnallocatedOperand(
    171         UnallocatedOperand::MUST_HAVE_REGISTER,
    172         UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
    173     sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
    174                                      op.virtual_register());
    175     return op;
    176   }
    177 
    178   InstructionOperand TempRegister(Register reg) {
    179     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
    180                               InstructionOperand::kInvalidVirtualRegister);
    181   }
    182 
    183   InstructionOperand TempImmediate(int32_t imm) {
    184     return sequence()->AddImmediate(Constant(imm));
    185   }
    186 
    187   InstructionOperand TempLocation(LinkageLocation location,
    188                                   MachineRepresentation rep) {
    189     return ToUnallocatedOperand(location, rep,
    190                                 sequence()->NextVirtualRegister());
    191   }
    192 
    193   InstructionOperand Label(BasicBlock* block) {
    194     return sequence()->AddImmediate(
    195         Constant(RpoNumber::FromInt(block->rpo_number())));
    196   }
    197 
    198  protected:
    199   InstructionSelector* selector() const { return selector_; }
    200   InstructionSequence* sequence() const { return selector()->sequence(); }
    201   Zone* zone() const { return selector()->instruction_zone(); }
    202 
    203  private:
    204   int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
    205 
    206   static Constant ToConstant(const Node* node) {
    207     switch (node->opcode()) {
    208       case IrOpcode::kInt32Constant:
    209         return Constant(OpParameter<int32_t>(node));
    210       case IrOpcode::kInt64Constant:
    211         return Constant(OpParameter<int64_t>(node));
    212       case IrOpcode::kFloat32Constant:
    213         return Constant(OpParameter<float>(node));
    214       case IrOpcode::kFloat64Constant:
    215       case IrOpcode::kNumberConstant:
    216         return Constant(OpParameter<double>(node));
    217       case IrOpcode::kExternalConstant:
    218         return Constant(OpParameter<ExternalReference>(node));
    219       case IrOpcode::kHeapConstant:
    220         return Constant(OpParameter<Handle<HeapObject>>(node));
    221       default:
    222         break;
    223     }
    224     UNREACHABLE();
    225     return Constant(static_cast<int32_t>(0));
    226   }
    227 
    228   UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
    229     DCHECK_NOT_NULL(node);
    230     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    231     selector()->MarkAsDefined(node);
    232     return operand;
    233   }
    234 
    235   UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
    236     DCHECK_NOT_NULL(node);
    237     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    238     selector()->MarkAsUsed(node);
    239     return operand;
    240   }
    241 
    242   UnallocatedOperand ToDualLocationUnallocatedOperand(
    243       LinkageLocation primary_location, LinkageLocation secondary_location,
    244       int virtual_register) {
    245     // We only support the primary location being a register and the secondary
    246     // one a slot.
    247     DCHECK(primary_location.IsRegister() &&
    248            secondary_location.IsCalleeFrameSlot());
    249     int reg_id = primary_location.AsRegister();
    250     int slot_id = secondary_location.AsCalleeFrameSlot();
    251     return UnallocatedOperand(reg_id, slot_id, virtual_register);
    252   }
    253 
    254   UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
    255                                           MachineRepresentation rep,
    256                                           int virtual_register) {
    257     if (location.IsAnyRegister()) {
    258       // any machine register.
    259       return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    260                                 virtual_register);
    261     }
    262     if (location.IsCallerFrameSlot()) {
    263       // a location on the caller frame.
    264       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    265                                 location.AsCallerFrameSlot(), virtual_register);
    266     }
    267     if (location.IsCalleeFrameSlot()) {
    268       // a spill location on this (callee) frame.
    269       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    270                                 location.AsCalleeFrameSlot(), virtual_register);
    271     }
    272     // a fixed register.
    273     if (IsFloatingPoint(rep)) {
    274       return UnallocatedOperand(UnallocatedOperand::FIXED_DOUBLE_REGISTER,
    275                                 location.AsRegister(), virtual_register);
    276     }
    277     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    278                               location.AsRegister(), virtual_register);
    279   }
    280 
    281   InstructionSelector* selector_;
    282 };
    283 
    284 
    285 // The flags continuation is a way to combine a branch or a materialization
    286 // of a boolean value with an instruction that sets the flags register.
    287 // The whole instruction is treated as a unit by the register allocator, and
    288 // thus no spills or moves can be introduced between the flags-setting
    289 // instruction and the branch or set it should be combined with.
    290 class FlagsContinuation final {
    291  public:
    292   FlagsContinuation() : mode_(kFlags_none) {}
    293 
    294   // Creates a new flags continuation from the given condition and true/false
    295   // blocks.
    296   FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
    297                     BasicBlock* false_block)
    298       : mode_(kFlags_branch),
    299         condition_(condition),
    300         true_block_(true_block),
    301         false_block_(false_block) {
    302     DCHECK_NOT_NULL(true_block);
    303     DCHECK_NOT_NULL(false_block);
    304   }
    305 
    306   // Creates a new flags continuation from the given condition and result node.
    307   FlagsContinuation(FlagsCondition condition, Node* result)
    308       : mode_(kFlags_set), condition_(condition), result_(result) {
    309     DCHECK_NOT_NULL(result);
    310   }
    311 
    312   bool IsNone() const { return mode_ == kFlags_none; }
    313   bool IsBranch() const { return mode_ == kFlags_branch; }
    314   bool IsSet() const { return mode_ == kFlags_set; }
    315   FlagsCondition condition() const {
    316     DCHECK(!IsNone());
    317     return condition_;
    318   }
    319   Node* result() const {
    320     DCHECK(IsSet());
    321     return result_;
    322   }
    323   BasicBlock* true_block() const {
    324     DCHECK(IsBranch());
    325     return true_block_;
    326   }
    327   BasicBlock* false_block() const {
    328     DCHECK(IsBranch());
    329     return false_block_;
    330   }
    331 
    332   void Negate() {
    333     DCHECK(!IsNone());
    334     condition_ = NegateFlagsCondition(condition_);
    335   }
    336 
    337   void Commute() {
    338     DCHECK(!IsNone());
    339     condition_ = CommuteFlagsCondition(condition_);
    340   }
    341 
    342   void OverwriteAndNegateIfEqual(FlagsCondition condition) {
    343     bool negate = condition_ == kEqual;
    344     condition_ = condition;
    345     if (negate) Negate();
    346   }
    347 
    348   // Encodes this flags continuation into the given opcode.
    349   InstructionCode Encode(InstructionCode opcode) {
    350     opcode |= FlagsModeField::encode(mode_);
    351     if (mode_ != kFlags_none) {
    352       opcode |= FlagsConditionField::encode(condition_);
    353     }
    354     return opcode;
    355   }
    356 
    357  private:
    358   FlagsMode mode_;
    359   FlagsCondition condition_;
    360   Node* result_;             // Only valid if mode_ == kFlags_set.
    361   BasicBlock* true_block_;   // Only valid if mode_ == kFlags_branch.
    362   BasicBlock* false_block_;  // Only valid if mode_ == kFlags_branch.
    363 };
    364 
    365 }  // namespace compiler
    366 }  // namespace internal
    367 }  // namespace v8
    368 
    369 #endif  // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
    370