instruction-selector-impl.h 17.5 KB
Newer Older
1 2 3 4 5 6 7 8
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_
#define V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_

#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 15 16 17

namespace v8 {
namespace internal {
namespace compiler {

18 19 20 21 22 23 24 25 26 27 28
// Helper struct containing data about a table or lookup switch.
struct SwitchInfo {
  int32_t min_value;           // minimum value of {case_values}
  int32_t max_value;           // maximum value of {case_values}
  size_t value_range;          // |max_value - min_value| + 1
  size_t case_count;           // number of cases
  int32_t* case_values;        // actual case values, unsorted
  BasicBlock** case_branches;  // basic blocks corresponding to case values
  BasicBlock* default_branch;  // default branch target
};

29 30 31 32 33 34 35
// A helper class for the instruction selector that simplifies construction of
// Operands. This class implements a base for architecture-specific helpers.
class OperandGenerator {
 public:
  explicit OperandGenerator(InstructionSelector* selector)
      : selector_(selector) {}

36 37 38 39 40
  InstructionOperand NoOutput() {
    return InstructionOperand();  // Generates an invalid operand.
  }

  InstructionOperand DefineAsRegister(Node* node) {
41
    return Define(node,
42 43
                  UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
                                     GetVReg(node)));
44 45
  }

46
  InstructionOperand DefineSameAsFirst(Node* node) {
47
    return Define(node,
48 49
                  UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT,
                                     GetVReg(node)));
50 51
  }

52 53
  InstructionOperand DefineAsFixed(Node* node, Register reg) {
    return Define(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
54
                                           reg.code(), GetVReg(node)));
55 56
  }

57 58
  template <typename FPRegType>
  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 66 67 68
    return DefineAsConstant(node, ToConstant(node));
  }

  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 76
  InstructionOperand DefineAsLocation(Node* node, LinkageLocation location) {
    return Define(node, ToUnallocatedOperand(location, GetVReg(node)));
77 78
  }

79 80 81 82 83 84 85 86
  InstructionOperand DefineAsDualLocation(Node* node,
                                          LinkageLocation primary_location,
                                          LinkageLocation secondary_location) {
    return Define(node,
                  ToDualLocationUnallocatedOperand(
                      primary_location, secondary_location, GetVReg(node)));
  }

87 88 89 90
  InstructionOperand Use(Node* node) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::NONE,
                                        UnallocatedOperand::USED_AT_START,
                                        GetVReg(node)));
91 92
  }

93 94 95 96 97 98
  InstructionOperand UseAnyAtEnd(Node* node) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
                                        UnallocatedOperand::USED_AT_END,
                                        GetVReg(node)));
  }

99 100 101 102 103 104
  InstructionOperand UseAny(Node* node) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::ANY,
                                        UnallocatedOperand::USED_AT_START,
                                        GetVReg(node)));
  }

105 106 107 108
  InstructionOperand UseRegister(Node* node) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
                                        UnallocatedOperand::USED_AT_START,
                                        GetVReg(node)));
109 110
  }

111 112 113 114 115
  InstructionOperand UseUniqueSlot(Node* node) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_SLOT,
                                        GetVReg(node)));
  }

116 117
  // Use register or operand for the node. If a register is chosen, it won't
  // alias any temporary or output registers.
118 119 120
  InstructionOperand UseUnique(Node* node) {
    return Use(node,
               UnallocatedOperand(UnallocatedOperand::NONE, GetVReg(node)));
121 122 123 124
  }

  // Use a unique register for the node that does not alias any temporary or
  // output registers.
125 126 127
  InstructionOperand UseUniqueRegister(Node* node) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
                                        GetVReg(node)));
128 129
  }

130 131
  InstructionOperand UseFixed(Node* node, Register reg) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_REGISTER,
132
                                        reg.code(), GetVReg(node)));
133 134
  }

135 136 137 138
  template <typename FPRegType>
  InstructionOperand UseFixed(Node* node, FPRegType reg) {
    return Use(node, UnallocatedOperand(UnallocatedOperand::FIXED_FP_REGISTER,
                                        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 146
                             location.AsRegister());
    } else {
147
      return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
148 149
                             location.GetLocation());
    }
150 151
  }

152 153 154 155
  InstructionOperand UseImmediate(int immediate) {
    return sequence()->AddImmediate(Constant(immediate));
  }

156
  InstructionOperand UseImmediate(Node* node) {
157
    return sequence()->AddImmediate(ToConstant(node));
158 159
  }

160 161 162 163
  InstructionOperand UseNegatedImmediate(Node* node) {
    return sequence()->AddImmediate(ToNegatedConstant(node));
  }

164 165
  InstructionOperand UseLocation(Node* node, LinkageLocation location) {
    return Use(node, ToUnallocatedOperand(location, GetVReg(node)));
166 167
  }

