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 // 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   int AllocateVirtualRegister() { return sequence()->NextVirtualRegister(); }
    186 
    187   InstructionOperand DefineSameAsFirstForVreg(int vreg) {
    188     return UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, vreg);
    189   }
    190 
    191   InstructionOperand DefineAsRegistertForVreg(int vreg) {
    192     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg);
    193   }
    194 
    195   InstructionOperand UseRegisterForVreg(int vreg) {
    196     return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    197                               UnallocatedOperand::USED_AT_START, vreg);
    198   }
    199 
    200   InstructionOperand TempDoubleRegister() {
    201     UnallocatedOperand op = UnallocatedOperand(
    202         UnallocatedOperand::MUST_HAVE_REGISTER,
    203         UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
    204     sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
    205                                      op.virtual_register());
    206     return op;
    207   }
    208 
    209   InstructionOperand TempRegister(Register reg) {
    210     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER, reg.code(),
    211                               InstructionOperand::kInvalidVirtualRegister);
    212   }
    213 
    214   InstructionOperand TempImmediate(int32_t imm) {
    215     return sequence()->AddImmediate(Constant(imm));
    216   }
    217 
    218   InstructionOperand TempLocation(LinkageLocation location) {
    219     return ToUnallocatedOperand(location, sequence()->NextVirtualRegister());
    220   }
    221 
    222   InstructionOperand Label(BasicBlock* block) {
    223     return sequence()->AddImmediate(
    224         Constant(RpoNumber::FromInt(block->rpo_number())));
    225   }
    226 
    227  protected:
    228   InstructionSelector* selector() const { return selector_; }
    229   InstructionSequence* sequence() const { return selector()->sequence(); }
    230   Zone* zone() const { return selector()->instruction_zone(); }
    231 
    232  private:
    233   int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }
    234 
    235   static Constant ToConstant(const Node* node) {
    236     switch (node->opcode()) {
    237       case IrOpcode::kInt32Constant:
    238         return Constant(OpParameter<int32_t>(node));
    239       case IrOpcode::kInt64Constant:
    240         return Constant(OpParameter<int64_t>(node));
    241       case IrOpcode::kFloat32Constant:
    242         return Constant(OpParameter<float>(node));
    243       case IrOpcode::kRelocatableInt32Constant:
    244       case IrOpcode::kRelocatableInt64Constant:
    245         return Constant(OpParameter<RelocatablePtrConstantInfo>(node));
    246       case IrOpcode::kFloat64Constant:
    247       case IrOpcode::kNumberConstant:
    248         return Constant(OpParameter<double>(node));
    249       case IrOpcode::kExternalConstant:
    250       case IrOpcode::kComment:
    251         return Constant(OpParameter<ExternalReference>(node));
    252       case IrOpcode::kHeapConstant:
    253         return Constant(OpParameter<Handle<HeapObject>>(node));
    254       default:
    255         break;
    256     }
    257     UNREACHABLE();
    258     return Constant(static_cast<int32_t>(0));
    259   }
    260 
    261   static Constant ToNegatedConstant(const Node* node) {
    262     switch (node->opcode()) {
    263       case IrOpcode::kInt32Constant:
    264         return Constant(-OpParameter<int32_t>(node));
    265       case IrOpcode::kInt64Constant:
    266         return Constant(-OpParameter<int64_t>(node));
    267       default:
    268         break;
    269     }
    270     UNREACHABLE();
    271     return Constant(static_cast<int32_t>(0));
    272   }
    273 
    274   UnallocatedOperand Define(Node* node, UnallocatedOperand operand) {
    275     DCHECK_NOT_NULL(node);
    276     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    277     selector()->MarkAsDefined(node);
    278     return operand;
    279   }
    280 
    281   UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
    282     DCHECK_NOT_NULL(node);
    283     DCHECK_EQ(operand.virtual_register(), GetVReg(node));
    284     selector()->MarkAsUsed(node);
    285     return operand;
    286   }
    287 
    288   UnallocatedOperand ToDualLocationUnallocatedOperand(
    289       LinkageLocation primary_location, LinkageLocation secondary_location,
    290       int virtual_register) {
    291     // We only support the primary location being a register and the secondary
    292     // one a slot.
    293     DCHECK(primary_location.IsRegister() &&
    294            secondary_location.IsCalleeFrameSlot());
    295     int reg_id = primary_location.AsRegister();
    296     int slot_id = secondary_location.AsCalleeFrameSlot();
    297     return UnallocatedOperand(reg_id, slot_id, virtual_register);
    298   }
    299 
    300   UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
    301                                           int virtual_register) {
    302     if (location.IsAnyRegister()) {
    303       // any machine register.
    304       return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
    305                                 virtual_register);
    306     }
    307     if (location.IsCallerFrameSlot()) {
    308       // a location on the caller frame.
    309       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    310                                 location.AsCallerFrameSlot(), virtual_register);
    311     }
    312     if (location.IsCalleeFrameSlot()) {
    313       // a spill location on this (callee) frame.
    314       return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
    315                                 location.AsCalleeFrameSlot(), virtual_register);
    316     }
    317     // a fixed register.
    318     if (IsFloatingPoint(location.GetType().representation())) {
    319       return UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
    320                                 location.AsRegister(), virtual_register);
    321     }
    322     return UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
    323                               location.AsRegister(), virtual_register);
    324   }
    325 
    326   InstructionSelector* selector_;
    327 };
    328 
    329 
    330 // The flags continuation is a way to combine a branch or a materialization
    331 // of a boolean value with an instruction that sets the flags register.
    332 // The whole instruction is treated as a unit by the register allocator, and
    333 // thus no spills or moves can be introduced between the flags-setting
    334 // instruction and the branch or set it should be combined with.
    335 class FlagsContinuation final {
    336  public:
    337   FlagsContinuation() : mode_(kFlags_none) {}
    338 
    339   // Creates a new flags continuation from the given condition and true/false
    340   // blocks.
    341   FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
    342                     BasicBlock* false_block)
    343       : mode_(kFlags_branch),
    344         condition_(condition),
    345         true_block_(true_block),
    346         false_block_(false_block) {
    347     DCHECK_NOT_NULL(true_block);
    348     DCHECK_NOT_NULL(false_block);
    349   }
    350 
    351   // Creates a new flags continuation for an eager deoptimization exit.
    352   static FlagsContinuation ForDeoptimize(FlagsCondition condition,
    353                                          DeoptimizeKind kind,
    354                                          DeoptimizeReason reason,
    355                                          Node* frame_state) {
    356     return FlagsContinuation(condition, kind, reason, frame_state);
    357   }
    358 
    359   // Creates a new flags continuation for a boolean value.
    360   static FlagsContinuation ForSet(FlagsCondition condition, Node* result) {
    361     return FlagsContinuation(condition, result);
    362   }
    363 
    364   // Creates a new flags continuation for a wasm trap.
    365   static FlagsContinuation ForTrap(FlagsCondition condition,
    366                                    Runtime::FunctionId trap_id, Node* result) {
    367     return FlagsContinuation(condition, trap_id, result);
    368   }
    369 
    370   bool IsNone() const { return mode_ == kFlags_none; }
    371   bool IsBranch() const { return mode_ == kFlags_branch; }
    372   bool IsDeoptimize() const { return mode_ == kFlags_deoptimize; }
    373   bool IsSet() const { return mode_ == kFlags_set; }
    374   bool IsTrap() const { return mode_ == kFlags_trap; }
    375   FlagsCondition condition() const {
    376     DCHECK(!IsNone());
    377     return condition_;
    378   }
    379   DeoptimizeKind kind() const {
    380     DCHECK(IsDeoptimize());
    381     return kind_;
    382   }
    383   DeoptimizeReason reason() const {
    384     DCHECK(IsDeoptimize());
    385     return reason_;
    386   }
    387   Node* frame_state() const {
    388     DCHECK(IsDeoptimize());
    389     return frame_state_or_result_;
    390   }
    391   Node* result() const {
    392     DCHECK(IsSet());
    393     return frame_state_or_result_;
    394   }
    395   Runtime::FunctionId trap_id() const {
    396     DCHECK(IsTrap());
    397     return trap_id_;
    398   }
    399   BasicBlock* true_block() const {
    400     DCHECK(IsBranch());
    401     return true_block_;
    402   }
    403   BasicBlock* false_block() const {
    404     DCHECK(IsBranch());
    405     return false_block_;
    406   }
    407 
    408   void Negate() {
    409     DCHECK(!IsNone());
    410     condition_ = NegateFlagsCondition(condition_);
    411   }
    412 
    413   void Commute() {
    414     DCHECK(!IsNone());
    415     condition_ = CommuteFlagsCondition(condition_);
    416   }
    417 
    418   void Overwrite(FlagsCondition condition) { condition_ = condition; }
    419 
    420   void OverwriteAndNegateIfEqual(FlagsCondition condition) {
    421     DCHECK(condition_ == kEqual || condition_ == kNotEqual);
    422     bool negate = condition_ == kEqual;
    423     condition_ = condition;
    424     if (negate) Negate();
    425   }
    426 
    427   void OverwriteUnsignedIfSigned() {
    428     switch (condition_) {
    429       case kSignedLessThan:
    430         condition_ = kUnsignedLessThan;
    431         break;
    432       case kSignedLessThanOrEqual:
    433         condition_ = kUnsignedLessThanOrEqual;
    434         break;
    435       case kSignedGreaterThan:
    436         condition_ = kUnsignedGreaterThan;
    437         break;
    438       case kSignedGreaterThanOrEqual:
    439         condition_ = kUnsignedGreaterThanOrEqual;
    440         break;
    441       default:
    442         break;
    443     }
    444   }
    445 
    446   // Encodes this flags continuation into the given opcode.
    447   InstructionCode Encode(InstructionCode opcode) {
    448     opcode |= FlagsModeField::encode(mode_);
    449     if (mode_ != kFlags_none) {
    450       opcode |= FlagsConditionField::encode(condition_);
    451     }
    452     return opcode;
    453   }
    454 
    455  private:
    456   FlagsContinuation(FlagsCondition condition, DeoptimizeKind kind,
    457                     DeoptimizeReason reason, Node* frame_state)
    458       : mode_(kFlags_deoptimize),
    459         condition_(condition),
    460         kind_(kind),
    461         reason_(reason),
    462         frame_state_or_result_(frame_state) {
    463     DCHECK_NOT_NULL(frame_state);
    464   }
    465   FlagsContinuation(FlagsCondition condition, Node* result)
    466       : mode_(kFlags_set),
    467         condition_(condition),
    468         frame_state_or_result_(result) {
    469     DCHECK_NOT_NULL(result);
    470   }
    471 
    472   FlagsContinuation(FlagsCondition condition, Runtime::FunctionId trap_id,
    473                     Node* result)
    474       : mode_(kFlags_trap),
    475         condition_(condition),
    476         frame_state_or_result_(result),
    477         trap_id_(trap_id) {
    478     DCHECK_NOT_NULL(result);
    479   }
    480 
    481   FlagsMode const mode_;
    482   FlagsCondition condition_;
    483   DeoptimizeKind kind_;          // Only valid if mode_ == kFlags_deoptimize
    484   DeoptimizeReason reason_;      // Only valid if mode_ == kFlags_deoptimize
    485   Node* frame_state_or_result_;  // Only valid if mode_ == kFlags_deoptimize
    486                                  // or mode_ == kFlags_set.
    487   BasicBlock* true_block_;       // Only valid if mode_ == kFlags_branch.
    488   BasicBlock* false_block_;      // Only valid if mode_ == kFlags_branch.
    489   Runtime::FunctionId trap_id_;  // Only valid if mode_ == kFlags_trap.
    490 };
    491 
    492 }  // namespace compiler
    493 }  // namespace internal
    494 }  // namespace v8
    495 
    496 #endif  // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
    497