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