168 169 170 171 172
  // Used to force gap moves from the from_location to the to_location
  // immediately before an instruction.
  InstructionOperand UsePointerLocation(LinkageLocation to_location,
                                        LinkageLocation from_location) {
    UnallocatedOperand casted_from_operand =
173
        UnallocatedOperand::cast(TempLocation(from_location));
174
    selector_->Emit(kArchNop, casted_from_operand);
175
    return ToUnallocatedOperand(to_location,
176 177 178
                                casted_from_operand.virtual_register());
  }

179 180 181 182
  InstructionOperand TempRegister() {
    return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
                              UnallocatedOperand::USED_AT_START,
                              sequence()->NextVirtualRegister());
183 184
  }

185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
  int AllocateVirtualRegister() { return sequence()->NextVirtualRegister(); }

  InstructionOperand DefineSameAsFirstForVreg(int vreg) {
    return UnallocatedOperand(UnallocatedOperand::SAME_AS_FIRST_INPUT, vreg);
  }

  InstructionOperand DefineAsRegistertForVreg(int vreg) {
    return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER, vreg);
  }

  InstructionOperand UseRegisterForVreg(int vreg) {
    return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
                              UnallocatedOperand::USED_AT_START, vreg);
  }

200 201
  InstructionOperand TempDoubleRegister() {
    UnallocatedOperand op = UnallocatedOperand(
202 203
        UnallocatedOperand::MUST_HAVE_REGISTER,
        UnallocatedOperand::USED_AT_START, sequence()->NextVirtualRegister());
204 205
    sequence()->MarkAsRepresentation(MachineRepresentation::kFloat64,
                                     op.virtual_register());
206 207 208
    return op;
  }

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 219
  InstructionOperand TempLocation(LinkageLocation location) {
    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 228 229 230 231 232
  }

 protected:
  InstructionSelector* selector() const { return selector_; }
  InstructionSequence* sequence() const { return selector()->sequence(); }
  Zone* zone() const { return selector()->instruction_zone(); }

 private:
233 234
  int GetVReg(Node* node) const { return selector_->GetVirtualRegister(node); }

235 236 237
  static Constant ToConstant(const Node* node) {
    switch (node->opcode()) {
      case IrOpcode::kInt32Constant:
238
        return Constant(OpParameter<int32_t>(node));
239
      case IrOpcode::kInt64Constant:
240
        return Constant(OpParameter<int64_t>(node));
241 242
      case IrOpcode::kFloat32Constant:
        return Constant(OpParameter<float>(node));
243 244 245
      case IrOpcode::kRelocatableInt32Constant:
      case IrOpcode::kRelocatableInt64Constant:
        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 255 256 257 258 259 260
      default:
        break;
    }
    UNREACHABLE();
    return Constant(static_cast<int32_t>(0));
  }

261 262 263 264 265 266 267 268 269 270 271 272 273
  static Constant ToNegatedConstant(const Node* node) {
    switch (node->opcode()) {
      case IrOpcode::kInt32Constant:
        return Constant(-OpParameter<int32_t>(node));
      case IrOpcode::kInt64Constant:
        return Constant(-OpParameter<int64_t>(node));
      default:
        break;
    }
    UNREACHABLE();
    return Constant(static_cast<int32_t>(0));
  }

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 279 280
    return operand;
  }

281
  UnallocatedOperand Use(Node* node, UnallocatedOperand operand) {
282
    DCHECK_NOT_NULL(node);
283
    DCHECK_EQ(operand.virtual_register(), GetVReg(node));
284 285
    selector()->MarkAsUsed(node);
    return operand;
286 287
  }

288 289 290 291 292 293 294 295 296 297 298 299
  UnallocatedOperand ToDualLocationUnallocatedOperand(
      LinkageLocation primary_location, LinkageLocation secondary_location,
      int virtual_register) {
    // We only support the primary location being a register and the secondary
    // one a slot.
    DCHECK(primary_location.IsRegister() &&
           secondary_location.IsCalleeFrameSlot());
    int reg_id = primary_location.AsRegister();
    int slot_id = secondary_location.AsCalleeFrameSlot();
    return UnallocatedOperand(reg_id, slot_id, virtual_register);
  }

