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   template <typename FPRegType>
     58   InstructionOperand DefineAsFixed(Node* node, FPRegType reg) {
     59     return Define(node,
     60                   UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
     61                                      reg.code(), GetVReg(node)));
     62   }
     63 
     64   InstructionOperand DefineAsConstant(Node* node) {
     65     selector()->MarkAsDefined(node);
     66     int virtual_register = GetVReg(node);
     67     sequence()->AddConstant(virtual_register, ToConstant(node));
     68     return ConstantOperand(virtual_register);
     69   }
     70 
     71   InstructionOperand DefineAsLocation(Node* node, LinkageLocation location,
     72                                       MachineRepresentation rep) {
     73     return Define(node, ToUnallocatedOperand(location, rep, GetVReg(node)));
     74   }
     75 
     76   InstructionOperand DefineAsDualLocation(Node* node,
     77                                           LinkageLocation primary_location,
     78                                           LinkageLocation secondary_location) {
     79     return Define(node,
     80                   ToDualLocationUnallocatedOperand(
     81                       primary_location, secondary_location, GetVReg(node)));
     82   }
     83 
     84   InstructionOperand Use(Node* node) {
     85     return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
     86                                         UnallocatedOperand::USED_AT_START,
     87                                         GetVReg(node)));
     88   }
     89 
     90   InstructionOperand UseAny(Node* node) {
     91     return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
     92                                         UnallocatedOperand::USED_AT_START,
     93                                         GetVReg(node)));
     94   }
     95 
     96   InstructionOperand UseRegister(Node* node) {
     97     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
     98                                         UnallocatedOperand::USED_AT_START,
     99                                         GetVReg(node)));
    100   }
    101 
    102   InstructionOperand UseUniqueSlot(Node* node) {
    103     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
    104                                         GetVReg(node)));
    105   }
    106 
    107   // Use register or operand for the node. If a register is chosen, it won't
    108   // alias any temporary or output registers.
    109   InstructionOperand UseUnique(Node* node) {
    110     return Use(node,
    111                UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node)));
    112   }
    113 
    114   // Use a unique register for the node that does not alias any temporary or
    115   // output registers.
    116   InstructionOperand UseUniqueRegister(Node* node) {
    117     return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    118                                         GetVReg(node)));
    119   }
    120 
    121   InstructionOperand UseFixed(Node* node, Register reg) {
    122     return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    123                                         reg.code(), GetVReg(node)));
    124   }
    125 
    126   template <typename FPRegType>
    127   InstructionOperand UseFixed(Node* node, FPRegType reg) {
    128     return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
    129                                         reg.code(), GetVReg(node)));
    130   }
    131 
    132   InstructionOperand UseExplicit(LinkageLocation location) {
    133     MachineRepresentation rep = InstructionSequence::DefaultRepresentation();
    134     if (location.IsRegister()) {
    135       return ExplicitOperand(LocationOperand::REGISTER, rep,
    136                              location.AsRegister());
    137     } else {
    138       return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
    139                              location.GetLocation());
    140     }
    141   }
    142 
    143   InstructionOperand UseImmediate(Node* node) {
    144     return sequence()->AddImmediate(ToConstant(node));
    145   }
    146 
    147   InstructionOperand UseLocation(Node* node, LinkageLocation location,
    148                                  MachineRepresentation rep) {
    149     return Use(node, ToUnallocatedOperand(location, rep, GetVReg(node)));
    150   }
    151 
    152   // Used to force gap moves from the from_location to the to_location
    153   // immediately before an instruction.
    154   InstructionOperand UsePointerLocation(LinkageLocation to_location,
    155                                         LinkageLocation from_location) {
    156     MachineRepresentation rep = MachineType::PointerRepresentation();
    157     UnallocatedOperand casted_from_operand =
    158         UnallocatedOperand::cast(TempLocation(from_location, rep));
    159     selector_->Emit(kArchNop, casted_from_operand);
    160     return ToUnallocatedOperand(to_location, rep,
    161                                 casted_from_operand.virtual_register());
    162   }
    163 
    164   InstructionOperand TempRegister() {
    165     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    166                               UnallocatedOperand::USED_AT_START,
    167                               sequence()->NextVirtualRegister());
    168   }
    169 
    170   InstructionOperand TempDoubleRegister() {
    171     UnallocatedOperand op = UnallocatedOperand(
    172         UnallocatedOperand::MUST_HAVE_REGISTER,
    173         UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
    174     sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
    175                                      op.virtual_register());
    176     return op;
    177   }
    178 
    179   InstructionOperand TempRegister(Register reg) {
    180     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
    181                               InstructionOperand::kInvalidVirtualRegister);
    182   }
    183 
    184   InstructionOperand TempImmediate(int32_t imm) {
    185     return sequence()->AddImmediate(Constant(imm));
    186   }
    187 
    188   InstructionOperand TempLocation(LinkageLocation location,
    189                                   MachineRepresentation rep) {
    190     return ToUnallocatedOperand(location, rep,
    191                                 sequence()->NextVirtualRegister());
    192   }
    193 
    194   InstructionOperand Label(BasicBlock* block) {
    195     return sequence()->AddImmediate(
    196         Constant(RpoNumber::FromInt(block->rpo_number())));
    197   }
    198 
    199  protected:
    200   InstructionSelector* selector() const { return selector_; }
    201   InstructionSequence* sequence() const { return selector()->sequence(); }
    202   Zone* zone() const { return selector()->instruction_zone(); }
    203 
    204  private:
    205   int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
    206 
    207   static Constant ToConstant(const Node* node) {
    208     switch (node->opcode()) {
    209       case IrOpcode::kInt32Constant:
    210         return Constant(OpParameter<int32_t>(node));
    211       case IrOpcode::kInt64Constant:
    212         return Constant(OpParameter<int64_t>(node));
    213       case IrOpcode::kFloat32Constant:
    214         return Constant(OpParameter<float>(node));
    215       case IrOpcode::kRelocatableInt32Constant:
    216       case IrOpcode::kRelocatableInt64Constant:
    217         return Constant(OpParameter<RelocatablePtrConstantInfo>(node));
    218       case IrOpcode::kFloat64Constant:
    219       case IrOpcode::kNumberConstant:
    220         return Constant(OpParameter<double>(node));
    221       case IrOpcode::kExternalConstant:
    222       case IrOpcode::kComment:
    223         return Constant(OpParameter<ExternalReference>(node));
    224       case IrOpcode::kHeapConstant:
    225         return Constant(OpParameter<Handle<HeapObject>>(node));
    226       default:
    227         break;
    228     }
    229     UNREACHABLE();
    230     return Constant(static_cast<int32_t>(0));
    231   }
    232 
    233   UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
    234     DCHECK_NOT_NULL(node);
    235     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    236     selector()->MarkAsDefined(node);
    237     return operand;
    238   }
    239 
    240   UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
    241     DCHECK_NOT_NULL(node);
    242     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    243     selector()->MarkAsUsed(node);
    244     return operand;
    245   }
    246 
    247   UnallocatedOperand ToDualLocationUnallocatedOperand(
    248       LinkageLocation primary_location, LinkageLocation secondary_location,
    249       int virtual_register) {
    250     // We only support the primary location being a register and the secondary
    251     // one a slot.
    252     DCHECK(primary_location.IsRegister() &&
    253            secondary_location.IsCalleeFrameSlot());
    254     int reg_id = primary_location.AsRegister();
    255     int slot_id = secondary_location.AsCalleeFrameSlot();
    256     return UnallocatedOperand(reg_id, slot_id, virtual_register);
    257   }
    258 
    259   UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
    260                                           MachineRepresentation rep,
    261                                           int virtual_register) {
    262     if (location.IsAnyRegister()) {
    263       // any machine register.
    264       return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    265                                 virtual_register);
    266     }
    267     if (location.IsCallerFrameSlot()) {
    268       // a location on the caller frame.
    269       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    270                                 location.AsCallerFrameSlot(), virtual_register);
    271     }
    272     if (location.IsCalleeFrameSlot()) {
    273       // a spill location on this (callee) frame.
    274       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    275                                 location.AsCalleeFrameSlot(), virtual_register);
    276     }
    277     // a fixed register.
    278     if (IsFloatingPoint(rep)) {
    279       return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
    280                                 location.AsRegister(), virtual_register);
    281     }
    282     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    283                               location.AsRegister(), virtual_register);
    284   }
    285 
    286   InstructionSelector* selector_;
    287 };
    288 
    289 
    290 // The flags continuation is a way to combine a branch or a materialization
    291 // of a boolean value with an instruction that sets the flags register.
    292 // The whole instruction is treated as a unit by the register allocator, and
    293 // thus no spills or moves can be introduced between the flags-setting
    294 // instruction and the branch or set it should be combined with.
    295 class FlagsContinuation final {
    296  public:
    297   FlagsContinuation() : mode_(kFlags_none) {}
    298 
    299   // Creates a new flags continuation from the given condition and true/false
    300   // blocks.
    301   FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
    302                     BasicBlock* false_block)
    303       : mode_(kFlags_branch),
    304         condition_(condition),
    305         true_block_(true_block),
    306         false_block_(false_block) {
    307     DCHECK_NOT_NULL(true_block);
    308     DCHECK_NOT_NULL(false_block);
    309   }
    310 
    311   // Creates a new flags continuation for an eager deoptimization exit.
    312   static FlagsContinuation ForDeoptimize(FlagsCondition condition,
    313                                          Node* frame_state) {
    314     return FlagsContinuation(kFlags_deoptimize, condition, frame_state);
    315   }
    316 
    317   // Creates a new flags continuation for a boolean value.
    318   static FlagsContinuation ForSet(FlagsCondition condition, Node* result) {
    319     return FlagsContinuation(kFlags_set, condition, result);
    320   }
    321 
    322   bool IsNone() const { return mode_ == kFlags_none; }
    323   bool IsBranch() const { return mode_ == kFlags_branch; }
    324   bool IsDeoptimize() const { return mode_ == kFlags_deoptimize; }
    325   bool IsSet() const { return mode_ == kFlags_set; }
    326   FlagsCondition condition() const {
    327     DCHECK(!IsNone());
    328     return condition_;
    329   }
    330   Node* frame_state() const {
    331     DCHECK(IsDeoptimize());
    332     return frame_state_or_result_;
    333   }
    334   Node* result() const {
    335     DCHECK(IsSet());
    336     return frame_state_or_result_;
    337   }
    338   BasicBlock* true_block() const {
    339     DCHECK(IsBranch());
    340     return true_block_;
    341   }
    342   BasicBlock* false_block() const {
    343     DCHECK(IsBranch());
    344     return false_block_;
    345   }
    346 
    347   void Negate() {
    348     DCHECK(!IsNone());
    349     condition_ = NegateFlagsCondition(condition_);
    350   }
    351 
    352   void Commute() {
    353     DCHECK(!IsNone());
    354     condition_ = CommuteFlagsCondition(condition_);
    355   }
    356 
    357   void OverwriteAndNegateIfEqual(FlagsCondition condition) {
    358     bool negate = condition_ == kEqual;
    359     condition_ = condition;
    360     if (negate) Negate();
    361   }
    362 
    363   // Encodes this flags continuation into the given opcode.
    364   InstructionCode Encode(InstructionCode opcode) {
    365     opcode |= FlagsModeField::encode(mode_);
    366     if (mode_ != kFlags_none) {
    367       opcode |= FlagsConditionField::encode(condition_);
    368     }
    369     return opcode;
    370   }
    371 
    372  private:
    373   FlagsContinuation(FlagsMode mode, FlagsCondition condition,
    374                     Node* frame_state_or_result)
    375       : mode_(mode),
    376         condition_(condition),
    377         frame_state_or_result_(frame_state_or_result) {
    378     DCHECK_NOT_NULL(frame_state_or_result);
    379   }
    380 
    381   FlagsMode const mode_;
    382   FlagsCondition condition_;
    383   Node* frame_state_or_result_;  // Only valid if mode_ == kFlags_deoptimize
    384                                  // or mode_ == kFlags_set.
    385   BasicBlock* true_block_;       // Only valid if mode_ == kFlags_branch.
    386   BasicBlock* false_block_;      // Only valid if mode_ == kFlags_branch.
    387 };
    388 
    389 }  // namespace compiler
    390 }  // namespace internal
    391 }  // namespace v8
    392 
    393 #endif  // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
    394