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-selector.h"
      9 #include "src/compiler/instruction.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 struct CaseInfo {
     19   int32_t value;  // The case value.
     20   int32_t order;  // The order for lowering to comparisons (less means earlier).
     21   BasicBlock* branch;  // The basic blocks corresponding to the case value.
     22 };
     23 
     24 inline bool operator<(const CaseInfo& l, const CaseInfo& r) {
     25   return l.order < r.order;
     26 }
     27 
     28 // Helper struct containing data about a table or lookup switch.
     29 class SwitchInfo {
     30  public:
     31   SwitchInfo(ZoneVector<CaseInfo>& cases, int32_t min_value, int32_t max_value,
     32              BasicBlock* default_branch)
     33       : cases_(cases),
     34         min_value_(min_value),
     35         max_value_(min_value),
     36         default_branch_(default_branch) {
     37     if (cases.size() != 0) {
     38       DCHECK_LE(min_value, max_value);
     39       // Note that {value_range} can be 0 if {min_value} is -2^31 and
     40       // {max_value} is 2^31-1, so don't assume that it's non-zero below.
     41       value_range_ =
     42           1u + bit_cast<uint32_t>(max_value) - bit_cast<uint32_t>(min_value);
     43     } else {
     44       value_range_ = 0;
     45     }
     46   }
     47 
     48   // Ensure that comparison order of if-cascades is preserved.
     49   std::vector<CaseInfo> CasesSortedByOriginalOrder() const {
     50     std::vector<CaseInfo> result(cases_.begin(), cases_.end());
     51     std::stable_sort(result.begin(), result.end());
     52     return result;
     53   }
     54   std::vector<CaseInfo> CasesSortedByValue() const {
     55     std::vector<CaseInfo> result(cases_.begin(), cases_.end());
     56     std::stable_sort(result.begin(), result.end(),
     57                      [](CaseInfo a, CaseInfo b) { return a.value < b.value; });
     58     return result;
     59   }
     60   const ZoneVector<CaseInfo>& CasesUnsorted() const { return cases_; }
     61   int32_t min_value() const { return min_value_; }
     62   int32_t max_value() const { return max_value_; }
     63   size_t value_range() const { return value_range_; }
     64   size_t case_count() const { return cases_.size(); }
     65   BasicBlock* default_branch() const { return default_branch_; }
     66 
     67  private:
     68   const ZoneVector<CaseInfo>& cases_;
     69   int32_t min_value_;   // minimum value of {cases_}
     70   int32_t max_value_;   // maximum value of {cases_}
     71   size_t value_range_;  // |max_value - min_value| + 1
     72   BasicBlock* default_branch_;
     73 };
     74 
     75 // A helper class for the instruction selector that simplifies construction of
     76 // Operands. This class implements a base for architecture-specific helpers.
     77 class OperandGenerator {
     78  public:
     79   explicit OperandGenerator(InstructionSelector* selector)
     80       : selector_(selector) {}
     81 
     82   InstructionOperand NoOutput() {
     83     return InstructionOperand();  // Generates an invalid operand.
     84   }
     85 
     86   InstructionOperand DefineAsRegister(Node* node) {
     87     return Define(node,
     88                   UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
     89                                      GetVReg(node)));
     90   }
     91 
     92   InstructionOperand DefineSameAsFirst(Node* node) {
     93     return Define(node,
     94                   UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
     95                                      GetVReg(node)));
     96   }
     97 
     98   InstructionOperand DefineAsFixed(Node* node, Register reg) {
     99     return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    100                                            reg.code(), GetVReg(node)));
    101   }
    102 
    103   template <typename FPRegType>
    104   InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
    105     return Define(node,
    106                   UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
    107                                      reg.code(), GetVReg(node)));
    108   }
    109 
    110   InstructionOperand DefineAsConstant(Node* node) {
    111     return DefineAsConstant(node, ToConstant(node));
    112   }
    113 
    114   InstructionOperand DefineAsConstant(Node* node, Constant constant) {
    115     selector()->MarkAsDefined(node);
    116     int virtual_register = GetVReg(node);
    117     sequence()->AddConstant(virtual_register, constant);
    118     return ConstantOperand(virtual_register);
    119   }
    120 
    121   InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
    122     return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
    123   }
    124 
    125   InstructionOperand DefineAsDualLocation(Node* node,
    126                                           LinkageLocation primary_location,
    127                                           LinkageLocation secondary_location) {
    128     return Define(node,
    129                   ToDualLocationUnallocatedOperand(
    130                       primary_location, secondary_location, GetVReg(node)));
    131   }
    132 
    133   InstructionOperand Use(Node* node) {
    134     return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
    135                                         UnallocatedOperand::USED_AT_START,
    136                                         GetVReg(node)));
    137   }
    138 
    139   InstructionOperand UseAnyAtEnd(Node* node) {
    140     return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
    141                                         UnallocatedOperand::USED_AT_END,
    142                                         GetVReg(node)));
    143   }
    144 
    145   InstructionOperand UseAny(Node* node) {
    146     return Use(node, UnallocatedOperand(UnallocatedOperand::REGISTER_OR_SLOT,
    147                                         UnallocatedOperand::USED_AT_START,
    148                                         GetVReg(node)));
    149   }
    150 
    151   InstructionOperand UseRegisterOrSlotOrConstant(Node* node) {
    152     return Use(node, UnallocatedOperand(
    153                          UnallocatedOperand::REGISTER_OR_SLOT_OR_CONSTANT,
    154                          UnallocatedOperand::USED_AT_START, GetVReg(node)));
    155   }
    156 
    157   InstructionOperand UseRegister(Node* node) {
    158     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    159                                         UnallocatedOperand::USED_AT_START,
    160                                         GetVReg(node)));
    161   }
    162 
    163   InstructionOperand UseUniqueSlot(Node* node) {
    164     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
    165                                         GetVReg(node)));
    166   }
    167 
    168   // Use register or operand for the node. If a register is chosen, it won't
    169   // alias any temporary or output registers.
    170   InstructionOperand UseUnique(Node* node) {
    171     return Use(node,
    172                UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node)));
    173   }
    174 
    175   // Use a unique register for the node that does not alias any temporary or
    176   // output registers.
    177   InstructionOperand UseUniqueRegister(Node* node) {
    178     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    179                                         GetVReg(node)));
    180   }
    181 
    182   InstructionOperand UseFixed(Node* node, Register reg) {
    183     return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    184                                         reg.code(), GetVReg(node)));
    185   }
    186 
    187   template <typename FPRegType>
    188   InstructionOperand UseFixed(Node* node, FPRegType reg) {
    189     return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
    190                                         reg.code(), GetVReg(node)));
    191   }
    192 
    193   InstructionOperand UseExplicit(LinkageLocation location) {
    194     MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
    195     if (location.IsRegister()) {
    196       return ExplicitOperand(LocationOperand::REGISTER, rep,
    197                              location.AsRegister());
    198     } else {
    199       return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
    200                              location.GetLocation());
    201     }
    202   }
    203 
    204   InstructionOperand UseImmediate(int immediate) {
    205     return sequence()->AddImmediate(Constant(immediate));
    206   }
    207 
    208   InstructionOperand UseImmediate(Node* node) {
    209     return sequence()->AddImmediate(ToConstant(node));
    210   }
    211 
    212   InstructionOperand UseNegatedImmediate(Node* node) {
    213     return sequence()->AddImmediate(ToNegatedConstant(node));
    214   }
    215 
    216   InstructionOperand UseLocation(Node* node, LinkageLocation location) {
    217     return Use(node, ToUnallocatedOperand(location, GetVReg(node)));
    218   }
    219 
    220   // Used to force gap moves from the from_location to the to_location
    221   // immediately before an instruction.
    222   InstructionOperand UsePointerLocation(LinkageLocation to_location,
    223                                         LinkageLocation from_location) {
    224     UnallocatedOperand casted_from_operand =
    225         UnallocatedOperand::cast(TempLocation(from_location));
    226     selector_->Emit(kArchNop, casted_from_operand);
    227     return ToUnallocatedOperand(to_location,
    228                                 casted_from_operand.virtual_register());
    229   }
    230 
    231   InstructionOperand TempRegister() {
    232     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    233                               UnallocatedOperand::USED_AT_START,
    234                               sequence()->NextVirtualRegister());
    235   }
    236 
    237   int AllocateVirtualRegister() { return sequence()->NextVirtualRegister(); }
    238 
    239   InstructionOperand DefineSameAsFirstForVreg(int vreg) {
    240     return UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, vreg);
    241   }
    242 
    243   InstructionOperand DefineAsRegistertForVreg(int vreg) {
    244     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg);
    245   }
    246 
    247   InstructionOperand UseRegisterForVreg(int vreg) {
    248     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    249                               UnallocatedOperand::USED_AT_START, vreg);
    250   }
    251 
    252   InstructionOperand TempDoubleRegister() {
    253     UnallocatedOperand op = UnallocatedOperand(
    254         UnallocatedOperand::MUST_HAVE_REGISTER,
    255         UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
    256     sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
    257                                      op.virtual_register());
    258     return op;
    259   }
    260 
    261   InstructionOperand TempSimd128Register() {
    262     UnallocatedOperand op = UnallocatedOperand(
    263         UnallocatedOperand::MUST_HAVE_REGISTER,
    264         UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
    265     sequence()->MarkAsRepresentation(MachineRepresentation::kSimd128,
    266                                      op.virtual_register());
    267     return op;
    268   }
    269 
    270   InstructionOperand TempRegister(Register reg) {
    271     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
    272                               InstructionOperand::kInvalidVirtualRegister);
    273   }
    274 
    275   InstructionOperand TempImmediate(int32_t imm) {
    276     return sequence()->AddImmediate(Constant(imm));
    277   }
    278 
    279   InstructionOperand TempLocation(LinkageLocation location) {
    280     return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
    281   }
    282 
    283   InstructionOperand Label(BasicBlock* block) {
    284     return sequence()->AddImmediate(
    285         Constant(RpoNumber::FromInt(block->rpo_number())));
    286   }
    287 
    288  protected:
    289   InstructionSelector* selector() const { return selector_; }
    290   InstructionSequence* sequence() const { return selector()->sequence(); }
    291   Zone* zone() const { return selector()->instruction_zone(); }
    292 
    293  private:
    294   int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
    295 
    296   static Constant ToConstant(const Node* node) {
    297     switch (node->opcode()) {
    298       case IrOpcode::kInt32Constant:
    299         return Constant(OpParameter<int32_t>(node->op()));
    300       case IrOpcode::kInt64Constant:
    301         return Constant(OpParameter<int64_t>(node->op()));
    302       case IrOpcode::kFloat32Constant:
    303         return Constant(OpParameter<float>(node->op()));
    304       case IrOpcode::kRelocatableInt32Constant:
    305       case IrOpcode::kRelocatableInt64Constant:
    306         return Constant(OpParameter<RelocatablePtrConstantInfo>(node->op()));
    307       case IrOpcode::kFloat64Constant:
    308       case IrOpcode::kNumberConstant:
    309         return Constant(OpParameter<double>(node->op()));
    310       case IrOpcode::kExternalConstant:
    311         return Constant(OpParameter<ExternalReference>(node->op()));
    312       case IrOpcode::kComment: {
    313         // We cannot use {intptr_t} here, since the Constant constructor would
    314         // be ambiguous on some architectures.
    315         using ptrsize_int_t =
    316             std::conditional<kPointerSize == 8, int64_t, int32_t>::type;
    317         return Constant(reinterpret_cast<ptrsize_int_t>(
    318             OpParameter<const char*>(node->op())));
    319       }
    320       case IrOpcode::kHeapConstant:
    321         return Constant(HeapConstantOf(node->op()));
    322       case IrOpcode::kDeadValue: {
    323         switch (DeadValueRepresentationOf(node->op())) {
    324           case MachineRepresentation::kBit:
    325           case MachineRepresentation::kWord32:
    326           case MachineRepresentation::kTagged:
    327           case MachineRepresentation::kTaggedSigned:
    328           case MachineRepresentation::kTaggedPointer:
    329             return Constant(static_cast<int32_t>(0));
    330           case MachineRepresentation::kFloat64:
    331             return Constant(static_cast<double>(0));
    332           case MachineRepresentation::kFloat32:
    333             return Constant(static_cast<float>(0));
    334           default:
    335             UNREACHABLE();
    336         }
    337         break;
    338       }
    339       default:
    340         break;
    341     }
    342     UNREACHABLE();
    343   }
    344 
    345   static Constant ToNegatedConstant(const Node* node) {
    346     switch (node->opcode()) {
    347       case IrOpcode::kInt32Constant:
    348         return Constant(-OpParameter<int32_t>(node->op()));
    349       case IrOpcode::kInt64Constant:
    350         return Constant(-OpParameter<int64_t>(node->op()));
    351       default:
    352         break;
    353     }
    354     UNREACHABLE();
    355   }
    356 
    357   UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
    358     DCHECK_NOT_NULL(node);
    359     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    360     selector()->MarkAsDefined(node);
    361     return operand;
    362   }
    363 
    364   UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
    365     DCHECK_NOT_NULL(node);
    366     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    367     selector()->MarkAsUsed(node);
    368     return operand;
    369   }
    370 
    371   UnallocatedOperand ToDualLocationUnallocatedOperand(
    372       LinkageLocation primary_location, LinkageLocation secondary_location,
    373       int virtual_register) {
    374     // We only support the primary location being a register and the secondary
    375     // one a slot.
    376     DCHECK(primary_location.IsRegister() &&
    377            secondary_location.IsCalleeFrameSlot());
    378     int reg_id = primary_location.AsRegister();
    379     int slot_id = secondary_location.AsCalleeFrameSlot();
    380     return UnallocatedOperand(reg_id, slot_id, virtual_register);
    381   }
    382 
    383   UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
    384                                           int virtual_register) {
    385     if (location.IsAnyRegister()) {
    386       // any machine register.
    387       return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    388                                 virtual_register);
    389     }
    390     if (location.IsCallerFrameSlot()) {
    391       // a location on the caller frame.
    392       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    393                                 location.AsCallerFrameSlot(), virtual_register);
    394     }
    395     if (location.IsCalleeFrameSlot()) {
    396       // a spill location on this (callee) frame.
    397       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    398                                 location.AsCalleeFrameSlot(), virtual_register);
    399     }
    400     // a fixed register.
    401     if (IsFloatingPoint(location.GetType().representation())) {
    402       return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
    403                                 location.AsRegister(), virtual_register);
    404     }
    405     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    406                               location.AsRegister(), virtual_register);
    407   }
    408 
    409   InstructionSelector* selector_;
    410 };
    411 
    412 }  // namespace compiler
    413 }  // namespace internal
    414 }  // namespace v8
    415 
    416 #endif  // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
    417