300 301
  UnallocatedOperand ToUnallocatedOperand(LinkageLocation location,
                                          int virtual_register) {
302
    if (location.IsAnyRegister()) {
303
      // any machine register.
304 305
      return UnallocatedOperand(UnallocatedOperand::MUST_HAVE_REGISTER,
                                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 315
      return UnallocatedOperand(UnallocatedOperand::FIXED_SLOT,
                                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 327 328 329 330 331 332 333 334
  }

  InstructionSelector* selector_;
};


// The flags continuation is a way to combine a branch or a materialization
// of a boolean value with an instruction that sets the flags register.
// The whole instruction is treated as a unit by the register allocator, and
// thus no spills or moves can be introduced between the flags-setting
// instruction and the branch or set it should be combined with.
335
class FlagsContinuation final {
336
 public:
337 338
  FlagsContinuation() : mode_(kFlags_none) {}

339 340 341 342 343 344 345 346
  // Creates a new flags continuation from the given condition and true/false
  // blocks.
  FlagsContinuation(FlagsCondition condition, BasicBlock* true_block,
                    BasicBlock* false_block)
      : mode_(kFlags_branch),
        condition_(condition),
        true_block_(true_block),
        false_block_(false_block) {
347 348
    DCHECK_NOT_NULL(true_block);
    DCHECK_NOT_NULL(false_block);
349 350
  }

351 352
  // Creates a new flags continuation for an eager deoptimization exit.
  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 360
  }

  // Creates a new flags continuation for a boolean value.
  static FlagsContinuation ForSet(FlagsCondition condition, Node* result) {
361
    return FlagsContinuation(condition, result);
362 363
  }

364 365 366 367 368 369
  // Creates a new flags continuation for a wasm trap.
  static FlagsContinuation ForTrap(FlagsCondition condition,
                                   Runtime::FunctionId trap_id, Node* result) {
    return FlagsContinuation(condition, trap_id, result);
  }

370 371
  bool IsNone() const { return mode_ == kFlags_none; }
  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 378
    return condition_;
  }
379 380 381 382
  DeoptimizeKind kind() const {
    DCHECK(IsDeoptimize());
    return kind_;
  }
383 384 385 386
  DeoptimizeReason reason() const {
    DCHECK(IsDeoptimize());
    return reason_;
  }
387 388 389 390
  Node* frame_state() const {
    DCHECK(IsDeoptimize());
    return frame_state_or_result_;
  }
391
  Node* result() const {
392
    DCHECK(IsSet());
393
    return frame_state_or_result_;
394
  }
395 396 397 398
  Runtime::FunctionId trap_id() const {
    DCHECK(IsTrap());
    return trap_id_;
  }
399
  BasicBlock* true_block() const {
400
    DCHECK(IsBranch());
401 402 403
    return true_block_;
  }
  BasicBlock* false_block() const {
404
    DCHECK(IsBranch());
405 406 407
    return false_block_;
  }

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 419
  void Overwrite(FlagsCondition condition) { condition_ = condition; }

420
  void OverwriteAndNegateIfEqual(FlagsCondition condition) {
421
    DCHECK(condition_ == kEqual || condition_ == kNotEqual);
422 423 424 425 426
    bool negate = condition_ == kEqual;
    condition_ = condition;
    if (negate) Negate();
  }

427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445
  void OverwriteUnsignedIfSigned() {
    switch (condition_) {
      case kSignedLessThan:
        condition_ = kUnsignedLessThan;
        break;
      case kSignedLessThanOrEqual:
        condition_ = kUnsignedLessThanOrEqual;
        break;
      case kSignedGreaterThan:
        condition_ = kUnsignedGreaterThan;
        break;
      case kSignedGreaterThanOrEqual:
        condition_ = kUnsignedGreaterThanOrEqual;
        break;
      default:
        break;
    }
  }

446 447
  // Encodes this flags continuation into the given opcode.
  InstructionCode Encode(InstructionCode opcode) {
448 449 450 451 452
    opcode |= FlagsModeField::encode(mode_);
    if (mode_ != kFlags_none) {
      opcode |= FlagsConditionField::encode(condition_);
    }
    return opcode;
453 454 455
  }

 private:
456 457
  FlagsContinuation(FlagsCondition condition, DeoptimizeKind kind,
                    DeoptimizeReason reason, Node* frame_state)
458 459
      : mode_(kFlags_deoptimize),
        condition_(condition),
460
        kind_(kind),
461 462 463 464 465 466
        reason_(reason),
        frame_state_or_result_(frame_state) {
    DCHECK_NOT_NULL(frame_state);
  }
  FlagsContinuation(FlagsCondition condition, Node* result)
      : mode_(kFlags_set),
467
        condition_(condition),
468 469
        frame_state_or_result_(result) {
    DCHECK_NOT_NULL(result);
470 471
  }

472 473 474 475 476 477 478 479 480
  FlagsContinuation(FlagsCondition condition, Runtime::FunctionId trap_id,
                    Node* result)
      : mode_(kFlags_trap),
        condition_(condition),
        frame_state_or_result_(result),
        trap_id_(trap_id) {
    DCHECK_NOT_NULL(result);
  }

481
  FlagsMode const mode_;
482
  FlagsCondition condition_;
483 484
  DeoptimizeKind kind_;          // Only valid if mode_ == kFlags_deoptimize
  DeoptimizeReason reason_;      // Only valid if mode_ == kFlags_deoptimize
485 486 487 488
  Node* frame_state_or_result_;  // Only valid if mode_ == kFlags_deoptimize
                                 // or mode_ == kFlags_set.
  BasicBlock* true_block_;       // Only valid if mode_ == kFlags_branch.
  BasicBlock* false_block_;      // Only valid if mode_ == kFlags_branch.
489
  Runtime::FunctionId trap_id_;  // Only valid if mode_ == kFlags_trap.
490 491 492 493 494 495 496
};

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_INSTRUCTION_SELECTOR_IMPL_H_